Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations
arXiv:2207.14810 · doi:10.1103/PhysRevA.106.062419
Abstract
The problem of Phase Estimation (or Amplitude Estimation) admits a quadratic quantum speedup. Wang, Higgott and Brierley [2019, Phys. Rev. Lett. 122 140504] have shown that there is a continuous trade-off between quantum speedup and circuit depth (by defining a family of algorithms known as -QPE). In this work, we show that the scaling of -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 -QPE, while providing a new interpretation of the interpolation parameters, and show that QSVT is a promising framework for reasoning about classical-quantum interpolations.
arXiv comment7 pages, 1 figure. Keywords: alpha-QPE, alpha-VQE, hybrid classical-quantum computing, quantum algorithms, quantum singular value transformation, limited coherence, oracle complexity
References in corpus (13)
- Quantum algorithm for solving linear systems of equations
- Hamiltonian Simulation by Qubitization
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Semiclassical Fourier Transform for Quantum Computation
- A Grand Unification of Quantum Algorithms
- Quantum speedup of Monte Carlo methods
- Quantum Counting
- Amplitude estimation without phase estimation
- Accelerated Variational Quantum Eigensolver
- Efficient Bayesian Phase Estimation
- Near-optimal ground state preparation
- Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
- Low depth algorithms for quantum amplitude estimation