Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
1Amazon Web Services, WA, USA
2Pritzker School of Molecular Engineering, University of Chicago, IL, USA
3Department of Computer Science, University of Chicago, IL, USA
4AWS Center for Quantum Computing, Pasadena, CA, USA
5AWS AI Labs, Pasadena, CA, USA
| Published: | 2024-02-15, volume 8, page 1257 |
| Eprint: | arXiv:2303.02131v3 |
| Doi: | https://doi.org/10.22331/q-2024-02-15-1257 |
| Citation: | Quantum 8, 1257 (2024). |
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(N\log(\log(N)/\epsilon))$, improving over $O(\log(N)\log(\log (N)/\epsilon))$ and $O(N\log(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(w\log(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
► 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] Hang Zou, Erika Magnusson, Hampus Brunander, Werner Dobrautz, and Martin Rahm, "Multireference error mitigation for quantum computation of chemistry", Digital Discovery 4 9, 2521 (2025).
[2] Orson Ye and Sergii Strelchuk, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 631 (2024) ISBN:979-8-3315-4137-8.
[3] Zhaoyuan Meng, Jiarun Zhong, Shibo Xu, Ke Wang, Jiachen Chen, Feitong Jin, Xuhao Zhu, Yu Gao, Yaozu Wu, Chuanyu Zhang, Ning Wang, Yiren Zou, Aosai Zhang, Zhengyi Cui, Fanhao Shen, Zehang Bao, Zitian Zhu, Ziqi Tan, Tingting Li, Pengfei Zhang, Shiying Xiong, Hekang Li, Qiujiang Guo, Zhen Wang, Chao Song, H. Wang, and Yue Yang, "Simulating unsteady flows on a superconducting quantum processor", Communications Physics 7 1, 349 (2024).
[4] Riccardo Pellini and Maurizio Ferrari Dacrema, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 276 (2025) ISBN:979-8-3315-5736-2.
[5] Xiao-Ming Zhang and Xiao Yuan, "Circuit complexity of quantum access models for encoding classical data", npj Quantum Information 10 1, 42 (2024).
[6] Erik J. Gustafson, Yao Ji, Henry Lamm, Edison M. Murairi, Sebastian Osorio Perez, and Shuchen Zhu, "Primitive quantum gates for an SU(3) discrete subgroup: Σ(36×3)", Physical Review D 110 3, 034515 (2024).
[7] José Alex de Carvalho, Carlos Batista, Tiago de Veras, Israel Araujo, and Adenilton José da Silva, "Quantum Multiplexer Simplification for State Preparation", ACM Transactions on Quantum Computing 6 4, 1 (2025).
[8] Alvin Gonzales, Rebekah Herrman, Colin Campbell, Igor Gaidai, Ji Liu, Teague Tomesh, and Zain H. Saleem, "Efficient sparse state preparation via quantum walks", npj Quantum Information 11 1, 143 (2025).
[9] Adarsh Kumar, Ali Ismail Awad, Gaurav Sharma, Rajalakshmi Krishnamurthi, Saurabh Jain, P. Srikanth, Kriti Sharma, Mustapha Hedabou, and Surinder Sood, "Artificial intelligence and blockchain for quantum satellites and UAV-based communications: a review", Quantum Machine Intelligence 7 1, 45 (2025).
[10] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer, "Trading T gates for dirty qubits in state preparation and unitary synthesis", Quantum 8, 1375 (2024).
[11] Xiao-Ming Zhang, "Robust and Optimal Loading of General Classical Data Into Quantum Computers", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 45 3, 1170 (2026).
[12] Kasra Rajabzadeh Dizaji, Ariq Haqq, Alicia B Magann, and Christian Arenz, "Hamiltonian simulation in Zeno subspaces", Physica Scripta 101 25, 255106 (2026).
[13] Josh Green and Jingbo Wang, "Quantum encoding of functions and images with matrix product states", Physical Review A 113 5, 052616 (2026).
[14] Patrick Selig, Niall Murphy, David Redmond, and Simon Caton, "On the Challenges of Quantum Circuit Encoding Using Deep and Reinforcement Learning", IEEE Access 13, 75220 (2025).
[15] Giacomo Belli and Michele Amoretti, Lecture Notes in Computer Science 16626, 77 (2026) ISBN:978-3-032-30838-2.
[16] 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).
[17] 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).
[18] 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).
[19] Xi-Ning Zhuang, Zhao-Yun Chen, Ming-Yang Tan, Jiaxuan Zhang, Chuang-Chao Ye, Tian-Hao Wei, Teng-Yang Ma, Cheng Xue, Huan-Yu Liu, Qing-Song Li, Tai-Ping Sun, Xiao-Fan Xu, Yun-Jie Wang, Yu-Chun Wu, and Guo-Ping Guo, "A Pathway to Practical Quantum Advantage in Solving Navier-Stokes Equations", arXiv:2509.08807, (2025).
[20] Gregory Rosenthal, "Efficient Quantum State Synthesis with One Query", arXiv:2306.01723, (2023).
[21] Jielun Chen and Garnet Kin-Lic Chan, "A framework for robust quantum speedups in practical correlated electronic structure and dynamics", arXiv:2508.15765, (2025).
[22] Sebastian Osorio Perez, Edison M. Murairi, Erik J. Gustafson, and Henry Lamm, "Primitive Quantum Gates for an $SU(3)$ Discrete Subgroup: $Σ(72\times3)$", arXiv:2511.17437, (2025).
[23] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", arXiv:2504.05624, (2025).
[24] Vu Tuan Hai, Nguyen Tan Viet, and Le Bin Ho, "<mml:math altimg="si26.svg" display="inline" id="d1e1792"><mml:mrow><mml:mo>〈</mml:mo><mml:mi mathvariant="normal">qo</mml:mi><mml:mo>|</mml:mo><mml:mi mathvariant="normal">op</mml:mi><mml:mo>〉</mml:mo></mml:mrow></mml:math>: A quantum object optimizer", SoftwareX 26, 101726 (2024).
[25] Sunil Vittal, Anthony Wilkie, Nika Rastegari, Mostafa Atallah, and Rebekah Herrman, "Efficient circuits for leaf-separable state preparation", arXiv:2511.11227, (2025).
[26] Ben Foxman, Barak Nehoran, and Yongshan Ding, "Efficient Quantum Fourier Transforms For Semisimple Algebras", arXiv:2605.05337, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-11 22:24:18) and SAO/NASA ADS (last updated successfully 2026-08-11 22:24:22). 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.