Spacetime-Efficient Low-Depth Quantum State Preparation With Applications

Republished By Plato

Followers: 0

Kaiwen Gui^1,2,3, Alexander M. Dalzell⁴, Alessandro Achille⁵, Martin Suchara¹, and Frederic T. Chong³

¹Amazon Web Services, WA, USA
²Pritzker School of Molecular Engineering, University of Chicago, IL, USA
³Department of Computer Science, University of Chicago, IL, USA
⁴AWS Center for Quantum Computing, Pasadena, CA, USA
⁵AWS AI Labs, Pasadena, CA, USA

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

Abstract

We propose a novel deterministic method for preparing arbitrary quantum states. When our protocol is compiled into CNOT and arbitrary single-qubit gates, it prepares an $N$-dimensional state in depth $O(log(N))$ and $textit{spacetime allocation}$ (a metric that accounts for the fact that oftentimes some ancilla qubits need not be active for the entire circuit) $O(N)$, which are both optimal. When compiled into the ${mathrm{H,S,T,CNOT}}$ gate set, we show that it requires asymptotically fewer quantum resources than previous methods. Specifically, it prepares an arbitrary state up to error $epsilon$ with optimal depth of $O(log(N) + log (1/epsilon))$ and spacetime allocation $O(Nlog(log(N)/epsilon))$, improving over $O(log(N)log(log (N)/epsilon))$ and $O(Nlog(N/epsilon))$, respectively. We illustrate how the reduced spacetime allocation of our protocol enables rapid preparation of many disjoint states with only constant-factor ancilla overhead – $O(N)$ ancilla qubits are reused efficiently to prepare a product state of $w$ $N$-dimensional states in depth $O(w + log(N))$ rather than $O(wlog(N))$, achieving effectively constant depth per state. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations. We provide quantum circuit descriptions of our protocol, detailed pseudocode, and gate-level implementation examples using Braket.

► BibTeX data

@article{Gui2024spacetimeefficient, doi = {10.22331/q-2024-02-15-1257}, url = {https://doi.org/10.22331/q-2024-02-15-1257}, title = {Spacetime-{E}fficient {L}ow-{D}epth {Q}uantum {S}tate {P}reparation with {A}pplications}, author = {Gui, Kaiwen and Dalzell, Alexander M. and Achille, Alessandro and Suchara, Martin and Chong, Frederic T.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1257}, month = feb, year = {2024}<br /> }

► References

[1] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. “Quantum machine learning”. Nature 549, 195–202 (2017).
https://doi.org/10.1038/nature23474

[2] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. “Quantum principal component analysis”. Nature Physics 10, 631–633 (2014).
https://doi.org/10.1038/nphys3029

[3] Iordanis Kerenidis and Anupam Prakash. “Quantum recommendation systems”. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21. (2017).
https://doi.org/10.4230/LIPIcs.ITCS.2017.49

[4] Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd. “Quantum singular-value decomposition of nonsparse low-rank matrices”. Physical review A 97, 012327 (2018).
https://doi.org/10.1103/PhysRevA.97.012327

[5] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. “q-means: A quantum algorithm for unsupervised machine learning”. Advances in neural information processing systems (2019).
https://proceedings.neurips.cc/paper/2019/hash/16026d60ff9b54410b3435b403afd226-Abstract.html

[6] Iordanis Kerenidis and Jonas Landman. “Quantum spectral clustering”. Physical Review A 103, 042415 (2021).
https://doi.org/10.1103/PhysRevA.103.042415

[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] Maria Schuld and Francesco Petruccione. “Machine learning with quantum computers”. Springer. (2021).
https://doi.org/10.1007/978-3-030-83098-4

[9] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. “Simulating Hamiltonian dynamics with a truncated Taylor series”. Physical review letters 114, 090502 (2015).
https://doi.org/10.1103/PhysRevLett.114.090502

[10] Dominic W Berry, Andrew M Childs, and Robin Kothari. “Hamiltonian simulation with nearly optimal dependence on all parameters”. In 2015 IEEE 56th annual symposium on foundations of computer science. Pages 792–809. IEEE (2015).
https://doi.org/10.1109/FOCS.2015.54

[11] Guang Hao Low and Isaac L Chuang. “Optimal Hamiltonian simulation by quantum signal processing”. Physical review letters 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501

[12] Guang Hao Low and Isaac L Chuang. “Hamiltonian simulation by qubitization”. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163

[13] 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

[14] Andris Ambainis. “Variable time amplitude amplification and quantum algorithms for linear algebra problems”. In STACS’12 (29th Symposium on Theoretical Aspects of Computer Science). Volume 14, pages 636–647. LIPIcs (2012).
https://doi.org/10.4230/LIPIcs.STACS.2012.636

[15] Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. “Quantum linear system algorithm for dense matrices”. Physical review letters 120, 050502 (2018).
https://doi.org/10.1103/PhysRevLett.120.050502

[16] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. “Trading T-gates for dirty qubits in state preparation and unitary synthesis”. arXiv.1812.00954 (2018).
https://doi.org/10.48550/arXiv.1812.00954

[17] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. “Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2023).
https://doi.org/10.1109/TCAD.2023.3244885

[18] Pei Yuan and Shengyu Zhang. “Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits”. Quantum 7, 956 (2023).
https://doi.org/10.22331/q-2023-03-20-956

[19] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. “Quantum state preparation with optimal circuit depth: Implementations and applications”. Physical Review Letters 129, 230504 (2022).
https://doi.org/10.1103/PhysRevLett.129.230504

[20] 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 (2023).
https://doi.org/10.1109/TQE.2022.3231194

[21] Gregory Rosenthal. “Query and depth upper bounds for quantum unitaries via grover search”. arXiv.2111.07992 (2021).
https://doi.org/10.48550/arXiv.2111.07992

[22] Neil J. Ross and Peter Selinger. “Optimal ancilla-free Clifford+T approximation of z-rotations”. Quantum Info. Comput. (2016).
https://dl.acm.org/doi/10.5555/3179330.3179331

[23] Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. “Encoding electronic spectra in quantum circuits with linear T complexity”. Physical Review X 8, 041015 (2018).
https://doi.org/10.1103/PhysRevX.8.041015

[24] Israel F Araujo, Daniel K Park, Francesco Petruccione, and Adenilton J da Silva. “A divide-and-conquer algorithm for quantum state preparation”. Scientific reports 11, 1–12 (2021).
https://doi.org/10.1038/s41598-021-85474-1

[25] Vivek V. Shende and Igor L. Markov. “On the CNOT-cost of TOFFOLI gates”. Quantum Info. Comput. (2009).
https://dl.acm.org/doi/10.5555/2011791.2011799

[26] John A Smolin and David P DiVincenzo. “Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate”. Physical Review A 53, 2855 (1996).
https://doi.org/10.1103/PhysRevA.53.2855

[27] Edward Walker. “The real cost of a CPU hour”. Computer 42, 35–41 (2009).
https://doi.org/10.1109/MC.2009.135

[28] Yongshan Ding, Xin-Chuan Wu, Adam Holmes, Ash Wiseth, Diana Franklin, Margaret Martonosi, and Frederic T Chong. “Square: Strategic quantum ancilla reuse for modular quantum programs via cost-effective uncomputation”. In 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). Pages 570–583. IEEE (2020).
https://doi.org/10.1109/ISCA45697.2020.00054

[29] Martin Plesch and Časlav Brukner. “Quantum-state preparation with universal gate decompositions”. Phys. Rev. A 83, 032302 (2011).
https://doi.org/10.1103/PhysRevA.83.032302

[30] Xiao-Ming Zhang and Xiao Yuan. “On circuit complexity of quantum access models for encoding classical data”. arXiv.2311.11365 (2023).
https://doi.org/10.48550/arXiv.2311.11365

[31] Michael A Nielsen and Isaac Chuang. “Quantum computation and quantum information”. American Association of Physics Teachers. (2002).
https://doi.org/10.1017/CBO9780511976667

[32] Sebastian Ruder. “An overview of gradient descent optimization algorithms”. arXiv.1609.04747 (2016).
https://doi.org/10.48550/arXiv.1609.04747

[33] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross, and Yuan Su. “Toward the first quantum simulation with quantum speedup”. Proceedings of the National Academy of Sciences 115, 9456–9461 (2018).
https://doi.org/10.1073/pnas.1801723115

[34] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. “The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation”. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP). Pages 33:1–33:14. (2019).
https://doi.org/10.4230/LIPIcs.ICALP.2019.33

[35] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics”. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC). Pages 193–204. (2019).
https://doi.org/10.1145/3313276.3316366

[36] Trygve Helgaker, Poul Jorgensen, and Jeppe Olsen. “Molecular electronic-structure theory”. John Wiley & Sons. (2013).
https://doi.org/10.1002/9781119019572

[37] Mario Motta, Tanvi P Gujarati, Julia E Rice, Ashutosh Kumar, Conner Masteran, Joseph A Latone, Eunseok Lee, Edward F Valeev, and Tyler Y Takeshita. “Quantum simulation of electronic structure with a transcorrelated Hamiltonian: improved accuracy with a smaller footprint on the quantum computer”. Physical Chemistry Chemical Physics 22, 24270–24281 (2020).
https://doi.org/10.1039/D0CP04106H

[38] Sam McArdle and David P Tew. “Improving the accuracy of quantum computational chemistry using the transcorrelated method”. arXiv.2006.11181 (2020).
https://doi.org/10.48550/arXiv.2006.11181

[39] Sebastien Bubeck, Sitan Chen, and Jerry Li. “Entanglement is necessary for optimal quantum property testing”. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Pages 692–703. IEEE (2020).
https://doi.org/10.1109/FOCS46700.2020.00070

[40] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. “Exponential separations between learning with and without quantum memory”. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Pages 574–585. IEEE (2022).
https://doi.org/10.1109/FOCS52979.2021.00063

[41] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. “Quantum advantage in learning from experiments”. Science 376, 1182–1186 (2022).
https://doi.org/10.1126/science.abn7293

[42] Jonathan Richard Shewchuk et al. “An introduction to the conjugate gradient method without the agonizing pain”. 1994 Technical Report (1994).
https://dl.acm.org/doi/10.5555/865018

[43] Ashley Montanaro and Sam Pallister. “Quantum algorithms and the finite element method”. Physical Review A 93, 032324 (2016).
https://doi.org/10.1103/PhysRevA.93.032324

[44] Ashley Montanaro and Changpeng Shao. “Quantum communication complexity of linear regression”. ACM Trans. Comput. Theory (2023).
https://doi.org/10.1145/3625225

[45] Yiğit Subaşi, Rolando D. Somma, and Davide Orsucci. “Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing”. Phys. Rev. Lett. 122, 060504 (2019).
https://doi.org/10.1103/PhysRevLett.122.060504

[46] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush, and Dominic W Berry. “Optimal scaling quantum linear-systems solver via discrete adiabatic theorem”. PRX Quantum 3, 040303 (2022).
https://doi.org/10.1103/PRXQuantum.3.040303

[47] John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. “Grand unification of quantum algorithms”. PRX Quantum 2, 040203 (2021).
https://doi.org/10.1017/CBO9780511976667

[48] Craig Gidney. “Quirk: A drag-and-drop quantum circuit simulator”. https://algassert.com/quirk (2016).
https://algassert.com/quirk

[49] Alexander M Dalzell, B David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A Bader, Nikitas Stamatopoulos, Martin JA Schuetz, Fernando GSL Brandão, Helmut G Katzgraber, et al. “End-to-end resource analysis for quantum interior-point methods and portfolio optimization”. PRX Quantum 4, 040325 (2023).
https://doi.org/10.1103/PRXQuantum.4.040325

Cited by

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

[2] Raghav Jumade and Nicolas PD Sawaya, “Data is often loadable in short depth: Quantum circuits from tensor networks for finance, images, fluids, and proteins”, arXiv:2309.13108, (2023).

[3] Gideon Lee, Connor T. Hann, Shruti Puri, S. M. Girvin, and Liang Jiang, “Error Suppression for Arbitrary-Size Black Box Quantum Operations”, Physical Review Letters 131 19, 190601 (2023).

[4] Gregory Rosenthal, “Efficient Quantum State Synthesis with One Query”, arXiv:2306.01723, (2023).

[5] Xiao-Ming Zhang and Xiao Yuan, “On circuit complexity of quantum access models for encoding classical data”, arXiv:2311.11365, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2024-02-15 15:17: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 2024-02-15 15:17:09: Could not fetch cited-by data for 10.22331/q-2024-02-15-1257 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.