Query and Depth Upper Bounds for Quantum Unitaries via Grover Search

Gregory Rosenthal

doi:10.22331/q-2026-06-30-2144

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search

Gregory Rosenthal

Institute for Quantum Computing, University of Waterloo

Published:	2026-06-30, volume 10, page 2144
Editor:	Daniel Grier
Eprint:	arXiv:2111.07992v5
Doi:	https://doi.org/10.22331/q-2026-06-30-2144
Citation:	Quantum 10, 2144 (2026).

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

Abstract

We 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 by

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

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

[3] Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C. Caro, "Learning Quantum States and Unitaries of Bounded Gate Complexity", PRX Quantum 5 4, 040306 (2024).

[4] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).

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

[6] R. Weiss, A. Baroni, J. Carlson, and I. Stetcu, "Solving reaction dynamics with quantum computing algorithms", Physical Review C 111 6, 064004 (2025).

[7] Shuai Yang, Lihao Xu, Guojing Tian, and Xiaoming Sun, "Quantum circuit synthesis with qudit phase gadget method", arXiv:2504.12710, (2025).

[8] Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda, and Naoki Yamamoto, "Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicators", Physical Review Research 4 2, 023136 (2022).

[9] Chun-Tse Li and Hao-Chung Cheng, "Adaptive circuit learning of born machine: towards realization of amplitude embedding and quantum data loading", Quantum Science and Technology 10 2, 025019 (2025).

[10] Lorenzo Laneve, "Robust black-box quantum-state preparation via quantum signal processing", arXiv:2305.04705, (2023).

[11] Qisheng Wang and Zhicheng Zhang, "Tight quantum depth lower bound for solving systems of linear equations", Physical Review A 110 1, 012422 (2024).

[12] Xiao-Ming Zhang, "Robust and Optimal Loading of General Classical Data Into Quantum Computers", IEEE Transactions on Computer Aided Design 45 3, 1170 (2026).

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

[14] Pei Yuan, Jonathan Allcock, and Shengyu Zhang, "Does Qubit Connectivity Impact Quantum Circuit Complexity?", IEEE Transactions on Computer Aided Design 43 2, 520 (2024).

[15] David Gosset, Robin Kothari, and Kewen Wu, "Quantum state preparation with optimal T-count", arXiv:2411.04790, (2024).

[16] Akel Hashim, Ming Yuan, Pranav Gokhale, Larry Chen, Christian Juenger, Neelay Fruitwala, Yilun Xu, Gang Huang, Kasra Nowrouzi, Liang Jiang, and Irfan Siddiqi, "Efficient Generation of Multi-partite Entanglement between Non-local Superconducting Qubits using Classical Feedback", arXiv:2403.18768, (2024).

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

[18] William Kretschmer, "Quantum Pseudorandomness and Classical Complexity", arXiv:2103.09320, (2021).

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

[20] Zhicheng Zhang and Mingsheng Ying, "Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs", arXiv:2408.10054, (2024).

[21] Nai-Hui Chia, Daniel Liang, and Fang Song, "Quantum State Learning Implies Circuit Lower Bounds", arXiv:2405.10242, (2024).

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

[23] Shuai Yang, Wei Zi, Bujiao Wu, Cheng Guo, Jialin Zhang, and Xiaoming Sun, "Efficient quantum circuit synthesis for SAT-oracle with limited ancillary qubit", arXiv:2101.05430, (2021).

[24] Jingquan Luo, Guanzhong Li, and Lvzhou Li, "Space-time tradeoff for sparse quantum state preparation", arXiv:2506.16964, (2025).

[25] Qisheng Wang, "Optimal Trace Distance and Fidelity Estimations for Pure Quantum States", arXiv:2408.16655, (2024).

[26] Giacomo Belli, Marco Mordacci, and Michele Amoretti, "SRBB-Based Quantum State Preparation", arXiv:2503.13647, (2025).

[27] Yariv Yanay, Brian Swingle, and Charles Tahan, "Detecting Measurement-Induced Entanglement Transitions with Unitary Mirror Circuits", Physical Review Letters 133 7, 070601 (2024).

[28] Alex Lombardi, Fermi Ma, and John Wright, "A one-query lower bound for unitary synthesis and breaking quantum cryptography", arXiv:2310.08870, (2023).

[29] Qisheng Wang and Zhicheng Zhang, "Fast Quantum Algorithms for Trace Distance Estimation", arXiv:2301.06783, (2023).

[30] Yanwu Gu, Wei-Feng Zhuang, Xudan Chai, and Dong E. Liu, "Benchmarking universal quantum gates via channel spectrum", Nature Communications 14, 5880 (2023).

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

[32] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", arXiv:2504.05624, (2025).

[33] Alexander I. Zenchuk, Wentao Qi, and Junde Wu, "Arbitrary State Creation via Controlled Measurement", Quantum Information & Computation 26 1, 114 (2026).

[34] Stephen Fenner and Rabins Wosti, "Quantum Fanout and GHZ states using spin-exchange interactions", arXiv:2502.10602, (2025).

[35] Vu Tuan Hai, Nguyen Tan Viet, and Le Bin Ho, "Variational preparation of entangled states on quantum computers", arXiv:2306.17422, (2023).

[36] Giacomo Belli and Michele Amoretti, "Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm", arXiv:2602.06535, (2026).

[37] Qisheng Wang and Zhicheng Zhang, "Fast Quantum Algorithms for Trace Distance Estimation", IEEE Transactions on Information Theory 70 4, 2720 (2024).

[38] Yu Tanaka, Hayata Yamasaki, and Mio Murao, "Quantum state preparation via free binary decision diagram", Journal of Physics A Mathematical General 59 26, 265302 (2026).

[39] Xiao-Ming Zhang and Xiao Yuan, "Circuit complexity of quantum access models for encoding classical data", npj Quantum Information 10 1, 42 (2024).

[40] Shuai Yang, Wei Zi, Bujiao Wu, Cheng Guo, Jialin Zhang, and Xiaoming Sun, "Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit", IEEE Transactions on Computer Aided Design 43 3, 868 (2024).

[41] Qisheng Wang, "Optimal Trace Distance and Fidelity Estimations for Pure Quantum States", IEEE Transactions on Information Theory 70 12, 8791 (2024).

[42] David Gosset, Robin Kothari, and Kewen Wu, "Quantum state preparation with optimal T-count", Quantum 10, 2168 (2026).

[43] 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-10 14:00:25) and SAO/NASA ADS (last updated successfully 2026-08-10 14:00:34). 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.