Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Understand this faster with AI
AbstractWe prove that any $n$-qubit unitary can be implemented (i) approximately in time $\tilde O\big(2^{n/2}\big)$ with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth $\tilde O\big(2^{n/2}\big)$ with one- and two-qubit gates and $2^{O(n)}$ ancillae. The proofs involve similar reductions to Grover search. The proof of (ii) also involves a linear-depth construction of arbitrary quantum states using one- and two-qubit gates (in fact, this can be improved to constant depth with the addition of fanout and generalized Toffoli gates) which may be of independent interest. We also prove a matching $\Omega\big(2^{n/2}\big)$ lower bound for (i) and (ii) for a certain class of implementations.► BibTeX data@article{Rosenthal2026querydepthupper, doi = {10.22331/q-2026-06-30-2144}, url = {https://doi.org/10.22331/q-2026-06-30-2144}, title = {Query and {D}epth {U}pper {B}ounds for {Q}uantum {U}nitaries via {G}rover {S}earch}, author = {Rosenthal, Gregory}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2144}, month = jun, year = {2026} }► References [1] Scott Aaronson. ``The complexity of quantum states and transformations: from quantum money to black holes''. arXiv:1607.05256 (2016). arXiv:1607.05256 [2] Scott Aaronson and Greg Kuperberg. ``Quantum versus classical proofs and advice''. Theory Comput. 3, 129–157 (2007). arXiv:quant-ph/0604056. https://doi.org/10.4086/toc.2007.v003a007 arXiv:quant-ph/0604056 [3] Scott Aaronson. ``Open problems related to quantum query complexity''. ACM Trans. Quantum Comput. 2, 1–9 (2021). arXiv:2109.06917. https://doi.org/10.1145/3488559 arXiv:2109.06917 [4] Alex Lombardi, Fermi Ma, and John Wright. ``A one-query lower bound for unitary synthesis and breaking quantum cryptography''. In STOC. Pages 979–990. (2024). arXiv:2310.08870. https://doi.org/10.1145/3618260.3649650 arXiv:2310.08870 [5] Gregory Rosenthal. ``Efficient quantum state synthesis with one query''. In SODA. Pages 2508–2534. (2024). arXiv:2306.01723. https://doi.org/10.1137/1.9781611977912.89 arXiv:2306.01723 [6] 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 [7] Christopher M. Dawson and Michael A. Nielsen. ``The Solovay–Kitaev algorithm''. Quantum Inf. Comput. 6, 81–95 (2006). arXiv:quant-ph/0505030. https://doi.org/10.26421/QIC6.1-6 arXiv:quant-ph/0505030 [8] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. ``Quantum search-to-decision reductions and the state synthesis problem''. In CCC. Volume 234, pages 5:1–5:19. (2022). arXiv:2111.02999. https://doi.org/10.4230/lipics.ccc.2022.5 arXiv:2111.02999 [9] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. ``Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis''. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 42, 3301–3314 (2023). arXiv:2108.06150. https://doi.org/10.1109/TCAD.2023.3244885 arXiv:2108.06150 [10] 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). arXiv:2202.11302. https://doi.org/10.22331/q-2023-03-20-956 arXiv:2202.11302 [11] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. ``Quantum state preparation with optimal circuit depth: Implementations and applications''.
Physical Review Letters 129, 230504 (2022). arXiv:2201.11495. https://doi.org/10.1103/PhysRevLett.129.230504 arXiv:2201.11495 [12] Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. ``Counting, fanout, and the complexity of quantum ACC''. Quantum Inf. Comput. 2, 35–65 (2002). arXiv:quant-ph/0106017. https://doi.org/10.26421/QIC2.1-3 arXiv:quant-ph/0106017 [13] Peter Høyer and Robert Špalek. ``Quantum fan-out is powerful''. Theory Comput. 1, 81–103 (2005). https://doi.org/10.4086/toc.2005.v001a005 [14] Yasuhiro Takahashi and Seiichiro Tani. ``Collapse of the hierarchy of constant-depth exact quantum circuits''. Comput. Complexity 25, 849–881 (2016). arXiv:1112.6063. https://doi.org/10.1007/s00037-016-0140-0 arXiv:1112.6063 [15] Johan Håstad. ``Almost optimal lower bounds for small depth circuits''. In STOC. Pages 6–20. (1986). https://doi.org/10.1145/12130.12132 [16] Stasys Jukna. ``Boolean function complexity''. Volume 27 of Algorithms and Combinatorics. Springer, Heidelberg. (2012). https://doi.org/10.1007/978-3-642-24508-4 [17] Oleg Lupanov. ``On a method of circuit synthesis''. Izvestia VUZ 1, 120–140 (1958). https://doi.org/10.2307/2271493 [18] Claude Shannon. ``The synthesis of two-terminal switching circuits''.
Bell System Tech. J. 28, 59–98 (1949). https://doi.org/10.1002/j.1538-7305.1949.tb03624.x [19] Andris Ambainis. ``Quantum lower bounds by quantum arguments''. J. Comput. System Sci. 64, 750–767 (2002). arXiv:quant-ph/0002066. https://doi.org/10.1006/jcss.2002.1826 arXiv:quant-ph/0002066 [20] Ashwin Nayak. ``Inverting a permutation is as hard as unordered search''. Theory Comput. 7, 19–25 (2011). arXiv:1007.2899. https://doi.org/10.4086/toc.2011.v007a002 arXiv:1007.2899 [21] Sándor Imre and Ferenc Balázs. ``Quantum computing and communications: an engineering approach''. Chapter 7. John Wiley & Sons. (2005). https://doi.org/10.1002/9780470869048 [22] Nathan Wiebe (2021). Personal communication.Cited byCould not fetch Crossref cited-by data during last attempt 2026-06-30 09:34:23: Could not fetch cited-by data for 10.22331/q-2026-06-30-2144 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-06-30 09:34:23: Cannot retrieve data from ADS due to rate limitations.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. AbstractWe prove that any $n$-qubit unitary can be implemented (i) approximately in time $\tilde O\big(2^{n/2}\big)$ with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth $\tilde O\big(2^{n/2}\big)$ with one- and two-qubit gates and $2^{O(n)}$ ancillae. The proofs involve similar reductions to Grover search. The proof of (ii) also involves a linear-depth construction of arbitrary quantum states using one- and two-qubit gates (in fact, this can be improved to constant depth with the addition of fanout and generalized Toffoli gates) which may be of independent interest. We also prove a matching $\Omega\big(2^{n/2}\big)$ lower bound for (i) and (ii) for a certain class of implementations.► BibTeX data@article{Rosenthal2026querydepthupper, doi = {10.22331/q-2026-06-30-2144}, url = {https://doi.org/10.22331/q-2026-06-30-2144}, title = {Query and {D}epth {U}pper {B}ounds for {Q}uantum {U}nitaries via {G}rover {S}earch}, author = {Rosenthal, Gregory}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2144}, month = jun, year = {2026} }► References [1] Scott Aaronson. ``The complexity of quantum states and transformations: from quantum money to black holes''. arXiv:1607.05256 (2016). arXiv:1607.05256 [2] Scott Aaronson and Greg Kuperberg. ``Quantum versus classical proofs and advice''. Theory Comput. 3, 129–157 (2007). arXiv:quant-ph/0604056. https://doi.org/10.4086/toc.2007.v003a007 arXiv:quant-ph/0604056 [3] Scott Aaronson. ``Open problems related to quantum query complexity''. ACM Trans. Quantum Comput. 2, 1–9 (2021). arXiv:2109.06917. https://doi.org/10.1145/3488559 arXiv:2109.06917 [4] Alex Lombardi, Fermi Ma, and John Wright. ``A one-query lower bound for unitary synthesis and breaking quantum cryptography''. In STOC. Pages 979–990. (2024). arXiv:2310.08870. https://doi.org/10.1145/3618260.3649650 arXiv:2310.08870 [5] Gregory Rosenthal. ``Efficient quantum state synthesis with one query''. In SODA. Pages 2508–2534. (2024). arXiv:2306.01723. https://doi.org/10.1137/1.9781611977912.89 arXiv:2306.01723 [6] 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 [7] Christopher M. Dawson and Michael A. Nielsen. ``The Solovay–Kitaev algorithm''. Quantum Inf. Comput. 6, 81–95 (2006). arXiv:quant-ph/0505030. https://doi.org/10.26421/QIC6.1-6 arXiv:quant-ph/0505030 [8] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. ``Quantum search-to-decision reductions and the state synthesis problem''. In CCC. Volume 234, pages 5:1–5:19. (2022). arXiv:2111.02999. https://doi.org/10.4230/lipics.ccc.2022.5 arXiv:2111.02999 [9] Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. ``Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis''. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 42, 3301–3314 (2023). arXiv:2108.06150. https://doi.org/10.1109/TCAD.2023.3244885 arXiv:2108.06150 [10] 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). arXiv:2202.11302. https://doi.org/10.22331/q-2023-03-20-956 arXiv:2202.11302 [11] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. ``Quantum state preparation with optimal circuit depth: Implementations and applications''.
Physical Review Letters 129, 230504 (2022). arXiv:2201.11495. https://doi.org/10.1103/PhysRevLett.129.230504 arXiv:2201.11495 [12] Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. ``Counting, fanout, and the complexity of quantum ACC''. Quantum Inf. Comput. 2, 35–65 (2002). arXiv:quant-ph/0106017. https://doi.org/10.26421/QIC2.1-3 arXiv:quant-ph/0106017 [13] Peter Høyer and Robert Špalek. ``Quantum fan-out is powerful''. Theory Comput. 1, 81–103 (2005). https://doi.org/10.4086/toc.2005.v001a005 [14] Yasuhiro Takahashi and Seiichiro Tani. ``Collapse of the hierarchy of constant-depth exact quantum circuits''. Comput. Complexity 25, 849–881 (2016). arXiv:1112.6063. https://doi.org/10.1007/s00037-016-0140-0 arXiv:1112.6063 [15] Johan Håstad. ``Almost optimal lower bounds for small depth circuits''. In STOC. Pages 6–20. (1986). https://doi.org/10.1145/12130.12132 [16] Stasys Jukna. ``Boolean function complexity''. Volume 27 of Algorithms and Combinatorics. Springer, Heidelberg. (2012). https://doi.org/10.1007/978-3-642-24508-4 [17] Oleg Lupanov. ``On a method of circuit synthesis''. Izvestia VUZ 1, 120–140 (1958). https://doi.org/10.2307/2271493 [18] Claude Shannon. ``The synthesis of two-terminal switching circuits''.
Bell System Tech. J. 28, 59–98 (1949). https://doi.org/10.1002/j.1538-7305.1949.tb03624.x [19] Andris Ambainis. ``Quantum lower bounds by quantum arguments''. J. Comput. System Sci. 64, 750–767 (2002). arXiv:quant-ph/0002066. https://doi.org/10.1006/jcss.2002.1826 arXiv:quant-ph/0002066 [20] Ashwin Nayak. ``Inverting a permutation is as hard as unordered search''. Theory Comput. 7, 19–25 (2011). arXiv:1007.2899. https://doi.org/10.4086/toc.2011.v007a002 arXiv:1007.2899 [21] Sándor Imre and Ferenc Balázs. ``Quantum computing and communications: an engineering approach''. Chapter 7. John Wiley & Sons. (2005). https://doi.org/10.1002/9780470869048 [22] Nathan Wiebe (2021). Personal communication.Cited byCould not fetch Crossref cited-by data during last attempt 2026-06-30 09:34:23: Could not fetch cited-by data for 10.22331/q-2026-06-30-2144 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-06-30 09:34:23: Cannot retrieve data from ADS due to rate limitations.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.
Tags
Source Information
Discussion
0 professional contributions
Sign in to join this professional discussion.
Be the first to add a constructive contribution.