Amplitude Estimation from Quantum Signal Processing

Patrick Rall1 and Bryce Fuller2

1IBM Quantum, MIT-IBM Watson AI Lab, Cambridge, Massachusetts 02142, USA
2IBM Quantum, Thomas J Watson Research Center, Yorktown Heights, New York 10598, USA

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

Abstract

Amplitude estimation algorithms are based on Grover's algorithm: alternating reflections about the input state and the desired outcome. But what if we are given the ability to perform arbitrary rotations, instead of just reflections? In this situation, we find that quantum signal processing lets us estimate the amplitude in a more flexible way. We leverage this technique to give improved and simplified algorithms for many amplitude estimation tasks: we perform non-destructive estimation without any assumptions on the amplitude, develop an algorithm with improved performance in practice, present a new method for unbiased amplitude estimation, and finally give a simpler method for trading quantum circuit depth for more repetitions of short circuits.

► BibTeX data

► References

[1] Arjan Cornelissen, Yassine Hamoudi A Sublinear-Time Quantum Algorithm for Approximating Partition Functions arXiv:2207.08643 Proceedings of the 34th Symposium on Discrete Algorithms (SODA) (2022).
https:/​/​doi.org/​10.1137/​1.9781611977554.ch46
arXiv:2207.08643

[2] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, Giacomo Nannicini Quantum tomography using state-preparation unitaries arXiv:2207.08800 Proceedings of the 34th Symposium on Discrete Algorithms (SODA) (2022).
https:/​/​doi.org/​10.1137/​1.9781611977554.ch47
arXiv:2207.08800

[3] Yunpeng Zhao, Haiyan Wang, Kuai Xu, Yue Wang, Ji Zhu, Feng Wang Adaptive Algorithm for Quantum Amplitude Estimation arXiv:2206.08449 (2022).
arXiv:2206.08449

[4] Alberto Manzano, Daniele Musso, Álvaro Leitao Real Quantum Amplitude Estimation arXiv:2204.13641 EPJ Quantum Technol. 10, 2 (2022).
https:/​/​doi.org/​10.1140/​epjqt/​s40507-023-00159-0
arXiv:2204.13641

[5] Ansis Rosmanis Hybrid Quantum-Classical Search Algorithms arXiv:2202.11443 (2022).
arXiv:2202.11443

[6] Jiasu Wang, Yulong Dong, Lin Lin On the energy landscape of symmetric quantum signal processing arXiv:2110.04993 Quantum 6, 850 (2021).
https:/​/​doi.org/​10.22331/​q-2022-11-03-850
arXiv:2110.04993

[7] Noah Linden, Ronald de Wolf Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation arXiv:2109.10215 Quantum 6, 872 (2021).
https:/​/​doi.org/​10.22331/​q-2022-12-07-872
arXiv:2109.10215

[8] Tudor Giurgica-Tiron, Sonika Johri, Iordanis Kerenidis, Jason Nguyen, Neal Pisenti, Anupam Prakash, Ksenia Sosnova, Ken Wright, William Zeng Low depth amplitude estimation on a trapped ion quantum computer arXiv:2109.09685 Physical Review Research 4, 033034 (2021).
https:/​/​doi.org/​10.1103/​PhysRevResearch.4.033034
arXiv:2109.09685

[9] John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang A Grand Unification of Quantum Algorithms arXiv:2105.02859 PRX Quantum 2, 040203 (2021).
https:/​/​doi.org/​10.1103/​PRXQuantum.2.040203
arXiv:2105.02859

[10] Patrick Rall Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation arXiv:2103.09717 Quantum 5, 566 (2021).
https:/​/​doi.org/​10.22331/​q-2021-10-19-566
arXiv:2103.09717

[11] Tudor Giurgica-Tironc, Iordanis Kerenidisa, Farrokh Labibd, Anupam Prakash, and William Zeng Low depth algorithms for quantum amplitude estimation arXiv:2012.03348 Quantum 6, 745 (2020).
https:/​/​doi.org/​10.22331/​q-2022-06-27-745
arXiv:2012.03348

[12] Ramgopal Venkateswaran, Ryan O'Donnell Quantum Approximate Counting with Nonadaptive Grover Iterations arXiv:2010.04370 38th International Symposium on Theoretical Aspects of Computer Science (STACS) (2020).
https:/​/​doi.org/​10.4230/​LIPIcs.STACS.2021.59
arXiv:2010.04370

[13] Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, Pawel Wocjan Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions arXiv:2009.11270 Quantum 6, 789 (2020).
https:/​/​doi.org/​10.22331/​q-2022-09-01-789
arXiv:2009.11270

[14] Kwangmin Yu, Hyunkyung Lim, Pooja Rao, Dasol Jin Comparison of Amplitude Estimation Algorithms by Implementation arXiv:2005.05300 (2020).
arXiv:2005.05300

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

[16] Kouhei Nakaji Faster Amplitude Estimation arXiv:2003.02417 QIC20.13-14-2 (2020).
https:/​/​doi.org/​10.26421/​QIC20.13-14-2
arXiv:2003.02417

[17] Lin Lin, Yu Tong. Near-optimal ground state preparation Quantum 4, 372 arXiv:2002.12508 (2020).
https:/​/​doi.org/​10.22331/​q-2020-12-14-372
arXiv:2002.12508

[18] Dmitry Grinko, Julien Gacon, Christa Zoufal, Stefan Woerner Iterative Quantum Amplitude Estimation npj Quantum Inf 7, 52 arXiv:1912.05559 (2019).
https:/​/​doi.org/​10.1038/​s41534-021-00379-1
arXiv:1912.05559

[19] Scott Aaronson, Patrick Rall. Quantum Approximate Counting, Simplified Symposium on Simplicity in Algorithms. 2020, 24-32 arXiv:1908.10846 (2019).
https:/​/​doi.org/​10.1137/​1.9781611976014.5
arXiv:1908.10846

[20] 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).
https:/​/​doi.org/​10.1137/​1.9781611975994.12
arXiv:1907.09965

[21] Yohichi Suzuki, Shumpei Uno, Rudy Raymond, Tomoki Tanaka, Tamiya Onodera, Naoki Yamamoto Amplitude estimation without phase estimation arXiv:1904.10246 Quantum Information Processing, 19, 75 (2019).
https:/​/​doi.org/​10.1007/​s11128-019-2565-2
arXiv:1904.10246

[22] Jeongwan Haah Product Decomposition of Periodic Functions in Quantum Signal Processing Quantum 3, 190. arXiv:1806.10236 (2018).
https:/​/​doi.org/​10.22331/​q-2019-10-07-190
arXiv:1806.10236

[23] 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 (2018).
https:/​/​doi.org/​10.1145/​3313276.3316366
arXiv:1806.01838

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

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

[26] Guang Hao Low, Isaac L. Chuang Hamiltonian Simulation by Qubitization Quantum 3, 163 arXiv:1610.06546 (2016).
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
arXiv:1610.06546

[27] Guang Hao Low, Isaac L. Chuang Optimal Hamiltonian Simulation by Quantum Signal Processing Phys. Rev. Lett. 118, 010501 arXiv:1606.02685 (2016).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501
arXiv:1606.02685

[28] Earl T. Campbell, Joe O'Gorman An efficient magic state approach to small angle rotations Quantum Science and Technology, 1, 015007 arXiv:1603.04230 (2016).
https:/​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007
arXiv:1603.04230

[29] Guang Hao Low, Theodore J. Yoder, Isaac L. Chuang The methodology of resonant equiangular composite quantum gates arXiv:1603.03996 Phys. Rev. X 6, 041067 (2016).
https:/​/​doi.org/​10.1103/​PhysRevX.6.041067
arXiv:1603.03996

[30] Ashley Montanaro Quantum speedup of Monte Carlo methods Proc. Roy. Soc. Ser. A, vol. 471 no. 2181 arXiv:1504.06987 (2015).
https:/​/​doi.org/​10.1098/​rspa.2015.0301
arXiv:1504.06987

[31] Theodore J. Yoder, Guang Hao Low, Isaac L. Chuang Fixed-point quantum search with an optimal number of queries arXiv:1409.3305 Phys. Rev. Lett. 113, 210501 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.113.210501
arXiv:1409.3305

[32] Itai Arad, Alexei Kitaev, Zeph Landau, Umesh Vazirani ``An area law and sub-exponential algorithm for 1D systems'' arXiv:1301.1162.
arXiv:1301.1162

[33] J. Demeyer ``Diophantine Sets over Polynomial Rings and Hilbert's Tenth Problem for Function Fields'' PhD Thesis at Universiteit Gent. (2007).

[34] 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).
https:/​/​doi.org/​10.1090/​conm/​305/​05215
arXiv:quant-ph/0005055

[35] Ashwin Nayak, Felix Wu. The quantum query complexity of approximating the median and related statistics arXiv:quant-ph/​9804066 Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC 1999) Pages 384-393 (1998).
https:/​/​doi.org/​10.1145/​301250.301349
arXiv:quant-ph/9804066

[36] Theodore Rivlin An Introduction to the Approximation of Functions SIAM Review Vol. 12, Iss. 2 Dover Publications, Inc. New York. (1969).
https:/​/​doi.org/​10.1137/​1012069

[37] C. Clopper, E. Pearson The use of confidence or fiducial limits illustrated in the case of the binomial, Biometrika, vol. 26, no. 4, pp. 404–413. (1934).
https:/​/​doi.org/​10.2307/​2331986

Cited by

[1] Kosuke Mitarai, Kiichiro Toyoizumi, and Wataru Mizukami, "Perturbation theory with quantum signal processing", Quantum 7, 1000 (2023).

[2] 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).

[3] 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).

[4] Yongming Li and Ariel Neufeld, "Quantum Monte Carlo algorithm for solving Black-Scholes PDEs for high-dimensional option pricing in finance and its proof of overcoming the curse of dimensionality", arXiv:2301.09241, (2023).

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

[6] Jin-Peng Liu and Lin Lin, "Dense outputs from quantum simulations", arXiv:2307.14441, (2023).

[7] Gabriele Agliardi, Corey O'Meara, Kavitha Yogaraj, Kumar Ghosh, Piergiacomo Sabino, Marina Fernández-Campoamor, Giorgio Cortiana, Juan Bernabé-Moreno, Francesco Tacchino, Antonio Mezzacapo, and Omar Shehab, "Quadratic quantum speedup in evaluating bilinear risk functions", arXiv:2304.10385, (2023).

[8] Kumar J. B. Ghosh, Kavitha Yogaraj, Gabriele Agliardi, Piergiacomo Sabino, Marina Fernández-Campoamor, Juan Bernabé-Moreno, Giorgio Cortiana, Omar Shehab, and Corey O'Meara, "Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling", arXiv:2305.09501, (2023).

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