Patrick Rall
Quantum Information Center, University of Texas at Austin
Wa iwe yii ti o nifẹ tabi fẹ lati jiroro? Lootọ tabi fi asọye silẹ lori SciRate.
áljẹbrà
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.
Featured image: We present a novel algorithm for energy estimation that calculates the estimate one bit at a time. Each bit is extracted via a polynomial that is applied to the Hamiltonian via singular value transformation. The image shows polynomial approximations of cosines that are post-processed to approximate square waves that indicate the bits.
Presentation at TQC 2021
Gbajumo Lakotan
Data Data BibTeX
Awọn itọkasi
[1] Pawel Wocjan, Kristan Temme, Szegedy Walk Unitaries for Quantum Maps arXiv:2107.07365 (2021).
arXiv: 2107.07365
[2] John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang, A Grand Unification of Quantum Algorithms arXiv:2105.02859 (2021).
arXiv: 2105.02859
[3] Lin Lin, Yu Tong, Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers arXiv:2102.11340 (2021).
arXiv: 2102.11340
[4] Earl T. Campbell, Early fault-tolerant simulations of the Hubbard model arXiv:2012.09238 (2020).
arXiv: 2012.09238
[5] Yuan Su, Hsin-Yuan Huang, Earl T. Campbell, Nearly tight Trotterization of interacting electrons arXiv:2012.09194 Quantum 5, 495 (2020).
https://doi.org/10.22331/q-2021-07-05-495
arXiv: 2012.09194
[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).
https: / / doi.org/ 10.1063 / 5.0040313
arXiv: 2012.06681
[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).
https://doi.org/10.22331/q-2021-06-24-481
arXiv: 2012.06283
[8] Isaac Chuang, Grand unification of quantum algorithms. Seminar presentation at IQC Waterloo. (2020).
https://uwaterloo.ca/institute-for-quantum-computing/events/grand-unification-quantum-algorithms
[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).
https: / / doi.org/ 10.1103 / PhysRevResearch.3.033151
arXiv: 2010.04173
[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).
arXiv: 2009.11270
[11] András Gilyén, Zhao Song, Ewin Tang, An improved quantum-inspired algorithm for linear regression arXiv:2009.07268 (2020).
arXiv: 2009.07268
[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).
https://doi.org/10.1088/2058-9565/abc096
arXiv: 2005.13434
[13] Patrick Rall, Quantum Algorithms for Estimating Physical Quantities using Block-Encodings Phys. Rev. A 102, 022408 arXiv:2004.06832 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022408
arXiv: 2004.06832
[14] Alessandro Roggero, Spectral density estimation with the Gaussian Integral Transform Phys. Rev. A 102, 022409 arXiv:2004.04889 (2020).
https: / / doi.org/ 10.1103 / PhysRevA.102.022409
arXiv: 2004.04889
[15] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, Mario Szegedy, Finding Angles for Quantum Signal Processing with Machine Precision arXiv:2003.02831 (2020).
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 2003.02831
[16] Lin Lin, Yu Tong, Near-optimal ground state preparation arXiv:2002.12508 Quantum 4, 372 (2020).
https://doi.org/10.22331/q-2020-12-14-372
arXiv: 2002.12508
[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).
https: / / doi.org/ 10.1103 / PhysRevX.11.011020
arXiv: 1912.08854
[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] 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).
https://doi.org/10.22331/q-2020-06-29-287
arXiv: 1910.01659
[20] 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
[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).
https: / / doi.org/ 10.1137 / 1.9781611975994.12
arXiv: 1907.09965
[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).
arXiv: 1812.03584
[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).
https://doi.org/10.4230/LIPics.ICALP.2019.69
arXiv: 1807.06456
[24] 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
[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).
arXiv: 1806.01838
[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).
https: / / doi.org/ 10.1103 / PhysRevLett.121.010501
arXiv: 1711.11025
[27] Guang Hao Low, Isaac L. Chuang, Hamiltonian Simulation by Uniform Spectral Amplification arXiv:1707.05391 (2017).
arXiv: 1707.05391
[28] Iordanis Kerenidis, Anupam Prakash, Quantum gradient descent for linear systems and least squares arXiv:1704.04992 Phys. Rev. A 101, 022316 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.101.022316
arXiv: 1704.04992
[29] Yosi Atia, Dorit Aharonov, Fast-forwarding of Hamiltonians and exponentially precise measurements Nature Communications volume 8, 1572 arXiv:1610.09619 (2016).
https://doi.org/10.1038/s41467-017-01637-7
arXiv: 1610.09619
[30] 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
[31] 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
[32] Iordanis Kerenidis, Anupam Prakash, Quantum Recommendation Systems arXiv:1603.08675 ITCS 2017, p. 49:1–49:21 (2016).
https://doi.org/10.4230/LIPics.ITCS.2017.49
arXiv: 1603.08675
[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).
https://doi.org/10.1137/16M1087072
arXiv: 1511.02306
[34] Ashley Montanaro, Quantum speedup of Monte Carlo methods Proc. Roy. Soc. Ser. A, vol. 471 no. 2181, 20150301 arXiv:1504.06987 (2015).
https://doi.org/10.1098/rspa.2015.0301
arXiv: 1504.06987
[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).
https: / / doi.org/ 10.1103 / PhysRevA.92.062315
arXiv: 1502.02677
[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).
https://doi.org/10.1109/FOCS.2015.54
arXiv: 1501.01715
[37] Amnon Ta-Shma, Inverting well conditioned matrices in quantum logspace STOC ’13, Pages 881–890 (2013).
https: / / doi.org/ 10.1145 / 2488608.2488720
[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).
https://doi.org/10.1098/rspa.2012.0686
arXiv: 1207.2307
[39] Maris Ozols, Martin Roetteler, Jérémie Roland, Quantum Rejection Sampling arXiv:1103.2774 IRCS’12 pages 290-308 (2011).
https: / / doi.org/ 10.1145 / 2493252.2493256
arXiv: 1103.2774
[40] Man-Hong Yung, Alán Aspuru-Guzik, A Quantum-Quantum Metropolis Algorithm arXiv:1011.1468 PNAS 109, 754-759 (2011).
https: / / doi.org/ 10.1073 / pnas.1111758109
arXiv: 1011.1468
[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).
https://doi.org/10.4230/LIPIcs.STACS.2012.636
arXiv: 1010.4458
[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).
https: / / doi.org/ 10.1038 / nature09770
arXiv: 0911.3635
[43] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola, Bounded Independence Fools Halfspaces arXiv:0902.3757 FOCS ’09, Pages 171–180 (2009).
arXiv: 0902.3757
[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).
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171
[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).
https: / / doi.org/ 10.1038 / nature06257
arXiv: 0709.2996
[46] Chris Marriott, John Watrous, Quantum Arthur-Merlin Games CC, 14(2): 122 – 152 arXiv:cs/0506068 (2005).
https://doi.org/10.1007/s00037-005-0194-x
arXiv: cs/0506068
[47] Mario Szegedy, Quantum speed-up of Markov chain based algorithms FOCS ’04, Pages 32-41 (2004).
https://doi.org/10.1109/FOCS.2004.53
[48] Hartmut Klauck, Quantum Time-Space Tradeoffs for Sorting STOC 03, Pages 69–76 arXiv:quant-ph/0211174 (2002).
https: / / doi.org/ 10.1145 / 780542.780553
arXiv: quant-ph/0211174
[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).
https://doi.org/10.1007/3-540-48224-5_29
arXiv: quant-ph/0102078
[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).
https://doi.org/10.1090/conm/305/05215
arXiv: quant-ph/0005055
[52] Dorit Aharonov, Alexei Kitaev, Noam Nisan, Quantum Circuits with Mixed States STOC ’97, pages 20-30 arXiv:quant-ph/9806029 (1998).
https: / / doi.org/ 10.1145 / 276698.276708
arXiv: quant-ph/9806029
[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).
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph/9804066
[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).
https://doi.org/10.1137/S0097539796300933
arXiv: quant-ph/9701001
[55] A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem arXiv:quant-ph/9511026 (1995).
arXiv: quant-ph/9511026
[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).
https://doi.org/10.1137/S0097539795293172
arXiv: quant-ph/9508027
[57] Theodore J. Rivlin, An Introduction to the Approximation of Functions Dover Publications, Inc. New York. ISBN-13:978-0486640693 (1969).
Sọ nipa
[1] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, “Nearly tight Trotterization of interacting electrons”, arXiv: 2012.09194.
[2] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang, “A Grand Unification of Quantum Algorithms”, arXiv: 2105.02859.
Awọn atokọ ti o wa loke wa lati SAO / NASA ADS (imudojuiwọn ti o gbẹhin ni aṣeyọri 2021-10-23 15:14:11). Atokọ naa le pe bi kii ṣe gbogbo awọn onisewejade ti o pese data pipe ati pipe.
On Iṣẹ ti a tọka-nipasẹ Crossref ko si data lori awọn iṣẹ atokọ ti a ri (igbidanwo kẹhin 2021-10-23 15:14:09).
Iwe yii ni a tẹjade ni kuatomu labẹ awọn Idawọle Creative Commons 4.0 International (CC BY 4.0) iwe-aṣẹ. Aṣẹ-ori wa pẹlu awọn ti o ni aṣẹ lori ara atilẹba bi awọn onkọwe tabi awọn ile-iṣẹ wọn.
PlatoAi. Webim Reimagined. Data oye Amplified.
Tẹ ibi lati wọle si.
Orisun: https://quantum-journal.org/papers/q-2021-10-19-566/
