The Efficient Preparation of Normal Distributions in Quantum Registers

Arthur G. Rattew; Yue Sun; Pierre Minssen; Marco Pistoia

doi:10.22331/q-2021-12-23-609

The Efficient Preparation of Normal Distributions in Quantum Registers

Arthur G. Rattew, Yue Sun, Pierre Minssen, and Marco Pistoia

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

The efficient preparation of input distributions is particularly important for a wide range of quantum algorithms, such as those for amplitude estimation, option pricing, principal-component analysis, matrix inversion, and machine learning. These algorithms all offer the potential for quantum advantage, notably in financial applications, so long as their initial distributions may be generated without introducing computational bottlenecks. Constructing an arbitrary quantum state necessitates exponential-depth circuits. As a result, any efficient state preparation technique must either be approximate in nature, or exploit information specific to the distribution being generated. For an algorithm to offer quantum advantage in the near future, it is even more important that state-generation procedures use as shallow circuits with as few ancillary qubits as possible, and produce high-fidelity states even in the presence of low gate-execution fidelity. 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.6\times$ 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.

► BibTeX data

@article{Rattew2021efficient,
  doi = {10.22331/q-2021-12-23-609},
  url = {https://doi.org/10.22331/q-2021-12-23-609},
  title = {The {E}fficient {P}reparation of {N}ormal {D}istributions in {Q}uantum {R}egisters},
  author = {Rattew, Arthur G. and Sun, Yue and Minssen, Pierre and Pistoia, Marco},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {609},
  month = dec,
  year = {2021}
}

► 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] Yizhou Liu, Weijie J. Su, and Tongyang Li, "On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks", Quantum 7, 1030 (2023).

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

[5] Bálint Koczor, "Exponential Error Suppression for Near-Term Quantum Devices", Physical Review X 11 3, 031057 (2021).

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

[7] Jason Iaconis, Sonika Johri, and Elton Yechao Zhu, "Quantum State Preparation of Normal Distributions using Matrix Product States", arXiv:2303.01562, (2023).

[8] Justin Yirka and Yiğit Subaşı, "Qubit-efficient entanglement spectroscopy using qubit resets", Quantum 5, 535 (2021).

[9] Youle Wang, Benchi Zhao, and Xin Wang, "Quantum algorithms for estimating quantum entropies", arXiv:2203.02386, (2022).

[10] Youle Wang, Benchi Zhao, and Xin Wang, "Quantum Algorithms for Estimating Quantum Entropies", Physical Review Applied 19 4, 044041 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-09 11:06:52) and SAO/NASA ADS (last updated successfully 2023-06-09 11:06:53). 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.