{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T05:54:58Z","timestamp":1775195698299,"version":"3.50.1"},"reference-count":57,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T00:00:00Z","timestamp":1634601600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Scott Aaronson","award":["Vannevar Bush Faculty Fellowship"],"award-info":[{"award-number":["Vannevar Bush Faculty Fellowship"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.22331\/q-2021-10-19-566","type":"journal-article","created":{"date-parts":[[2021,10,19]],"date-time":"2021-10-19T18:21:10Z","timestamp":1634667670000},"page":"566","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":33,"title":["Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation"],"prefix":"10.22331","volume":"5","author":[{"given":"Patrick","family":"Rall","sequence":"first","affiliation":[{"name":"Quantum Information Center, University of Texas at Austin"}]}],"member":"9598","published-online":{"date-parts":[[2021,10,19]]},"reference":[{"key":"0","unstructured":"Pawel Wocjan, Kristan Temme, Szegedy Walk Unitaries for Quantum Maps arXiv:2107.07365 (2021)."},{"key":"1","doi-asserted-by":"crossref","unstructured":"John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang, A Grand Unification of Quantum Algorithms arXiv:2105.02859 (2021).","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Lin Lin, Yu Tong, Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers arXiv:2102.11340 (2021).","DOI":"10.1103\/PRXQuantum.3.010318"},{"key":"3","doi-asserted-by":"crossref","unstructured":"Earl T. Campbell, Early fault-tolerant simulations of the Hubbard model arXiv:2012.09238 (2020).","DOI":"10.1088\/2058-9565\/ac3110"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Yuan Su, Hsin-Yuan Huang, Earl T. Campbell, Nearly tight Trotterization of interacting electrons arXiv:2012.09194 Quantum 5, 495 (2020).","DOI":"10.22331\/q-2021-07-05-495"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1063\/5.0040313"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2021-06-24-481"},{"key":"7","unstructured":"Isaac Chuang, Grand unification of quantum algorithms. Seminar presentation at IQC Waterloo. (2020)."},{"key":"8","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevResearch.3.033151"},{"key":"9","doi-asserted-by":"crossref","unstructured":"Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, Pawel Wocjan, Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions arXiv:2009.11270 (2020).","DOI":"10.1109\/QCE52317.2021.00027"},{"key":"10","unstructured":"Andr\u00e1s Gily\u00e9n, Zhao Song, Ewin Tang, An improved quantum-inspired algorithm for linear regression arXiv:2009.07268 (2020)."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Phillip W. K. Jensen, Lasse Bj\u00f8rn Kristensen, Jakob S. Kottmann, Al\u00e1n Aspuru-Guzik, Quantum Computation of Eigenvalues within Target Intervals Quantum Science and Technology 6, 015004 arXiv:2005.13434 (2020).","DOI":"10.1088\/2058-9565\/abc096"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Patrick Rall, Quantum Algorithms for Estimating Physical Quantities using Block-Encodings Phys. Rev. A 102, 022408 arXiv:2004.06832 (2020).","DOI":"10.1103\/PhysRevA.102.022408"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Alessandro Roggero, Spectral density estimation with the Gaussian Integral Transform Phys. Rev. A 102, 022409 arXiv:2004.04889 (2020).","DOI":"10.1103\/PhysRevA.102.022409"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, Mario Szegedy, Finding Angles for Quantum Signal Processing with Machine Precision arXiv:2003.02831 (2020).","DOI":"10.1145\/3313276.3316366"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Lin Lin, Yu Tong, Near-optimal ground state preparation arXiv:2002.12508 Quantum 4, 372 (2020).","DOI":"10.22331\/q-2020-12-14-372"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Dmitry Grinko, Julien Gacon, Christa Zoufal, Stefan Woerner, Iterative Quantum Amplitude Estimation npj Quantum Inf 7, 52 arXiv:1912.05559 (2019).","DOI":"10.1038\/s41534-021-00379-1"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.22331\/q-2020-06-29-287"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Scott Aaronson, Patrick Rall, Quantum Approximate Counting,Simplified Symposium on Simplicity in Algorithms. 2020, 24-32 arXiv:1908.10846(2019).","DOI":"10.1137\/1.9781611976014.5"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1137\/1.9781611975994.12"},{"key":"21","unstructured":"Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash, q-means: A quantum algorithm for unsupervised machine learning arXiv:1812.03584 NIPS 32 (2018)."},{"key":"22","doi-asserted-by":"publisher","unstructured":"Yassine Hamoudi, Fr\u00e9d\u00e9ric Magniez, Quantum Chebyshev's Inequality and Applications ICALP, LIPIcs Vol 132, pages 69:1-99:16 arXiv:1807.06456 (2018).","DOI":"10.4230\/LIPIcs.ICALP.2019.69"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Jeongwan Haah, Product Decomposition of Periodic Functions in Quantum Signal Processing Quantum 3, 190. arXiv:1806.10236 (2018).","DOI":"10.22331\/q-2019-10-07-190"},{"key":"24","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s Gily\u00e9n, 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\u2013204 (2018).","DOI":"10.1145\/3313276.3316366"},{"key":"25","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.121.010501"},{"key":"26","unstructured":"Guang Hao Low, Isaac L. Chuang, Hamiltonian Simulation by Uniform Spectral Amplification arXiv:1707.05391 (2017)."},{"key":"27","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis, Anupam Prakash, Quantum gradient descent for linear systems and least squares arXiv:1704.04992 Phys. Rev. A 101, 022316 (2017).","DOI":"10.1103\/PhysRevA.101.022316"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Yosi Atia, Dorit Aharonov, Fast-forwarding of Hamiltonians and exponentially precise measurements Nature Communications volume 8, 1572 arXiv:1610.09619 (2016).","DOI":"10.1038\/s41467-017-01637-7"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Guang Hao Low, Isaac L. Chuang, Hamiltonian Simulation by Qubitization Quantum 3, 163 arXiv:1610.06546 (2016).","DOI":"10.22331\/q-2019-07-12-163"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Guang Hao Low, Isaac L. Chuang, Optimal Hamiltonian Simulation by Quantum Signal Processing Phys. Rev. Lett. 118, 010501 arXiv:1606.02685 (2016).","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis, Anupam Prakash, Quantum Recommendation Systems arXiv:1603.08675 ITCS 2017, p. 49:1\u201349:21 (2016).","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1137\/16M1087072"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro, Quantum speedup of Monte Carlo methods Proc. Roy. Soc. Ser. A, vol. 471 no. 2181, 20150301 arXiv:1504.06987 (2015).","DOI":"10.1098\/rspa.2015.0301"},{"key":"34","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevA.92.062315"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1109\/FOCS.2015.54"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Amnon Ta-Shma, Inverting well conditioned matrices in quantum logspace STOC '13, Pages 881\u2013890 (2013).","DOI":"10.1145\/2488608.2488720"},{"key":"37","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1098\/rspa.2012.0686"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Maris Ozols, Martin Roetteler, J\u00e9r\u00e9mie Roland, Quantum Rejection Sampling arXiv:1103.2774 IRCS'12 pages 290-308 (2011).","DOI":"10.1145\/2493252.2493256"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Man-Hong Yung, Al\u00e1n Aspuru-Guzik, A Quantum-Quantum Metropolis Algorithm arXiv:1011.1468 PNAS 109, 754-759 (2011).","DOI":"10.1073\/pnas.1111758109"},{"key":"40","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.4230\/LIPIcs.STACS.2012.636"},{"key":"41","doi-asserted-by":"publisher","unstructured":"K. Temme, T.J. Osborne, K.G. Vollbrecht, D. Poulin, F. Verstraete, Quantum Metropolis Sampling arXiv:0911.3635 Nature volume 471, pages 87\u201390 (2009).","DOI":"10.1038\/nature09770"},{"key":"42","doi-asserted-by":"crossref","unstructured":"Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola, Bounded Independence Fools Halfspaces arXiv:0902.3757 FOCS '09, Pages 171\u2013180 (2009).","DOI":"10.1109\/FOCS.2009.68"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, Quantum algorithm for solving linear systems of equations Phys. Rev. Lett. 103, 150502 arXiv:0811.3171 (2008).","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"44","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/nature06257"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Chris Marriott, John Watrous, Quantum Arthur-Merlin Games CC, 14(2): 122 - 152 arXiv:cs\/0506068 (2005).","DOI":"10.1007\/s00037-005-0194-x"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Mario Szegedy, Quantum speed-up of Markov chain based algorithms FOCS '04, Pages 32-41 (2004).","DOI":"10.1109\/FOCS.2004.53"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Hartmut Klauck, Quantum Time-Space Tradeoffs for Sorting STOC 03, Pages 69\u201376 arXiv:quant-ph\/0211174 (2002).","DOI":"10.1145\/780542.780553"},{"key":"48","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1007\/3-540-48224-5_29"},{"key":"49","unstructured":"Isaac Chuang and Michael Nielsen, Quantum Computation and Quantum Information Cambridge University Press. ISBN-13: 978-1107002173 (2000)."},{"key":"50","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1090\/conm\/305\/05215"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Alexei Kitaev, Noam Nisan, Quantum Circuits with Mixed States STOC '97, pages 20-30 arXiv:quant-ph\/9806029 (1998).","DOI":"10.1145\/276698.276708"},{"key":"52","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1145\/301250.301349"},{"key":"53","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1137\/S0097539796300933"},{"key":"54","unstructured":"A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem arXiv:quant-ph\/9511026 (1995)."},{"key":"55","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1137\/S0097539795293172"},{"key":"56","unstructured":"Theodore J. Rivlin, An Introduction to the Approximation of Functions Dover Publications, Inc. New York. ISBN-13:978-0486640693 (1969)."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-10-19-566\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,1,12]],"date-time":"2023-01-12T21:38:12Z","timestamp":1673559492000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-10-19-566\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,19]]},"references-count":57,"URL":"https:\/\/doi.org\/10.22331\/q-2021-10-19-566","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,19]]},"article-number":"566"}}