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.
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] 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).
[2] 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).
[3] Vladimir Vargas-Calderón, Fabio A. González, and Herbert Vinck-Posada, “Optimisation-free Classification and Density Estimation with Quantum Circuits”, arXiv:2203.14452.
[4] Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz, “Quantum algorithms for approximate function loading”, arXiv:2111.07933.
[5] 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.
[6] 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.
[7] M. Yu Kirillin, A. V. Priezzhev, J. Hast, and Risto Myllylä, “LASER APPLICATIONS AND OTHER TOPICS IN QUANTUM ELECTRONICS: Monte Carlo simulation of optical clearing of paper in optical coherence tomography”, Quantum Electronics 36 2, 174 (2006).
[8] 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).
[9] Raoul Heese, Patricia Bickert, and Astrid Elisa Niederle, “Representation of binary classification trees with binary features by quantum circuits”, arXiv:2108.13207.
[10] Weiwen Jiang, Jinjun Xiong, and Yiyu Shi, “When Machine Learning Meets Quantum Computers: A Case Study”, arXiv:2012.10360.
[11] 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).
[12] D. A. Zimnyakov, L. V. Kuznetsova, O. V. Ushakova, and Risto Myllylä, “Special issue devoted to multiple radiation scattering in random media: On the estimate of effective optical parameters of close-packed fibrillar media”, Quantum Electronics 37 1, 9 (2007).
[13] 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.
The above citations are from SAO/NASA ADS (last updated successfully 2022-08-04 12:34:11). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2022-08-04 12:34:09: Could not fetch cited-by data for 10.22331/q-2022-08-04-773 from Crossref. This is normal if the DOI was registered recently.
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.
