Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations

The problem of phase estimation (or amplitude estimation) admits a quadratic quantum speedup. Wang, Higgott, and Brierley [Wang, Higgott, and Brierley, Phys. Rev. Lett. 122, 140504 (2019)] have shown that there is a continuous tradeoff between quantum speedup and circuit depth [by defining a family of algorithms known as $\alpha$-quantum phase estimation $\left(\alpha \text{−}\mathrm{QPE}\right)$]. In this paper, we show that the scaling of $\alpha \text{−}\mathrm{QPE}$ can be naturally and succinctly derived within the framework of quantum singular value transformation (QSVT). From the QSVT perspective, a greater number of coherent oracle calls translates into a better polynomial approximation to the sign function, which is the key routine for solving phase estimation. The better the approximation to the sign function, the fewer samples one needs to determine the sign accurately. With this idea, we simplify the proof of $\alpha \text{−}\mathrm{QPE}$, while providing an interpretation of the interpolation parameters, and show that QSVT is a promising framework for reasoning about classical-quantum interpolations.

Figure 1

Circuit for iterative phase estimation. $U|\psi \rangle =e^{i\varphi }|\psi \rangle$, $R_Z\left(x\right)=|0\rangle \langle 0|+e^{ix}|1\rangle \langle 1|$, $M\in \mathbb{N}$, $\theta \in \mathbb{R}$, and $E\in \{0,1\}$, with $M\text{and}\theta$ to be set as part of the algorithm

Figure 2

For a fixed $\delta$ (here, $\delta =0.2$), polynomials of increasing degree allow for a better approximation to the step function (equivalently, with a smaller $\eta$). While this decreases the necessary number of samples, the implementation of polynomials of higher degrees in the quantum singular value transformation framework requires longer coherent computation. A theorem of [24] ensures the existence of a suitable polynomial for a given choice of $\delta \text{and}\eta$ (see Lemma $2$); here we used the pyqsp [21, 26, 27] package to explicitly generate such polynomials.