Fast Black-Box Quantum State Preparation
Google DeepMind
CQIF, DAMTP, University of Cambridge, UK
| Published: | 2022-08-04, volume 6, page 773 |
| Eprint: | arXiv:2009.10709v4 |
| Doi: | https://doi.org/10.22331/q-2022-08-04-773 |
| Citation: | Quantum 6, 773 (2022). |
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.
Popular summary
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] Sam McArdle, András Gilyén, and Mario Berta, "Quantum State Preparation without Coherent Arithmetic", Physical Review Letters 136 24, 240603 (2026).
[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] Sivarama Prasad Tera, Ravikumar Chinthaginjala, Xin Zhao, and Monia Hamdi, "Advancing quantum machine learning from conceptual design to practical use", Expert Systems with Applications 320, 132127 (2026).
[5] Steven Herbert, Ifan Williams, Roland Guichard, and Darren Ng, "Noise-Aware Quantum Amplitude Estimation", IEEE Transactions on Quantum Engineering 5, 1 (2024).
[6] Erik J. Gustafson, Henry Lamm, and Judah Unmuth-Yockey, "Quantum mean estimation for lattice field theory", Physical Review D 107 11, 114511 (2023).
[7] Nozomu Kobayashi, Yoshiyuki Suimon, and Koichi Miyamoto, "Time series generation for option pricing on quantum computers using tensor network", Quantum Machine Intelligence 8 1, 39 (2026).
[8] Jonathan Allcock, Jinge Bao, Joao F. Doriguello, Alessandro Luongo, and Miklos Santha, "Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates", Quantum 8, 1530 (2024).
[9] Matthias Rosenkranz, Eric Brunner, Gabriel Marin-Sanchez, Nathan Fitzpatrick, Silas Dilkes, Yao Tang, Yuta Kikuchi, and Marcello Benedetti, "Quantum state preparation for multivariate functions", Quantum 9, 1703 (2025).
[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] Guoming Wang and Angus Kan, "Option pricing under stochastic volatility on a quantum computer", Quantum 8, 1504 (2024).
[12] Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe, "Hybridized Methods for Quantum Simulation in the Interaction Picture", Quantum 6, 780 (2022).
[13] Ifan Williams and Mathieu Pellen, "A general approach to quantum integration of cross sections in high-energy physics", Quantum Science and Technology 10 4, 045017 (2025).
[14] 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).
[15] Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz, "Quantum algorithms for approximate function loading", Physical Review Research 5 3, 033114 (2023).
[16] Nicolas Parra-A, Vladimir Vargas-Calderón, and Herbert Vinck-Posada, "Arbitrary state preparation in quantum harmonic oscillators using neural networks", Results in Physics 87, 108721 (2026).
[17] Kumar Ghosh, Kavitha Yogaraj, Gabriele Agliardi, Piergiacomo Sabino, Marina Fernández-Campoamor, Juan Bernabé-Moreno, Giorgio Cortiana, Omar Shehab, and Corey O'Meara, "Energy Risk Analysis With Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling", IEEE Transactions on Quantum Engineering 5, 1 (2024).
[18] Wolfgang Merkle and Regine Kalka, Stammkundenbindung versus Neukundengewinnung 149 (2023) ISBN:978-3-658-40362-1.
[19] Matias Ginzburg and Ugo Marzolino, "Error convergence of quantum linear system solvers", Physical Review A 113 6, 062436 (2026).
[20] Yu Tanaka, Hayata Yamasaki, and Mio Murao, "Quantum state preparation via free binary decision diagram", Journal of Physics A: Mathematical and Theoretical 59 26, 265302 (2026).
[21] Xiang-Qun 向群 Fu 付, Tian-Ci 天赐 Tian 田, Hong-Wei 宏伟 Li 李, Jian-Hong 建红 Shi 史, Xiao-Liang 晓亮 Yang 杨, Tan 坦 Li 李, and Wan-Su 皖苏 Bao 鲍, "Efficient fault-tolerant circuit for preparing quantum uniform superposition states via quantum measurement", Chinese Physics B 34 12, 120303 (2025).
[22] Abhishek Arora, Benjamin M. Ward, and Caglar Oskay, "An implementation of the finite element method in hybrid classical/quantum computers", Finite Elements in Analysis and Design 248, 104354 (2025).
[23] Koichi Miyamoto, "Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration", Physical Review Research 5 3, 033059 (2023).
[24] Josh Green and Jingbo Wang, "Quantum encoding of functions and images with matrix product states", Physical Review A 113 5, 052616 (2026).
[25] Oliver O'Brien and Christoph Sünderhauf, "Quantum state preparation via piecewise QSVT", Quantum 9, 1786 (2025).
[26] 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).
[27] Ge Lin, Zhengming Guo, and Tingting Song, "Power Law Amplitude Estimation for Option Pricing with NISQ Devices", Advanced Quantum Technologies 8 6, 2400411 (2025).
[28] 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).
[29] 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).
[30] Lvzhou Li and Jingquan Luo, "Nearly Optimal Circuit Size for Sparse Quantum State Preparation", arXiv:2406.16142, (2024).
[31] 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).
[32] 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).
[33] 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).
[34] Junpeng Zhan, "Variational Quantum Search with Shallow Depth for Unstructured Database Search", arXiv:2212.09505, (2022).
[35] Jingjing Cui, Philippe J. S. de Brouwer, Steven Herbert, Philip Intallura, Cahit Kargi, Georgios Korpas, Alexandre Krajenbrink, William Shoosmith, Ifan Williams, and Ban Zheng, "Quantum Monte Carlo Integration for Simulation-Based Optimisation", arXiv:2410.03926, (2024).
[36] Abhishek Arora, Benjamin M. Ward, and Caglar Oskay, "An Implementation of the Finite Element Method in Hybrid Classical/Quantum Computers", arXiv:2411.09038, (2024).
[37] 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).
[38] 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).
[39] 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).
[40] 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 2026-08-07 12:40:00) and SAO/NASA ADS (last updated successfully 2026-08-07 12:40:02). 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.