Document Open Access Logo

Tight Bounds for Quantum Phase Estimation and Related Problems

Authors Nikhil S. Mande , Ronald de Wolf

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.81.pdf
  • Filesize: 0.79 MB
  • 16 pages

Document Identifiers

Author Details

Nikhil S. Mande
  • University of Liverpool, UK
Ronald de Wolf
  • QuSoft, CWI and University of Amsterdam, The Netherlands

Funding

  • Mande, Nikhil S.: Part of this work was done while the author was a postdoc at QuSoft and CWI, Amsterdam.
  • de Wolf, Ronald: Partially supported by the Dutch Research Council (NWO/OCW), as part of the Quantum Software Consortium programme (project number 024.003.037).

Acknowledgements

We thank Jordi Weggemans for useful comments and for a pointer to [{Lin Lin} and Yu Tong, 2020].

Cite As Get BibTex

Nikhil S. Mande and Ronald de Wolf. Tight Bounds for Quantum Phase Estimation and Related Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 81:1-81:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.81

Abstract

Phase estimation, due to Kitaev [arXiv'95], is one of the most fundamental subroutines in quantum computing, used in Shor’s factoring algorithm, optimization algorithms, quantum chemistry algorithms, and many others. In the basic scenario, one is given black-box access to a unitary U, and an eigenstate |ψ⟩ of U with unknown eigenvalue e^{iθ}, and the task is to estimate the eigenphase θ within ±δ, with high probability. The repeated application of U and U^{-1} is typically the most expensive part of phase estimation, so for us the cost of an algorithm will be that number of applications.
Motivated by the "guided Hamiltonian problem" in quantum chemistry, we tightly characterize the cost of several variants of phase estimation where we are no longer given an arbitrary eigenstate, but are required to estimate the maximum eigenphase of U, aided by advice in the form of states (or a unitary preparing those states) which are promised to have at least a certain overlap γ with the top eigenspace. We give algorithms and matching lower bounds (up to logarithmic factors) for all ranges of parameters. We show a crossover point below which advice is not helpful: o(1/γ²) copies of the advice state (or o(1/γ) applications of an advice-preparing unitary) are not significantly better than having no advice at all. We also show that having knowledge of the eigenbasis of U does not significantly reduce cost. Our upper bounds use the subroutine of generalized maximum-finding of van Apeldoorn, Gilyén, Gribling, and de Wolf [Quantum'20], the state-based Hamiltonian simulation of Lloyd, Mohseni, and Rebentrost [Nature Physics'13], and several other techniques. Our lower bounds follow by reductions from a fractional version of the Boolean OR function with advice, which we lower bound by a simple modification of the adversary method of Ambainis [JCSS'02]. As an immediate consequence we also obtain a lower bound on the complexity of the Unitary recurrence time problem, matching an upper bound of She and Yuen [ITCS'23] and resolving an open question posed by them.
Lastly, we study how efficiently one can reduce the error probability in the basic phase-estimation scenario. We show that an algorithm solving phase estimation to precision δ with error probability at most ε must have cost Ω(1/δ log(1/ε)), matching the obvious way to error-reduce the basic constant-error-probability phase estimation algorithm. This contrasts with some other scenarios in quantum computing (e.g. search) where error-reduction costs only a factor O(√{log(1/ε)}). Our lower bound technique uses a variant of the polynomial method with trigonometric polynomials.

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
  • Theory of computation → Quantum complexity theory
Keywords
  • Phase estimation
  • quantum computing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750-767, 2002. Earlier version in STOC'00. URL: https://doi.org/10.1006/jcss.2002.1826.
  2. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. Quantum, 4:230, 2020. https://arxiv.org/abs/1705.01843. Earlier version in FOCS'17. URL: https://doi.org/10.22331/q-2020-02-14-230.
  3. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, 2001. https://arxiv.org/abs/quant-ph/9802049. Earlier version in FOCS'98. URL: https://doi.org/10.1145/502090.502097.
  4. Arvid J. Bessen. Lower bound for quantum phase estimation. Physical Review A, 71(4):042313, 2005. Google Scholar
  5. Peter Borwein and Tamás Erdélyi. Polynomials and polynomial inequalities, volume 161. Springer Science & Business Media, 1995. Google Scholar
  6. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53-74. AMS, 2002. URL: https://arxiv.org/abs/quant-ph/0005055.
  7. Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In Proceedings of 40th IEEE FOCS, pages 358-368, 1999. https://arxiv.org/abs/cs/9904019. URL: https://doi.org/10.1109/SFFCS.1999.814607.
  8. Chris Cade, Marten Folkertsma, and Jordi Weggemans. Complexity of the guided local Hamiltonian problem: Improved parameters and extension to excited states, 2022. URL: https://arxiv.org/abs/2207.10097.
  9. Yanlin Chen and Ronald de Wolf. Quantum algorithms and lower bounds for linear regression with norm constraints. In Proceedings of 50th ICALP, 2023. To appear. URL: https://arxiv.org/abs/2110.13086.
  10. Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. In Proceedings of the Royal Society of London, volume A454, pages 339-354, 1998. URL: https://arxiv.org/abs/quant-ph/9708016.
  11. Yimin Ge, Jordi Tura, and J. Ignacio Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. Journal of Mathematical Physics, 60(2):022202, 2019. URL: https://arxiv.org/abs/1712.03193.
  12. Sevag Gharibian, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae. Improved hardness results for the guided local Hamiltonian problem, 2022. URL: https://doi.org/10.48550/arXiv.2207.10250.
  13. Sevag Gharibian and Francçois Le Gall. Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum PCP conjecture. In Proceedings of 54th ACM STOC, pages 19-32, 2022. URL: https://arxiv.org/abs/2111.09079.
  14. András Gilyén. Quantum Singular Value Transformation & Its Algorithmic Applications. PhD thesis, University of Amsterdam, 2019. Google Scholar
  15. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of 51st ACM STOC, pages 193-204, 2019. URL: https://arxiv.org/abs/1806.01838.
  16. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of 28th ACM STOC, pages 212-219, 1996. URL: https://arxiv.org/abs/quant-ph/9605043.
  17. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters, 103(15):150502, 2009. URL: https://arxiv.org/abs/0811.3171.
  18. Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3(13), 2017. URL: https://arxiv.org/abs/1608.00281.
  19. A. Yu. Kitaev. Quantum measurements and the abelian stabilizer problem, 1995. URL: https://arxiv.org/abs/quant-ph/9511026.
  20. Yao-Ting Lin. A note on quantum phase estimation. https://arxiv.org/abs/2304.02241, 2023.
  21. Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4(372), 2020. https://arxiv.org/abs/2002.12508. URL: https://doi.org/10.22331/q-2020-12-14-372.
  22. Lin Lin and Yu Tong. Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3(010318), 2022. URL: https://arxiv.org/abs/2102.11340.
  23. Noah Linden and Ronald de Wolf. Average-case verification of the quantum Fourier transform enables worst-case phase estimation. Quantum, 6(872), 2022. https://arxiv.org/abs/2109.1021. URL: https://doi.org/10.22331/q-2022-12-07-872.
  24. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10:631-633, 2013. URL: https://arxiv.org/abs/1307.0401.
  25. Nikhil S. Mande and Ronald de Wolf. Tight bounds for quantum phase estimation and related problems. CoRR, 2023. URL: https://doi.org/10.48550/arXiv.2305.04908.
  26. Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of 31st ACM STOC, pages 384-393, 1999. URL: https://doi.org/10.1145/301250.301349.
  27. David Poulin and Pawel Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. Physical Review Letters, 103(22):220502, 2009. https://arxiv.org/abs/0905.2199. URL: https://doi.org/10.1103/PhysRevLett.103.220502.
  28. Patrick Rall. Faster coherent quantum algorithms for phase, energy, and amplitude estimation. Quantum, 5(566), 2021. https://arxiv.org/abs/2103.09717. URL: https://doi.org/10.22331/q-2021-10-19-566.
  29. Adrian She and Henry Yuen. Unitary property testing lower bounds by polynomials. In 14th Innovations in Theoretical Computer Science Conference, ITCS, volume 251 of LIPIcs, pages 96:1-96:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. URL: https://doi.org/10.4230/LIPIcs.ITCS.2023.96.
  30. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484-1509, 1997. Earlier version in FOCS'94. URL: https://arxiv.org/abs/quant-ph/9508027.
  31. Kianna Wan, Mario Berta, and Earl T. Campbell. A randomized quantum algorithm for statistical phase estimation. Physical Review Letters, 129(030503), 2022. URL: https://arxiv.org/abs/2110.12071.
  32. Jordi Weggemans, Marten Folkertsma, and Chris Cade. Guidable local Hamiltonian problems with implications to heuristic Ansätze state preparation and the quantum PCP conjecture, 2023. URL: https://arxiv.org/abs/2302.11578.
  33. Ronald de Wolf. A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions. Quantum Information and Computation, 8(10):943-950, 2008. URL: https://arxiv.org/abs/0802.1816.
  34. Ronald de Wolf. Quantum computing: Lecture notes, 2019. arXiv:1907.09415, version 5. URL: https://arxiv.org/abs/1907.09415.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact