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] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).
[2] 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).
[3] 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.
[4] 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).
[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] 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).
[7] 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).
[8] 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).
[9] 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).
[10] 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).
[11] Gregory Rosenthal, "Query and Depth Upper Bounds for Quantum Unitaries via Grover Search", arXiv:2111.07992, (2021).
[12] Bojia Duan and Chang-Yu Hsieh, "Hamiltonian-based data loading with shallow quantum circuits", Physical Review A 106 5, 052422 (2022).
[13] Aaron Szasz, Ed Younis, and Wibe de Jong, "Numerical circuit synthesis and compilation for multi-state preparation", arXiv:2305.01816, (2023).
[14] 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).
[15] Gregory Rosenthal, "Efficient Quantum State Synthesis with One Query", arXiv:2306.01723, (2023).
[16] Gregory Boyd, "Low-Overhead Parallelisation of LCU via Commuting Operators", arXiv:2312.00696, (2023).
The above citations are from Crossref's cited-by service (last updated successfully 2024-05-18 04:34:11) and SAO/NASA ADS (last updated successfully 2024-05-18 04:34:12). 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.