{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T00:44:02Z","timestamp":1781829842839,"version":"3.54.5"},"reference-count":25,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T00:00:00Z","timestamp":1659571200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004222","name":"Pembroke College, Cambridge","doi-asserted-by":"crossref","award":["Drapers Junior Research Fellowship"],"award-info":[{"award-number":["Drapers Junior Research Fellowship"]}],"id":[{"id":"10.13039\/501100004222","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mi>(<\/mml:mo>N<\/mml:mi><\/mml:msqrt>)<\/mml:mo><\/mml:math> rounds of amplitude amplification, up to only O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:math> 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<\/mml:mi>2<\/mml:mn><\/mml:msub>&#x2061;<\/mml:mo>g<\/mml:mi><\/mml:math> vs g<\/mml:mi>+<\/mml:mo>2<\/mml:mn><\/mml:math> in the bit precision g<\/mml:mi><\/mml:math>), 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<\/mml:mi>+<\/mml:mo>log<\/mml:mi>2<\/mml:mn><\/mml:msub>&#x2061;<\/mml:mo>g<\/mml:mi><\/mml:math>) 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.<\/jats:p>","DOI":"10.22331\/q-2022-08-04-773","type":"journal-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T12:35:06Z","timestamp":1659616506000},"page":"773","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":25,"title":["Fast Black-Box Quantum State Preparation"],"prefix":"10.22331","volume":"6","author":[{"given":"Johannes","family":"Bausch","sequence":"first","affiliation":[{"name":"Google DeepMind"},{"name":"CQIF, DAMTP, University of Cambridge, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Lov K. Grover ``Synthesis of Quantum Superpositions by Quantum Computation'' Physical Review Letters 85, 1334-1337 (2000).","DOI":"10.1103\/PhysRevLett.85.1334"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.122.020502"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, ``Quantum Algorithm for Linear Systems of Equations'' Physical Review Letters 103, 150502 (2009).","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Julia Kempe ``Quantum random walks - an introductory overview'' Contemporary Physics 44, 307\u2013327 (2003).","DOI":"10.1080\/00107151031000110776"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Miklos Santha ``Quantum Walk Based Search Algorithms'' Theory and Applications of Models of Computation 31\u201346 (2008).","DOI":"10.1007\/978-3-540-79228-4_3"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Dominic W. Berryand Andrew M. Childs ``Black-box Hamiltonian simulation and unitary implementation'' (2009).","DOI":"10.26421\/QIC12.1-2"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Fernando G. S. L. Brand\u00e3o, 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).","DOI":"10.4230\/LIPIcs.ICALP.2019.27"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang, ``Obstacles to State Preparation and Variational Optimization from Symmetry Protection'' (2019).","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, and Robin Kothari, ``Hamiltonian simulation with nearly optimal dependence on all parameters'' (2015).","DOI":"10.1109\/FOCS.2015.54"},{"key":"9","doi-asserted-by":"publisher","unstructured":"N Cody Jones, James D. Whitfield, Peter L. McMahon, Man-Hong Yung, Rodney Van Meter, Al\u00e1n Aspuru-Guzik, and Yoshihisa Yamamoto, ``Faster quantum chemistry simulation on fault-tolerant quantum computers'' New Journal of Physics 14, 115023 (2012).","DOI":"10.1088\/1367-2630\/14\/11\/115023"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Andrei N. Soklakovand R\u00fcdiger Schack ``Efficient state preparation for a register of quantum bits'' Physical Review A 73, 012307 (2006).","DOI":"10.1103\/PhysRevA.73.012307"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Martin Pleschand \u010caslav Brukner ``Quantum-state preparation with universal gate decompositions'' Physical Review A 83, 032302 (2011).","DOI":"10.1103\/PhysRevA.83.032302"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.48550\/arXiv.quant-ph\/0407010"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Israel F. Araujo, Daniel K. Park, Francesco Petruccione, and Adenilton J. da Silva, ``A divide-and-conquer algorithm for quantum state preparation'' (2020).","DOI":"10.1038\/s41598-021-85474-1"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Lov Groverand Terry Rudolph ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002).","DOI":"10.48550\/arXiv.quant-ph\/0208112"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs ``On the Relationship Between Continuous- and Discrete-Time Quantum Walk'' Communications in Mathematical Physics 294, 581\u2013603 (2009).","DOI":"10.1007\/s00220-009-0930-1"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Christa Zoufal, Aur\u00e9lien Lucchi, and Stefan Woerner, ``Quantum Generative Adversarial Networks for learning and loading random distributions'' npj Quantum Information (2019).","DOI":"10.1038\/s41534-019-0223-2"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsenand Isaac L. Chuang ``Quantum Computation and Quantum Information'' Cambridge University Press (2010).","DOI":"10.1017\/CBO9780511976667"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.113.210501"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin, and David Petrie Moulton, ``A new quantum ripple-carry addition circuit'' (2004).","DOI":"10.48550\/arXiv.quant-ph\/0410184"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Craig Gidney ``Halving the cost of quantum addition'' Quantum 2, 74 (2018).","DOI":"10.22331\/q-2018-06-18-74"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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\u20132361 (2017).","DOI":"10.1007\/s10773-017-3389-4"},{"key":"22","doi-asserted-by":"publisher","unstructured":"John A. Smolinand David P. DiVincenzo ``Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate'' Physical Review A 53, 2855\u20132856 (1996).","DOI":"10.1103\/PhysRevA.53.2855"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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\u00e0, 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\u00e0, 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\u2013510 (2019).","DOI":"10.1038\/s41586-019-1666-5"},{"key":"24","unstructured":"Ashley Montanaro ``Quantum search with advice'' 1\u201314 (2009)."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-08-04-773\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T12:35:22Z","timestamp":1659616522000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-08-04-773\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,4]]},"references-count":25,"URL":"https:\/\/doi.org\/10.22331\/q-2022-08-04-773","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,4]]},"article-number":"773"}}