Amplitude Estimation From Quantum Signal Processing

Republished By Plato

Followers: 0

Patrick Rall¹ and Bryce Fuller²

¹IBM Quantum, MIT-IBM Watson AI Lab, Cambridge, Massachusetts 02142, USA
²IBM 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

@article{Rall2023amplitudeestimation, doi = {10.22331/q-2023-03-02-937}, url = {https://doi.org/10.22331/q-2023-03-02-937}, title = {Amplitude {E}stimation from {Q}uantum {S}ignal {P}rocessing}, author = {Rall, Patrick and Fuller, Bryce}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {937}, month = mar, year = {2023}<br /> }

► 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] Xin Wang, Youle Wang, Zhan Yu, and Lei Zhang, “Quantum Phase Processing: Transform and Extract Eigen-Information of Quantum Systems”, arXiv:2209.14278, (2022).

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

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

The above citations are from SAO/NASA ADS (last updated successfully 2023-03-03 05:17:47). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2023-03-03 05:17:45).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

SEO Powered Content & PR Distribution. Get Amplified Today.
Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
Source: https://quantum-journal.org/papers/q-2023-03-02-937/

Time Stamp: March 2, 2023

A Multi-Qubit Quantum Gate Using the Zeno Effect

Source Cluster:

Quantum Journal

Source Node: 2261556

Time Stamp: Sep 7, 2023

Republished By Plato

Abstract

► BibTeX data

► References

Cited by

Experimental Communication Through Superposition of Quantum Channels

Security of quantum key distribution with detection-efficiency mismatch in the multiphoton case

Only Classical Parameterised States have Optimal Measurements under Least Squares Loss

Towards Quantum One-Time Memories from Stateless Hardware

Generalization despite overfitting in quantum machine learning models

Bell-type inequalities for systems of relativistic vector bosons

Classification of measurement-based quantum wire in stabilizer PEPS

Generalized Belief Propagation Algorithms for Decoding of Surface Codes

Local Probabilistic Decoding of a Quantum Code

A Multi-Qubit Quantum Gate Using the Zeno Effect

About Us

Vertical Search & Ai

Platform

Stay Connected

Account