The Efficient Preparation of Normal Distributions in Quantum Registers
Future Lab for Applied Research and Engineering, JPMorgan Chase & Co.
| Published: | 2021-12-23, volume 5, page 609 |
| Eprint: | arXiv:2009.06601v5 |
| Doi: | https://doi.org/10.22331/q-2021-12-23-609 |
| Citation: | Quantum 5, 609 (2021). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
The efficient preparation of input distributions is an important problem in obtaining quantum advantage in a wide range of domains. We propose a novel quantum algorithm for the efficient preparation of arbitrary normal distributions in quantum registers. To the best of our knowledge, our work is the first to leverage the power of Mid-Circuit Measurement and Reuse (MCMR), in a way that is broadly applicable to a range of state-preparation problems. Specifically, our algorithm employs a repeat-until-success scheme, and only requires a constant-bounded number of repetitions in expectation. In the experiments presented, the use of MCMR enables up to a 862.6x reduction in required qubits. Furthermore, the algorithm is provably resistant to both phase-flip and bit-flip errors, leading to a first-of-its-kind empirical demonstration on real quantum hardware, the MCMR-enabled Honeywell System Models H0 and H1-2.
Featured image: A normal distribution generated in the quantum register using the Quantum Galton Machine algorithm, inspired by the classical Galton machine, shown on the left.
Popular summary
► BibTeX data
► References
[1] Almudena Carrera Vazquezand Stefan Woerner ``Efficient State Preparation for Quantum Amplitude Estimation'' Physical Review Applied 15 (2021).
https://doi.org/10.1103/physrevapplied.15.034027
[2] Nikitas Stamatopoulos, Daniel J Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen, and Stefan Woerner, ``Option pricing using quantum computers'' Quantum 4, 291 (2020).
https://doi.org/10.22331/q-2020-07-06-291
[3] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost, ``Quantum principal component analysis'' Nature Physics 10, 631–633 (2014).
https://doi.org/10.1038/nphys3029
[4] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd, ``Quantum algorithm for linear systems of equations'' Physical review letters 103, 150502 (2009).
https://doi.org/10.1103/physrevlett.103.150502
[5] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig, ``Quantum machine learning: a classical perspective'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170551 (2018).
https://doi.org/10.1098/rspa.2017.0551
[6] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii, ``Quantum circuit learning'' Physical Review A 98, 032309 (2018).
https://doi.org/10.1103/physreva.98.032309
[7] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd, ``Quantum support vector machine for big data classification'' Physical review letters 113, 130503 (2014).
https://doi.org/10.1103/physrevlett.113.130503
[8] Marco Pistoia, Syed Farhan Ahmad, Akshay Ajagekar, Alexander Buts, Shouvanik Chakrabarti, Dylan Herman, Shaohan Hu, Andrew Jena, Pierre Minssen, Pradeep Niroula, Arthur Rattew, Yue Sun, and Romina Yalovetzky, ``Quantum Machine Learning for Finance'' Proceedings of the 40th IEEE/ACM International Conference on Computer Aided Design (ICCAD) 2021 Invited Special Session Paper.
https://arxiv.org/abs/2109.04298
[9] Martin Pleschand Časlav Brukner ``Quantum-state preparation with universal gate decompositions'' Physical Review A 83, 032302 (2011).
https://doi.org/10.1103/physreva.83.032302
[10] John Preskill ``Quantum Computing in the NISQ era and beyond'' Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[11] Zhaoqing Pan, Weijie Yu, Xiaokai Yi, Asifullah Khan, Feng Yuan, and Yuhui Zheng, ``Recent progress on generative adversarial networks (GANs): A survey'' IEEE Access 7, 36322–36333 (2019).
https://doi.org/10.1109/ACCESS.2019.2905015
[12] Christa Zoufal, Aurélien Lucchi, and Stefan Woerner, ``Quantum generative adversarial networks for learning and loading random distributions'' npj Quantum Information 5, 1–9 (2019).
https://doi.org/10.1038/s41534-019-0223-2
[13] Ling Hu, Shu-Hao Wu, Weizhou Cai, Yuwei Ma, Xianghao Mu, Yuan Xu, Haiyan Wang, Yipu Song, Dong-Ling Deng, and Chang-Ling Zou, ``Quantum generative adversarial learning in a superconducting quantum circuit'' Science advances 5, eaav2761 (2019).
https://doi.org/10.1126/sciadv.aav2761
[14] Lov Groverand Terry Rudolph ``Creating superpositions that correspond to efficiently integrable probability distributions'' arXiv preprint (2002).
https://arxiv.org/abs/quant-ph/0208112
[15] Adam Holmesand AY Matsuura ``Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions'' arXiv preprint (2020).
https://arxiv.org/abs/2005.04351
[16] Alexei Kitaevand William A Webb ``Wavefunction preparation and resampling using a quantum computer'' arXiv preprint arXiv:0801.0342 (2008).
https://arxiv.org/abs/0801.0342
[17] Thomas Häner, Martin Roetteler, and Krysta M Svore, ``Optimizing quantum circuits for arithmetic'' arXiv preprint (2018).
https://arXiv.org/abs/1805.12445
[18] Bahram Ahansazand Abbas Ektesabi ``Quantum speedup, non-Markovianity and formation of bound state'' Scientific reports 9, 1–12 (2019).
https://doi.org/10.1038/s41598-019-51290-x
[19] Viv Kendonand Olivier Maloyer ``Optimal computation with non-unitary quantum walks'' Theoretical computer science 394, 187–196 (2008).
https://doi.org/10.1016/j.tcs.2007.12.011
[20] J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. S. Allman, C. H. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, and et al., ``Demonstration of the trapped-ion quantum CCD computer architecture'' Nature 592, 209–213 (2021).
https://doi.org/10.1038/s41586-021-03318-4
[21] Romina Yalovetzky, Pierre Minssen, Dylan Herman, and Marco Pistoia, ``NISQ-HHL: Portfolio Optimization for Near-Term Quantum Hardware'' (2021).
https://arxiv.org/abs/2110.15958
[22] Adam Paetznickand Krysta M Svore ``Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries'' arXiv preprint (2013).
https://arXiv.org/abs/1311.1074
[23] Yudong Cao, Gian Giacomo Guerreschi, and Alán Aspuru-Guzik, ``Quantum neuron: an elementary building block for machine learning on quantum computers'' arXiv preprint (2017).
https://arXiv.org/abs/1711.11240
[24] Wei Hu ``Towards a real quantum neuron'' Natural Science 10, 99–109 (2018).
https://doi.org/10.4236/ns.2018.103011
[25] Alex Bocharov, Martin Roetteler, and Krysta M Svore, ``Efficient synthesis of universal repeat-until-success quantum circuits'' Physical review letters 114, 080502 (2015).
https://doi.org/10.1103/physrevlett.114.080502
[26] Nathan Wiebeand Martin Roetteler ``Quantum Arithmetic and Numerical Analysis Using Repeat-until-Success Circuits'' Quantum Info. Comput. 16, 134–178 (2016).
https://doi.org/10.26421/QIC16.1-2-9
[27] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C Benjamin, and Xiao Yuan, ``Variational ansatz-based quantum simulation of imaginary time evolution'' npj Quantum Information 5, 1–6 (2019).
https://doi.org/10.1038/s41534-019-0187-2
[28] Sheldon Natenberg ``Option volatility and pricing: Advanced trading strategies and techniques'' McGraw-Hill Education (2014).
[29] Michael A Nielsenand Isaac Chuang ``Quantum computation and quantum information'' (2002).
https://doi.org/10.1017/CBO9780511976667
[30] Thomas G Draper ``Addition on a quantum computer'' arXiv preprint (2000).
https://arxiv.org/abs/quant-ph/0008033
[31] Thomas G Draper, Samuel A Kutin, Eric M Rains, and Krysta M Svore, ``A logarithmic-depth quantum carry-lookahead adder'' arXiv preprint (2004).
https://arxiv.org/abs/quant-ph/0406142
[32] Yunseong Nam, Yuan Su, and Dmitri Maslov, ``Approximate quantum Fourier transform with O (n log (n)) T gates'' NPJ Quantum Information 6, 1–6 (2020).
https://doi.org/10.1038/s41534-020-0257-5
[33] Hayato Goto ``Resource requirements for a fault-tolerant quantum Fourier transform'' Physical Review A 90, 052318 (2014).
https://doi.org/10.1103/PhysRevA.90.052318
[34] Stephane Beauregard ``Circuit for Shor's algorithm using 2n+3 qubits'' (2002).
https://arxiv.org/abs/quant-ph/0205095
[35] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter, ``Elementary gates for quantum computation'' Physical review A 52, 3457 (1995).
https://doi.org/10.1103/physreva.52.3457
[36] Hale F Trotter ``On the product of semi-groups of operators'' Proceedings of the American Mathematical Society 10, 545–551 (1959).
https://doi.org/10.1090/S0002-9939-1959-0108732-6
[37] Ying Liand Simon C Benjamin ``Efficient variational quantum simulator incorporating active error minimization'' Physical Review X 7, 021050 (2017).
https://doi.org/10.1103/physrevx.7.021050
Cited by
[1] Sergi Ramos-Calderer, "Efficient quantum interpolation of natural data", Physical Review A 106 6, 062427 (2022).
[2] Hans Hon Sang Chan, Richard Meister, Tyson Jones, David P. Tew, and Simon C. Benjamin, "Grid-based methods for chemistry simulations on a quantum computer", Science Advances 9 9, eabo7484 (2023).
[3] Mudassir Moosa, Thomas W Watts, Yiyou Chen, Abhijat Sarma, and Peter L McMahon, "Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions", Quantum Science and Technology 9 1, 015002 (2024).
[4] Ar A Melnikov, A A Termanova, S V Dolgov, F Neukart, and M R Perelshtein, "Quantum state preparation using tensor networks", Quantum Science and Technology 8 3, 035027 (2023).
[5] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).
[6] Yizhou Liu, Weijie J. Su, and Tongyang Li, "On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks", Quantum 7, 1030 (2023).
[7] 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).
[8] Ismail Yunus Akhalwaya, Adam Connolly, Roland Guichard, Steven Herbert, Cahit Kargi, Alexandre Krajenbrink, Michael Lubasch, Conor Mc Keever, Julien Sorci, Michael Spranger, and Ifan Williams, "A Modular Engine for Quantum Monte Carlo Integration", arXiv:2308.06081, (2023).
[9] Marco Pistoia, Syed Farhan Ahmad, Akshay Ajagekar, Alexander Buts, Shouvanik Chakrabarti, Dylan Herman, Shaohan Hu, Andrew Jena, Pierre Minssen, Pradeep Niroula, Arthur Rattew, Yue Sun, and Romina Yalovetzky, "Quantum Machine Learning for Finance", arXiv:2109.04298, (2021).
[10] Bálint Koczor, "Exponential Error Suppression for Near-Term Quantum Devices", Physical Review X 11 3, 031057 (2021).
[11] Wibe A. de Jong, Kyle Lee, James Mulligan, Mateusz Płoskoń, Felix Ringer, and Xiaojun Yao, "Quantum simulation of nonequilibrium dynamics and thermalization in the Schwinger model", Physical Review D 106 5, 054508 (2022).
[12] Justin Yirka and Yiğit Subaşı, "Qubit-efficient entanglement spectroscopy using qubit resets", Quantum 5, 535 (2021).
[13] Youle Wang, Benchi Zhao, and Xin Wang, "Quantum Algorithms for Estimating Quantum Entropies", Physical Review Applied 19 4, 044041 (2023).
[14] Jason Iaconis, Sonika Johri, and Elton Yechao Zhu, "Quantum State Preparation of Normal Distributions using Matrix Product States", arXiv:2303.01562, (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 10:19:07) and SAO/NASA ADS (last updated successfully 2023-11-29 10:19:07). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.