Fast Black-Box Quantum State Preparation

Johannes Bausch

Google DeepMind
CQIF, DAMTP, University of Cambridge, UK

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

Abstract

Quantum state preparation is an important ingredient for other higher-level quantum algorithms, such as Hamiltonian simulation, or for loading distributions into a quantum device to be used e.g. in the context of optimization tasks such as machine learning. Starting with a generic "black box" method devised by Grover in 2000, which employs amplitude amplification to load coefficients calculated by an oracle, there has been a long series of results and improvements with various additional conditions on the amplitudes to be loaded, culminating in Sanders et al.'s work which avoids almost all arithmetic during the preparation stage.
In this work, we construct an optimized black box state loading scheme with which various important sets of coefficients can be loaded significantly faster than in $O(\sqrt N)$ rounds of amplitude amplification, up to only $O(1)$ many. We achieve this with two variants of our algorithm. The first employs a modification of the oracle from Sanders et al., which requires fewer ancillas ($\log_2 g$ vs $g+2$ in the bit precision $g$), and fewer non-Clifford operations per amplitude amplification round within the context of our algorithm. The second utilizes the same oracle, but at slightly increased cost in terms of ancillas ($g+\log_2g$) and non-Clifford operations per amplification round. As the number of amplitude amplification rounds enters as multiplicative factor, our black box state loading scheme yields an up to exponential speedup as compared to prior methods. This speedup translates beyond the black box case.

Data loading is a crucial step for many algorithms, classical or quantum. A generic formulation of this task comprises two components, a "black box" subroutine that one can query and ask about parts of the data (for instance a specific pixel in an image), and the host routine that decides how to query the data, and takes the information it receives to prepare a state encoding the data to be loaded.
In this work, we improve upon the host routine, by significantly reducing the number of necessary queries to the black box, yielding an up to exponential speedup – naturally depending on the data to be loaded, but the results hold for a wide range of realistic datasets or distributions of interest. We further devise a specific black box subroutine, tailored to work particularly well with our host data loading scheme which further reduces the required qubit and gate overhead.

► BibTeX data

► References

[1] Lov K. Grover ``Synthesis of Quantum Superpositions by Quantum Computation'' Physical Review Letters 85, 1334-1337 (2000).
https:/​/​doi.org/​10.1103/​PhysRevLett.85.1334

[2] Yuval R. Sanders, Guang Hao Low, Artur Scherer, and Dominic W. Berry, ``Black-Box Quantum State Preparation without Arithmetic'' Physical Review Letters 122, 020502 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.122.020502

[3] 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
arXiv:0811.3171

[4] Julia Kempe ``Quantum random walks - an introductory overview'' Contemporary Physics 44, 307–327 (2003).
https:/​/​doi.org/​10.1080/​00107151031000110776
arXiv:0303081

[5] Miklos Santha ``Quantum Walk Based Search Algorithms'' Theory and Applications of Models of Computation 31–46 (2008).
https:/​/​doi.org/​10.1007/​978-3-540-79228-4_3
http:/​/​link.springer.com/​10.1007/​978-3-540-79228-4%7B%5C_%7D3

[6] Dominic W. Berryand Andrew M. Childs ``Black-box Hamiltonian simulation and unitary implementation'' (2009).
https:/​/​doi.org/​10.26421/​QIC12.1-2
arXiv:0910.4157

[7] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu, ``Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning'' ICALP 2019 (2017).
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.27
arXiv:1710.02581

[8] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang, ``Obstacles to State Preparation and Variational Optimization from Symmetry Protection'' (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.125.260505
arXiv:1910.08980

[9] Dominic W. Berry, Andrew M. Childs, and Robin Kothari, ``Hamiltonian simulation with nearly optimal dependence on all parameters'' (2015).
https:/​/​doi.org/​10.1109/​FOCS.2015.54
arXiv:1501.01715

[10] N Cody Jones, James D. Whitfield, Peter L. McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, and Yoshihisa Yamamoto, ``Faster quantum chemistry simulation on fault-tolerant quantum computers'' New Journal of Physics 14, 115023 (2012).
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​115023
arXiv:1204.0567

[11] Andrei N. Soklakovand Rüdiger Schack ``Efficient state preparation for a register of quantum bits'' Physical Review A 73, 012307 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.73.012307

[12] 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
arXiv:1003.5760

[13] Mikko Mottonen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa, ``Transformation of quantum states using uniformly controlled rotations'' Quant. Inf. Comp. 5, 467 (2004).
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0407010
arXiv:0407010

[14] Israel F. Araujo, Daniel K. Park, Francesco Petruccione, and Adenilton J. da Silva, ``A divide-and-conquer algorithm for quantum state preparation'' (2020).
https:/​/​doi.org/​10.1038/​s41598-021-85474-1
arXiv:2008.01511

[15] Lov Groverand Terry Rudolph ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002).
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0208112
arXiv:0208112

[16] Andrew M. Childs ``On the Relationship Between Continuous- and Discrete-Time Quantum Walk'' Communications in Mathematical Physics 294, 581–603 (2009).
https:/​/​doi.org/​10.1007/​s00220-009-0930-1

[17] Christa Zoufal, Aurélien Lucchi, and Stefan Woerner, ``Quantum Generative Adversarial Networks for learning and loading random distributions'' npj Quantum Information (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0223-2
arXiv:1904.00043

[18] Michael A. Nielsenand Isaac L. Chuang ``Quantum Computation and Quantum Information'' Cambridge University Press (2010).
https:/​/​doi.org/​10.1017/​CBO9780511976667
http:/​/​books.google.com/​books?id=-s4DEy7o-a0C%7B%5C&%7Dpgis=1%20http:/​/​ebooks.cambridge.org/​ref/​id/​CBO9780511976667

[19] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang, ``Fixed-Point Quantum Search with an Optimal Number of Queries'' Physical Review Letters 113, 210501 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.113.210501

[20] Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton, ``A new quantum ripple-carry addition circuit'' (2004).
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0410184
arXiv:0410184

[21] Craig Gidney ``Halving the cost of quantum addition'' Quantum 2, 74 (2018).
https:/​/​doi.org/​10.22331/​q-2018-06-18-74
arXiv:1709.06648

[22] Yong He, Ming-Xing Luo, E. Zhang, Hong-Ke Wang, and Xiao-Feng Wang, ``Decompositions of n-qubit Toffoli Gates with Linear Circuit Complexity'' International Journal of Theoretical Physics 56, 2350–2361 (2017).
https:/​/​doi.org/​10.1007/​s10773-017-3389-4

[23] John A. Smolinand David P. DiVincenzo ``Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate'' Physical Review A 53, 2855–2856 (1996).
https:/​/​doi.org/​10.1103/​PhysRevA.53.2855

[24] Quantum AI Lab Google, Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, John M. Martinis, Quantum AI Lab Google, Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis, ``Quantum supremacy using a programmable superconducting processor'' Nature 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5
http:/​/​www.nature.com/​articles/​s41586-019-1666-5

[25] Ashley Montanaro ``Quantum search with advice'' 1–14 (2009).
arXiv:0908.3066

Cited by

[1] Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa, and Mikel Sanz, "Efficient quantum amplitude encoding of polynomial functions", Quantum 8, 1297 (2024).

[2] Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe, "Hybridized Methods for Quantum Simulation in the Interaction Picture", Quantum 6, 780 (2022).

[3] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng, "Quantum Resources Required to Block-Encode a Matrix of Classical Data", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[4] Erik J. Gustafson, Henry Lamm, and Judah Unmuth-Yockey, "Quantum mean estimation for lattice field theory", Physical Review D 107 11, 114511 (2023).

[5] Jason Iaconis, Sonika Johri, and Elton Yechao Zhu, "Quantum state preparation of normal distributions using matrix product states", npj Quantum Information 10 1, 15 (2024).

[6] Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz, "Quantum algorithms for approximate function loading", Physical Review Research 5 3, 033114 (2023).

[7] Koichi Miyamoto, "Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration", Physical Review Research 5 3, 033059 (2023).

[8] Wolfgang Merkle and Regine Kalka, Stammkundenbindung versus Neukundengewinnung 149 (2023) ISBN:978-3-658-40362-1.

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

[10] Raoul Heese, Patricia Bickert, and Astrid Elisa Niederle, "Representation of binary classification trees with binary features by quantum circuits", Quantum 6, 676 (2022).

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

[12] Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda, and Naoki Yamamoto, "Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicators", Physical Review Research 4 2, 023136 (2022).

[13] Tiago M. L. de Veras, Leon D. da Silva, and Adenilton J. da Silva, "Double sparse quantum state preparation", Quantum Information Processing 21 6, 204 (2022).

[14] Weiwen Jiang, Jinjun Xiong, and Yiyu Shi, "A co-design framework of neural networks and quantum circuits towards quantum advantage", Nature Communications 12, 579 (2021).

[15] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng, "Quantum Resources Required to Block-Encode a Matrix of Classical Data", arXiv:2206.03505, (2022).

[16] Shengbin Wang, Zhimin Wang, Guolong Cui, Shangshang Shi, Ruimin Shang, Lixin Fan, Wendong Li, Zhiqiang Wei, and Yongjian Gu, "Fast black-box quantum state preparation based on linear combination of unitaries", Quantum Information Processing 20 8, 270 (2021).

[17] Shengbin Wang, Zhimin Wang, Runhong He, Shangshang Shi, Guolong Cui, Ruimin Shang, Jiayun Li, Yanan Li, Wendong Li, Zhiqiang Wei, and Yongjian Gu, "Inverse-coefficient black-box quantum state preparation", New Journal of Physics 24 10, 103004 (2022).

[18] Shengbin Wang, Zhimin Wang, Guolong Cui, Lixin Fan, Shangshang Shi, Ruimin Shang, Wendong Li, Zhiqiang Wei, and Yongjian Gu, "Quantum Amplitude Arithmetic", arXiv:2012.11056, (2020).

[19] Vladimir Vargas-Calderón, Fabio A. González, and Herbert Vinck-Posada, "Optimisation-free Classification and Density Estimation with Quantum Circuits", arXiv:2203.14452, (2022).

[20] Shengbin Wang, Zhimin Wang, Runhong He, Guolong Cui, Shangshang Shi, Ruimin Shang, Jiayun Li, Yanan Li, Wendong Li, Zhiqiang Wei, and Yongjian Gu, "Black-Box Quantum State Preparation with Inverse Coefficients", arXiv:2112.05937, (2021).

[21] Weiwen Jiang, Jinjun Xiong, and Yiyu Shi, "When Machine Learning Meets Quantum Computers: A Case Study", arXiv:2012.10360, (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-28 03:25:25) and SAO/NASA ADS (last updated successfully 2024-03-28 03:25:26). The list may be incomplete as not all publishers provide suitable and complete citation data.