Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits

Pei Yuan and Shengyu Zhang

Tencent Quantum Laboratory, Tencent, Shenzhen, Guangdong 518057, China

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

Updated version: The authors have uploaded version v3 of this work to the arXiv which may contain updates or corrections not contained in the published version v2.


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).

[2] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631–633 (2014).

[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.

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

[5] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Phys. Rev. Lett. 103, 150502 (2009).

[6] Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. ``Quantum linear system algorithm for dense matrices''. Phys. Rev. Lett. 120, 050502 (2018).

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

[8] Iordanis Kerenidis and Jonas Landman. ``Quantum spectral clustering''. Phys. Rev. A 103, 042415 (2021).

[9] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. ``Quantum support vector machine for big data classification''. Phys. Rev. Lett. 113, 130503 (2014).

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

[11] Guang Hao Low and Isaac L. Chuang. ``Optimal hamiltonian simulation by quantum signal processing''. Phys. Rev. Lett. 118, 010501 (2017).

[12] Guang Hao Low and Isaac L. Chuang. ``Hamiltonian Simulation by Qubitization''. Quantum 3, 163 (2019).

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

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

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

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

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

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

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

[20] Martin Plesch and Časlav Brukner. ``Quantum-state preparation with universal gate decompositions''. Phys. Rev. A 83, 032302 (2011).

[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.

[22] Xiao-Ming Zhang, Man-Hong Yung, and Xiao Yuan. ``Low-depth quantum state preparation''. Phys. Rev. Res. 3, 043200 (2021).

[23] Gregory Rosenthal. ``Query and depth upper bounds for quantum unitaries via grover search'' (2021). 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).

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

[26] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying. ``Parallel quantum algorithm for hamiltonian simulation'' (2021). 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).

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

[29] Emanuel Knill. ``Approximation by quantum circuits'' (1995). 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).

[31] M Mottonen and Juha J Vartiainen. ``Decompositions of general quantum gates'' (2005). arXiv:quant-ph/​0504100.

[32] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Quantum random access memory''. Phys. Rev. Lett. 100, 160501 (2008).

[33] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Architectures for a quantum random access memory''. Phys. Rev. A 78, 052310 (2008).

[34] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press. (2010).

[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.

[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.

[37] Lov Grover and Terry Rudolph. ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002). 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).

[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.

Cited by

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

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

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

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

[5] Anton S. Albino, Lucas Q. Galvão, Ethan Hansen, Mauro Q. Nooblath Neto, and Clebson Cruz, "Quantum algorithm for finding minimum values in a Quantum Random Access Memory", arXiv:2301.05122, (2023).

[6] Gregory Rosenthal, "Query and Depth Upper Bounds for Quantum Unitaries via Grover Search", arXiv:2111.07992, (2021).

[7] Bojia Duan and Chang-Yu Hsieh, "Hamiltonian-based data loading with shallow quantum circuits", Physical Review A 106 5, 052422 (2022).

[8] Kaiwen Gui, Alexander M. Dalzell, Alessandro Achille, Martin Suchara, and Frederic T. Chong, "Spacetime-Efficient Low-Depth Quantum State Preparation with Applications", arXiv:2303.02131, (2023).

[9] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", arXiv:2105.11889, (2021).

[10] Aaron Szasz, Ed Younis, and Wibe de Jong, "Numerical circuit synthesis and compilation for multi-state preparation", arXiv:2305.01816, (2023).

[11] Gregory Rosenthal, "Efficient Quantum State Synthesis with One Query", arXiv:2306.01723, (2023).

[12] Gregory Boyd, "Low-Overhead Parallelisation of LCU via Commuting Operators", arXiv:2312.00696.

[13] 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 Crossref's cited-by service (last updated successfully 2023-12-07 06:15:58) and SAO/NASA ADS (last updated successfully 2023-12-07 06:15:58). The list may be incomplete as not all publishers provide suitable and complete citation data.