Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
Tencent Quantum Laboratory, Tencent, Shenzhen, Guangdong 518057, China
| Published: | 2023-03-20, volume 7, page 956 |
| Eprint: | arXiv:2202.11302v2 |
| Doi: | https://doi.org/10.22331/q-2023-03-20-956 |
| Citation: | Quantum 7, 956 (2023). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
As a cornerstone for many quantum linear algebraic and quantum machine learning algorithms, controlled quantum state preparation (CQSP) aims to provide the transformation of $|i\rangle |0^n\rangle \to |i\rangle |\psi_i\rangle $ for all $i\in \{0,1\}^k$ for the given $n$-qubit states $|\psi_i\rangle$. In this paper, we construct a quantum circuit for implementing CQSP, with depth $O\left(n+k+\frac{2^{n+k}}{n+k+m}\right)$ and size $O(2^{n+k})$ for any given number $m$ of ancillary qubits. These bounds, which can also be viewed as a time-space tradeoff for the transformation, are optimal for any integer parameters $m,k\ge 0$ and $n\ge 1$. When $k=0$, the problem becomes the canonical quantum state preparation (QSP) problem with ancillary qubits, which asks for efficient implementations of the transformation $|0^n\rangle|0^m\rangle \to |\psi\rangle |0^m\rangle$. This problem has many applications with many investigations, yet its circuit complexity remains open. Our construction completely solves this problem, pinning down its depth complexity to $\Theta(n+2^{n}/(n+m))$ and its size complexity to $\Theta(2^{n})$ for any $m$. Another fundamental problem, unitary synthesis, asks to implement a general $n$-qubit unitary by a quantum circuit. Previous work shows a lower bound of $\Omega(n+4^n/(n+m))$ and an upper bound of $O(n2^n)$ for $m=\Omega(2^n/n)$ ancillary qubits. In this paper, we quadratically shrink this gap by presenting a quantum circuit of the depth of $O\left(n2^{n/2}+\frac{n^{1/2}2^{3n/2}}{m^{1/2}}~~\right)$.
► 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 Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21. Dagstuhl, Germany (2017). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
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''. Phys. Rev. A 97, 012327 (2018).
https://doi.org/10.1103/PhysRevA.97.012327
[5] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Phys. Rev. Lett. 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502
[6] Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. ``Quantum linear system algorithm for dense matrices''. Phys. Rev. Lett. 120, 050502 (2018).
https://doi.org/10.1103/PhysRevLett.120.050502
[7] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. ``q-means: a quantum algorithm for unsupervised machine learning''. In Advances in Neural Information Processing Systems. Volume 32, pages 4134–4144. (2019).
https://doi.org/10.48550/arXiv.1812.03584
[8] Iordanis Kerenidis and Jonas Landman. ``Quantum spectral clustering''. Phys. Rev. A 103, 042415 (2021).
https://doi.org/10.1103/PhysRevA.103.042415
[9] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. ``Quantum support vector machine for big data classification''. Phys. Rev. Lett. 113, 130503 (2014).
https://doi.org/10.1103/PhysRevLett.113.130503
[10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. ``Simulating hamiltonian dynamics with a truncated taylor series''. Phys. Rev. Lett. 114, 090502 (2015).
https://doi.org/10.1103/PhysRevLett.114.090502
[11] Guang Hao Low and Isaac L. Chuang. ``Optimal hamiltonian simulation by quantum signal processing''. Phys. Rev. Lett. 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] 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. (2015).
https://doi.org/10.1109/FOCS.2015.54
[14] Mario Szegedy. ``Quantum speed-up of markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004).
https://doi.org/10.1109/FOCS.2004.53
[15] Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. ``Search via quantum walk''. SIAM Journal on Computing 40, 142–164 (2011).
https://doi.org/10.1137/090745854
[16] Daniel K. Park, Francesco Petruccione, and June-Koo Kevin Rhee. ``Circuit-based quantum random access memory for classical data''. Scientific Reports 9, 3949 (2019).
https://doi.org/10.1038/s41598-019-40439-3
[17] Tiago M. L. de Veras, Ismael C. S. de Araujo, Daniel K. Park, and Adenilton J. da Silva. ``Circuit-based quantum random access memory for classical data with continuous amplitudes''. IEEE Transactions on Computers 70, 2125–2135 (2021).
https://doi.org/10.1109/TC.2020.3037932
[18] Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca. ``Fault-tolerant resource estimation of quantum random-access memories''. IEEE Transactions on Quantum Engineering 1, 1–13 (2020).
https://doi.org/10.1109/TQE.2020.2965803
[19] Ville Bergholm, Juha J. Vartiainen, Mikko Möttönen, and Martti M. Salomaa. ``Quantum circuits with uniformly controlled one-qubit gates''. Phys. Rev. A 71, 052330 (2005).
https://doi.org/10.1103/PhysRevA.71.052330
[20] 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
[21] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. ``Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis'' (2021) arXiv:2108.06150v3.
arXiv:2108.06150v3
[22] Xiao-Ming Zhang, Man-Hong Yung, and Xiao Yuan. ``Low-depth quantum state preparation''. Phys. Rev. Res. 3, 043200 (2021).
https://doi.org/10.1103/PhysRevResearch.3.043200
[23] Gregory Rosenthal. ``Query and depth upper bounds for quantum unitaries via grover search'' (2021). arXiv:2111.07992.
arXiv:2111.07992
[24] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. ``Quantum state preparation with optimal circuit depth: Implementations and applications''. Phys. Rev. Lett. 129, 230504 (2022).
https://doi.org/10.1103/PhysRevLett.129.230504
[25] Sonika Johri, Shantanu Debnath, Avinash Mocherla, Alexandros SINGK, Anupam Prakash, Jungsang Kim, and Iordanis Kerenidis. ``Nearest centroid classification on a trapped ion quantum computer''. npj Quantum Information 7, 122 (2021).
https://doi.org/10.1038/s41534-021-00456-5
[26] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying. ``Parallel quantum algorithm for hamiltonian simulation'' (2021). arXiv:2105.11889.
arXiv:2105.11889
[27] Vivek V. Shende, Igor L. Markov, and Stephen S. Bullock. ``Minimal universal two-qubit controlled-not-based circuits''. Phys. Rev. A 69, 062321 (2004).
https://doi.org/10.1103/PhysRevA.69.062321
[28] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. ``Elementary gates for quantum computation''. Phys. Rev. A 52, 3457–3467 (1995).
https://doi.org/10.1103/PhysRevA.52.3457
[29] Emanuel Knill. ``Approximation by quantum circuits'' (1995). arXiv:quant-ph/9508006.
arXiv:quant-ph/9508006
[30] Juha J. Vartiainen, Mikko Möttönen, and Martti M. Salomaa. ``Efficient decomposition of quantum gates''. Phys. Rev. Lett. 92, 177902 (2004).
https://doi.org/10.1103/PhysRevLett.92.177902
[31] M Mottonen and Juha J Vartiainen. ``Decompositions of general quantum gates'' (2005). arXiv:quant-ph/0504100.
arXiv:quant-ph/0504100
[32] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum random access memory''. Phys. Rev. Lett. 100, 160501 (2008).
https://doi.org/10.1103/PhysRevLett.100.160501
[33] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Architectures for a quantum random access memory''. Phys. Rev. A 78, 052310 (2008).
https://doi.org/10.1103/PhysRevA.78.052310
[34] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667
[35] Craig Gidney. ``Using quantum gates instead of ancilla bits''. https://algassert.com/circuits/2015/06/22/Using-Quantum-Gates-instead-of-Ancilla-Bits.html.
https://algassert.com/circuits/2015/06/22/Using-Quantum-Gates-instead-of-Ancilla-Bits.html
[36] Jonathan M Baker, Casey Duckering, Alexander Hoover, and Frederic T Chong. ``Decomposing quantum generalized toffoli with an arbitrary number of ancilla'' (2019). arXiv:1904.01671.
arXiv:1904.01671
[37] Lov Grover and Terry Rudolph. ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002). arXiv:quant-ph/0208112.
arXiv:quant-ph/0208112
[38] C.C. Paige and M. Wei. ``History and generality of the cs decomposition''. Linear Algebra and its Applications 208-209, 303–326 (1994).
https://doi.org/10.1016/0024-3795(94)90446-4
[39] Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. ``Trading t-gates for dirty qubits in state preparation and unitary synthesis'' (2018). arXiv:1812.00954.
arXiv:1812.00954
Cited by
[1] Julien Zylberman, Thibault Fredon, Nuno F Loureiro, and Fabrice Debbasch, "Trotter-based quantum algorithm for solving transport equations with exponentially fewer time-steps", Quantum Science and Technology 11 2, 025015 (2026).
[2] Aaron Szasz, Ed Younis, and Wibe De Jong, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 768 (2023) ISBN:979-8-3503-4323-6.
[3] Kasra Rajabzadeh Dizaji, Ariq Haqq, Alicia B Magann, and Christian Arenz, "Hamiltonian simulation in Zeno subspaces", Physica Scripta 101 25, 255106 (2026).
[4] Wei-Wei Zhang, Xiaopeng Huang, Shenglin Shan, Wei Zhao, Beiya Yang, Wei Pan, and Haobin Shi, "Quantum data generation in a denoising model with multiscale entanglement renormalization network", Physica Scripta 100 6, 065120 (2025).
[5] Julien Zylberman, Thibault Fredon, Nuno F. Loureiro, and Fabrice Debbasch, Communications in Computer and Information Science 2744, 255 (2026) ISBN:978-3-032-13854-5.
[6] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", IEEE Transactions on Quantum Engineering 7, 1 (2026).
[7] S. Malikis and V. Cheianov, "Integrability and chaos in the quantum brachistochrone problem", Physical Review A 110 2, 022205 (2024).
[8] Simon Apers and Sander Gribling, "Quantum Speedups for Linear Programming via Interior Point Methods", SIAM Journal on Computing 55 1, 93 (2026).
[9] Gregory Rosenthal, "Query and Depth Upper Bounds for Quantum Unitaries via Grover Search", Quantum 10, 2144 (2026).
[10] Carla Rieger, Michele Grossi, Gian Giacomo Guerreschi, Sofia Vallecorsa, and Martin Werner, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 259 (2025) ISBN:979-8-3315-5736-2.
[11] Qingwen Wang, Ying Jiang, Shiguang Feng, and Lvzhou Li, "Unifying quantum spatial search, state transfer, and uniform sampling on graphs", Physical Review A 111 4, 042608 (2025).
[12] Yuan-De Jin, Shi-Yu Zhang, Ulrik L. Andersen, and Wen-Long Ma, "General Approach to Error Detection of Bosonic Codes via Phase Estimation", Physical Review Letters 135 14, 140603 (2025).
[13] Alexander I. Zenchuk, Wentao Qi, and Junde Wu, "Arbitrary State Creation via Controlled Measurement", Quantum Information & Computation 26 1, 114 (2026).
[14] Samuel Jaques and Arthur G. Rattew, "QRAM: A Survey and Critique", Quantum 9, 1922 (2025).
[15] Yen-Jui Chang, Wei-Ting Wang, Hao-Yuan Chen, Shih-Wei Liao, and Ching-Ray Chang, "A novel approach for quantum financial simulation and quantum state preparation", Quantum Machine Intelligence 6 1, 24 (2024).
[16] Qisheng Wang and Zhicheng Zhang, "Tight quantum depth lower bound for solving systems of linear equations", Physical Review A 110 1, 012422 (2024).
[17] Yen Jui Chang, Wei-Ting Wang, Chen-Yu Liu, Yun-Yuan Wang, and Ching-Ray Chang, "Quantum walks–based adaptive distribution generation with efficient CUDA-Q acceleration", Quantum Machine Intelligence 8 1, 42 (2026).
[18] Pei Yuan, Jonathan Allcock, and Shengyu Zhang, "Does Qubit Connectivity Impact Quantum Circuit Complexity?", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 43 2, 520 (2024).
[19] Lucas Friedrich, Douglas F. Pinto, Diego S. Starke, and Jonas Maziero, "Preparing general mixed quantum states on quantum computers", Quantum Information Processing 25 9, 283 (2026).
[20] 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).
[21] Yu Wang, Meng Li, and Yuan-Yuan Zhao, "Determinate arbitrary quantum state engineering through one-dimensional quantum walks", Physical Review Research 7 2, 023252 (2025).
[22] Anton S. Albino, Lucas Q. Galvão, Mauro Q. Nooblath Neto, Ethan Hansen, and Clebson Cruz, "Quantum Algorithm for Finding Minimum Values in a Quantum Random Access Memory", Brazilian Journal of Physics 55 6, 284 (2025).
[23] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).
[24] Yi Hu, Congcong Zheng, Xiaojun Wang, Fanxu Meng, Xutao Yu, and Zaichen Zhang, "Suppressing quantum errors by noise-aware circuit design", Quantum Science and Technology 10 4, 045040 (2025).
[25] Giacomo Belli, Andrea Bersellini, and Michele Amoretti, Lecture Notes in Computer Science 15716, 37 (2025) ISBN:978-3-031-97062-7.
[26] 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).
[27] Xiao-Ming Zhang and Xiao Yuan, "Circuit complexity of quantum access models for encoding classical data", npj Quantum Information 10 1, 42 (2024).
[28] 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).
[29] Qisheng Wang, "Optimal Trace Distance and Fidelity Estimations for Pure Quantum States", IEEE Transactions on Information Theory 70 12, 8791 (2024).
[30] Zhicheng Zhang and Mingsheng Ying, "Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs", Proceedings of the ACM on Programming Languages 9 PLDI, 822 (2025).
[31] Jianling Fu, Ming Xu, Haifeng Qian, and Zhibin Li, "Theoretical and Experimental Performance Analysis on Error-Bounded Quantum Search Process", Journal of Systems Science and Complexity 39 3, 1331 (2026).
[32] Chunlin Yang, Zexian Li, Hongmei Yao, Zhaobing Fan, Guofeng Zhang, and Jianshe Liu, "Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth", Quantum 9, 1805 (2025).
[33] Kaiwen Gui, Alexander M. Dalzell, Alessandro Achille, Martin Suchara, and Frederic T. Chong, "Spacetime-Efficient Low-Depth Quantum State Preparation with Applications", Quantum 8, 1257 (2024).
[34] Yongchun Xu and Heng Hu, "Potential energy minimization for structural analysis via decomposition-free quantum computing", Computers & Structures 330, 108309 (2026).
[35] Yukun Zhang, Xiaoming Zhang, Jinzhao Sun, Heng Lin, Yifei Huang, Dingshun Lv, and Xiao Yuan, "Quantum Algorithms for Quantum Molecular Systems: A Survey", WIREs Computational Molecular Science 15 3, e70020 (2025).
[36] Xiaowei Huang, Fei Shi, Lijun Zhang, and Lvzhou Li, "Quantum states supported by matroids", Physical Review A 113 6, 062452 (2026).
[37] 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).
[38] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan, "Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications", Physical Review Letters 129 23, 230504 (2022).
[39] 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 42 10, 3301 (2023).
[40] Gregory Boyd, "Low-Overhead Parallelisation of LCU via Commuting Operators", arXiv:2312.00696, (2023).
[41] Yen-Jui Chang, Wei-Ting Wang, Hao-Yuan Chen, Shih-Wei Liao, and Ching-Ray Chang, "A novel approach for quantum financial simulation and quantum state preparation", arXiv:2308.01844, (2023).
[42] Qisheng Wang, "Optimal Trace Distance and Fidelity Estimations for Pure Quantum States", arXiv:2408.16655, (2024).
[43] Gregory Rosenthal, "Efficient Quantum State Synthesis with One Query", arXiv:2306.01723, (2023).
[44] Zhicheng Zhang and Mingsheng Ying, "Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs", arXiv:2408.10054, (2024).
[45] Bojia Duan and Chang-Yu Hsieh, "Hamiltonian-based data loading with shallow quantum circuits", Physical Review A 106 5, 052422 (2022).
[46] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", arXiv:2504.05624, (2025).
[47] SeungYeop Baik, Sicheol Sung, and Yo-Sub Han, "A Framework for Quantum Finite-State Languages with Density Mapping", arXiv:2407.02776, (2024).
[48] Yen-Jui Chang, Wei-Ting Wang, Chen-Yu Liu, Yun-Yuan Wang, and Ching-Ray Chang, "Quantum Walks-Based Adaptive Distribution Generation with Efficient CUDA-Q Acceleration", arXiv:2504.13532, (2025).
[49] Aaron Szasz, Ed Younis, and Wibe de Jong, "Numerical circuit synthesis and compilation for multi-state preparation", arXiv:2305.01816, (2023).
[50] Wang Fang, Chris Heunen, and Qisheng Wang, "Unitary Synthesis with Near-Optimal T-Count for Near-Clifford Unitaries", arXiv:2607.12907, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-13 13:04:26) and SAO/NASA ADS (last updated successfully 2026-08-13 13:04:27). 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.