Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation

Patrick Rall

Quantum Information Center, University of Texas at Austin

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Updated version: The authors have uploaded version v4 of this work to the arXiv which may contain updates or corrections not contained in the published version v3. The authors left the following comment on the arXiv:
Added Jupyter notebook for reproducibility and fixed a benchmarking error


We consider performing phase estimation under the following conditions: we are given only one copy of the input state, the input state does not have to be an eigenstate of the unitary, and the state must not be measured. Most quantum estimation algorithms make assumptions that make them unsuitable for this 'coherent' setting, leaving only the textbook approach. We present novel algorithms for phase, energy, and amplitude estimation that are both conceptually and computationally simpler than the textbook method, featuring both a smaller query complexity and ancilla footprint. They do not require a quantum Fourier transform, and they do not require a quantum sorting network to compute the median of several estimates. Instead, they use block-encoding techniques to compute the estimate one bit at a time, performing all amplification via singular value transformation. These improved subroutines accelerate the performance of quantum Metropolis sampling and quantum Bayesian inference.

Presentation at TQC 2021

A fundamental objective of quantum computing is to help study physical systems. One of the earliest results in the area was a fast quantum algorithm for measuring the energy of a system, which can serve as a building block for other quantum algorithms. However this algorithm is very complicated and hard to analyze. In this paper we present a simpler method based on applying polynomials to the Hamiltonian that extract each of the bits of the estimate. This technique is up to 20x faster than the prior state of the art.

► BibTeX data

► References

[1] Pawel Wocjan, Kristan Temme, Szegedy Walk Unitaries for Quantum Maps arXiv:2107.07365 (2021).

[2] John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang, A Grand Unification of Quantum Algorithms arXiv:2105.02859 (2021).

[3] Lin Lin, Yu Tong, Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers arXiv:2102.11340 (2021).

[4] Earl T. Campbell, Early fault-tolerant simulations of the Hubbard model arXiv:2012.09238 (2020).

[5] Yuan Su, Hsin-Yuan Huang, Earl T. Campbell, Nearly tight Trotterization of interacting electrons arXiv:2012.09194 Quantum 5, 495 (2020).

[6] Alexander Engel, Graeme Smith, Scott E. Parker, A framework for applying quantum computation to nonlinear dynamical systems arXiv:2012.06681 Physics of Plasmas 28, 062305 (2020).

[7] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, Jiasu Wang, Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance arXiv:2012.06283 Quantum 5, 481 (2020).

[8] Isaac Chuang, Grand unification of quantum algorithms. Seminar presentation at IQC Waterloo. (2020).

[9] Lewis Wright, Fergus Barratt, James Dborin, George H. Booth, Andrew G. Green, Automatic Post-selection by Ancillae Thermalisation arXiv:2010.04173 Phys. Rev. Research 3, 033151 (2020).

[10] Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, Pawel Wocjan, Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions arXiv:2009.11270 (2020).

[11] András Gilyén, Zhao Song, Ewin Tang, An improved quantum-inspired algorithm for linear regression arXiv:2009.07268 (2020).

[12] Phillip W. K. Jensen, Lasse Bjørn Kristensen, Jakob S. Kottmann, Alán Aspuru-Guzik, Quantum Computation of Eigenvalues within Target Intervals Quantum Science and Technology 6, 015004 arXiv:2005.13434 (2020).

[13] Patrick Rall, Quantum Algorithms for Estimating Physical Quantities using Block-Encodings Phys. Rev. A 102, 022408 arXiv:2004.06832 (2020).

[14] Alessandro Roggero, Spectral density estimation with the Gaussian Integral Transform Phys. Rev. A 102, 022409 arXiv:2004.04889 (2020).

[15] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, Mario Szegedy, Finding Angles for Quantum Signal Processing with Machine Precision arXiv:2003.02831 (2020).

[16] Lin Lin, Yu Tong, Near-optimal ground state preparation arXiv:2002.12508 Quantum 4, 372 (2020).

[17] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, Shuchen Zhu, A Theory of Trotter Error Phys. Rev. X 11, 011020 arXiv:1912.08854 (2019).

[18] Dmitry Grinko, Julien Gacon, Christa Zoufal, Stefan Woerner, Iterative Quantum Amplitude Estimation npj Quantum Inf 7, 52 arXiv:1912.05559 (2019).

[19] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, Matthias Troyer, Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm Quantum 4, 287 arXiv:1910.01659 (2019).

[20] Scott Aaronson, Patrick Rall, Quantum Approximate Counting,Simplified Symposium on Simplicity in Algorithms. 2020, 24-32 arXiv:1908.10846(2019).

[21] Aram W. Harrow, Annie Y. Wei, Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions Proc. of SODA 2020 arXiv:1907.09965 (2019).

[22] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash, q-means: A quantum algorithm for unsupervised machine learning arXiv:1812.03584 NIPS 32 (2018).

[23] Yassine Hamoudi, Frédéric Magniez, Quantum Chebyshev's Inequality and Applications ICALP, LIPIcs Vol 132, pages 69:1-99:16 arXiv:1807.06456 (2018).

[24] Jeongwan Haah, Product Decomposition of Periodic Functions in Quantum Signal Processing Quantum 3, 190. arXiv:1806.10236 (2018).

[25] András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe, Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics arXiv:1806.01838 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019) Pages 193–204 (2018).

[26] David Poulin, Alexei Kitaev, Damian S. Steiger, Matthew B. Hastings, Matthias Troyer, Quantum Algorithm for Spectral Measurement with Lower Gate Count arXiv:1711.11025 Phys. Rev. Lett. 121, 010501 (2017).

[27] Guang Hao Low, Isaac L. Chuang, Hamiltonian Simulation by Uniform Spectral Amplification arXiv:1707.05391 (2017).

[28] Iordanis Kerenidis, Anupam Prakash, Quantum gradient descent for linear systems and least squares arXiv:1704.04992 Phys. Rev. A 101, 022316 (2017).

[29] Yosi Atia, Dorit Aharonov, Fast-forwarding of Hamiltonians and exponentially precise measurements Nature Communications volume 8, 1572 arXiv:1610.09619 (2016).

[30] Guang Hao Low, Isaac L. Chuang, Hamiltonian Simulation by Qubitization Quantum 3, 163 arXiv:1610.06546 (2016).

[31] Guang Hao Low, Isaac L. Chuang, Optimal Hamiltonian Simulation by Quantum Signal Processing Phys. Rev. Lett. 118, 010501 arXiv:1606.02685 (2016).

[32] Iordanis Kerenidis, Anupam Prakash, Quantum Recommendation Systems arXiv:1603.08675 ITCS 2017, p. 49:1–49:21 (2016).

[33] Andrew M. Childs, Robin Kothari, Rolando D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision SIAM Journal on Computing 46, 1920-1950 arXiv:1511.02306 (2015).

[34] Ashley Montanaro, Quantum speedup of Monte Carlo methods Proc. Roy. Soc. Ser. A, vol. 471 no. 2181, 20150301 arXiv:1504.06987 (2015).

[35] Shelby Kimmel, Guang Hao Low, Theodore J. Yoder, Robust Calibration of a Universal Single-Qubit Gate-Set via Robust Phase Estimation Phys. Rev. A 92, 062315 arXiv:1502.02677 (2015).

[36] Dominic W. Berry, Andrew M. Childs, Robin Kothari, Hamiltonian simulation with nearly optimal dependence on all parameters arXiv:1501.01715 Proc. FOCS, pp. 792-809 (2015).

[37] Amnon Ta-Shma, Inverting well conditioned matrices in quantum logspace STOC '13, Pages 881–890 (2013).

[38] Robert Beals, Stephen Brierley, Oliver Gray, Aram Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather, Efficient Distributed Quantum Computing Proc. R. Soc. A 2013 469, 20120686 arXiv:1207.2307 (2012).

[39] Maris Ozols, Martin Roetteler, Jérémie Roland, Quantum Rejection Sampling arXiv:1103.2774 IRCS'12 pages 290-308 (2011).

[40] Man-Hong Yung, Alán Aspuru-Guzik, A Quantum-Quantum Metropolis Algorithm arXiv:1011.1468 PNAS 109, 754-759 (2011).

[41] Andris Ambainis, Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations arXiv:1010.4458 STACS'12, 636-647 (2010).

[42] K. Temme, T.J. Osborne, K.G. Vollbrecht, D. Poulin, F. Verstraete, Quantum Metropolis Sampling arXiv:0911.3635 Nature volume 471, pages 87–90 (2009).

[43] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola, Bounded Independence Fools Halfspaces arXiv:0902.3757 FOCS '09, Pages 171–180 (2009).

[44] Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, Quantum algorithm for solving linear systems of equations Phys. Rev. Lett. 103, 150502 arXiv:0811.3171 (2008).

[45] B. L. Higgins, D. W. Berry, S. D. Bartlett, H. M. Wiseman, G. J. Pryde, Entanglement-free Heisenberg-limited phase estimation Nature.450:393-396 arXiv:0709.2996 (2007).

[46] Chris Marriott, John Watrous, Quantum Arthur-Merlin Games CC, 14(2): 122 - 152 arXiv:cs/​0506068 (2005).

[47] Mario Szegedy, Quantum speed-up of Markov chain based algorithms FOCS '04, Pages 32-41 (2004).

[48] Hartmut Klauck, Quantum Time-Space Tradeoffs for Sorting STOC 03, Pages 69–76 arXiv:quant-ph/​0211174 (2002).

[49] Peter Hoyer, Jan Neerbek, Yaoyun Shi, Quantum complexities of ordered searching, sorting, and element distinctness 28th ICALP, LNCS 2076, pp. 346-357 arXiv:quant-ph/​0102078 (2001).

[50] Isaac Chuang and Michael Nielsen, Quantum Computation and Quantum Information Cambridge University Press. ISBN-13: 978-1107002173 (2000).

[51] Gilles Brassard, Peter Hoyer, Michele Mosca, Alain Tapp, Quantum Amplitude Amplification and Estimation Quantum Computation and Quantum Information, 305:53-74 arXiv:quant-ph/​0005055 (2000).

[52] Dorit Aharonov, Alexei Kitaev, Noam Nisan, Quantum Circuits with Mixed States STOC '97, pages 20-30 arXiv:quant-ph/​9806029 (1998).

[53] Ashwin Nayak, Felix Wu, The quantum query complexity of approximating the median and related statistics arXiv:quant-ph/​9804066 STOC '99 pp 384-393 (1998).

[54] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani, Strengths and Weaknesses of Quantum Computing arXiv:quant-ph/​9701001 SIAM Journal on Computing 26(5):1510-1523 (1997).

[55] A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem arXiv:quant-ph/​9511026 (1995).

[56] Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer SIAM J.Sci.Statist.Comput. 26, 1484 arXiv:quant-ph/​9508027 (1995).

[57] Theodore J. Rivlin, An Introduction to the Approximation of Functions Dover Publications, Inc. New York. ISBN-13:978-0486640693 (1969).

Cited by

[1] Rahul Sarkar and Theodore J. Yoder, "Density theorems with applications in quantum signal processing", Journal of Computational and Applied Mathematics 430, 115243 (2023).

[2] Patrick Rall, Chunhao Wang, and Pawel Wocjan, "Thermal State Preparation via Rounding Promises", Quantum 7, 1132 (2023).

[3] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng, "Quantum Resources Required to Block-Encode a Matrix of Classical Data", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[4] Mark Steudtner, Sam Morley-Short, William Pol, Sukin Sim, Cristian L. Cortes, Matthias Loipersberger, Robert M. Parrish, Matthias Degroote, Nikolaj Moll, Raffaele Santagati, and Michael Streif, "Fault-tolerant quantum computation of molecular observables", Quantum 7, 1164 (2023).

[5] Noah Linden and Ronald de Wolf, "Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation", Quantum 6, 872 (2022).

[6] Ryu Hayakawa, "Quantum algorithm for persistent Betti numbers and topological data analysis", Quantum 6, 873 (2022).

[7] Linlin Ye, Zhaoqi Wu, and Shao-Ming Fei, "Tsallis relative α entropy of coherence dynamics in Grover′s search algorithm", Communications in Theoretical Physics 75 8, 085101 (2023).

[8] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, "Nearly tight Trotterization of interacting electrons", Quantum 5, 495 (2021).

[9] Youle Wang, Lei Zhang, Zhan Yu, and Xin Wang, "Quantum phase processing and its applications in estimating phase and entropies", Physical Review A 108 6, 062413 (2023).

[10] J. M. Hernández Cáceres, E. F. Combarro, and I. F. Rúa, "Combinatorial and rotational quantum abstract detecting systems", Quantum Information Processing 21 2, 66 (2022).

[11] Muhammad Abdullah Ijaz and Muhammad Faryad, "Noise analysis of Grover and phase estimation algorithms implemented as quantum singular value transformations for a small number of noisy qubits", Scientific Reports 13 1, 20144 (2023).

[12] Zane M. Rossi and Isaac L. Chuang, "Semantic embedding for quantum algorithms", Journal of Mathematical Physics 64 12, 122202 (2023).

[13] Ruizhe Zhang, Guoming Wang, and Peter Johnson, "Computing Ground State Properties with Early Fault-Tolerant Quantum Computers", Quantum 6, 761 (2022).

[14] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "Complexity of Implementing Trotter Steps", PRX Quantum 4 2, 020323 (2023).

[15] Zane M. Rossi and Isaac L. Chuang, "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle", Quantum 6, 811 (2022).

[16] Patrick Rall and Bryce Fuller, "Amplitude Estimation from Quantum Signal Processing", Quantum 7, 937 (2023).

[17] Pawel Wocjan and Kristan Temme, "Szegedy Walk Unitaries for Quantum Maps", Communications in Mathematical Physics 402 3, 3201 (2023).

[18] Guillermo Lugilde, Elías F. Combarro, and Ignacio F. Rúa, "Functional quantum abstract detecting systems", Quantum Information Processing 23 3, 82 (2024).

[19] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang, "Grand Unification of Quantum Algorithms", PRX Quantum 2 4, 040203 (2021).

[20] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[21] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "On the complexity of implementing Trotter steps", arXiv:2211.09133, (2022).

[22] Garrett T. Floyd, David P. Landau, and Michael R. Geller, "Quantum algorithm for Wang-Landau sampling", arXiv:2208.09543, (2022).

[23] Adam Callison and Dan E. Browne, "Improved maximum-likelihood quantum amplitude estimation", arXiv:2209.03321, (2022).

[24] Anand Natarajan and Tina Zhang, "Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification", arXiv:2303.01545, (2023).

[25] Nikhil S. Mande and Ronald de Wolf, "Tight Bounds for Quantum Phase Estimation and Related Problems", arXiv:2305.04908, (2023).

[26] Sean Greenaway, William Pol, and Sukin Sim, "A case study against QSVT: assessment of quantum phase estimation improved by signal processing techniques", arXiv:2404.01396, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-12 05:05:55) and SAO/NASA ADS (last updated successfully 2024-04-12 05:05:56). The list may be incomplete as not all publishers provide suitable and complete citation data.

1 thought on “Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation

  1. Pingback: Research Roundup for October 2021 - Quantum Computing Report