pith. sign in

arxiv: 2111.07992 · v5 · submitted 2021-11-15 · 🪐 quant-ph · cs.CC

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search

Gregory Rosenthal This is my paper

Pith reviewed 2026-05-24 13:23 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords quantum unitariesGrover searchquery complexitycircuit depthquantum computingstate preparationoracle accessancilla qubits
0
0 comments X

The pith

Any n-qubit unitary can be implemented approximately in time Õ(2^{n/2}) with oracle queries or exactly in circuit depth Õ(2^{n/2}) with ancillae.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that arbitrary n-qubit unitaries admit implementations whose resource cost scales as the square root of the Hilbert-space dimension. With query access to a suitable classical oracle, the unitary can be approximated in time Õ(2^{n/2}). The same scaling holds exactly for circuit depth when one- and two-qubit gates are supplemented by 2^{O(n)} ancilla qubits. Both upper bounds are obtained by reducing the implementation task to Grover search; the circuit result also rests on a linear-depth subroutine for preparing arbitrary quantum states.

Core claim

We prove that any n-qubit unitary can be implemented (i) approximately in time Õ(2^{n/2}) with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth Õ(2^{n/2}) 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 Ω(2^{n/2}) lower bound for (i) and (ii) for a certain class of implementations.

What carries the argument

Reductions of unitary implementation to Grover search, together with a linear-depth subroutine for preparing arbitrary quantum states from one- and two-qubit gates.

If this is right

  • Approximate implementation of any unitary becomes possible with query complexity scaling as the square root of the Hilbert-space dimension.
  • Exact circuit implementations of unitaries achieve depth scaling as 2^{n/2} using one- and two-qubit gates plus polynomially many ancilla qubits.
  • Arbitrary quantum states can be prepared exactly with one- and two-qubit gates in linear depth.
  • Matching lower bounds of Ω(2^{n/2}) hold for certain restricted classes of implementations.
  • The state-preparation subroutine may be reused in other quantum algorithms that require specific initial states.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Oracle access models make quantum control of unitaries feasible at scales previously considered costly.
  • The linear-depth state preparation may apply directly to other tasks that begin with a prescribed quantum state.
  • Similar Grover reductions could be examined for implementing quantum channels or measurements rather than unitaries.
  • The bounds invite study of how they degrade when the gate set is further restricted or when the oracle is noisy.

Load-bearing premise

An appropriate classical oracle encoding the unitary is available for queries, and 2^{O(n)} ancilla qubits plus the linear-depth state-preparation subroutine are available for the circuit construction.

What would settle it

An explicit n-qubit unitary together with a proof that its approximate implementation requires more than 2^{n/2} queries to any classical oracle, or that its exact implementation requires circuit depth greater than 2^{n/2} even with 2^{O(n)} ancillae.

Figures

Figures reproduced from arXiv: 2111.07992 by Gregory Rosenthal.

Figure 1
Figure 1. Figure 1: The nodes are labeled with the inputs to [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that any n-qubit unitary can be implemented (i) approximately in time Õ(2^{n/2}) with query access to an appropriate classical oracle, and (ii) exactly by a circuit of depth Õ(2^{n/2}) using one- and two-qubit gates and 2^{O(n)} ancillae. Both results are obtained via reductions to Grover search; the proof of (ii) additionally supplies a linear-depth subroutine for arbitrary state preparation (improvable to constant depth with fanout and generalized Toffoli gates) that may be of independent interest. A matching Ω(2^{n/2}) lower bound is shown for a restricted class of implementations.

Significance. If the reductions hold, the work supplies tight query and depth bounds for arbitrary unitary implementation, a central question in quantum complexity. The explicit Grover reductions and the auxiliary state-preparation construction are concrete strengths; the matching lower bound for the indicated class further strengthens the contribution. These results could inform oracle-model algorithms and circuit-depth analyses more broadly.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'an appropriate classical oracle' is used without a one-sentence characterization of its input/output format; adding this would improve immediate readability.
  2. [Abstract] The lower-bound statement refers to 'a certain class of implementations' without an explicit definition in the abstract; a parenthetical pointer to the precise restriction (e.g., 'oracle-free circuits of linear depth') would clarify the tightness claim.
  3. The manuscript would benefit from a short comparison paragraph (or table) situating the new Õ(2^{n/2}) bounds against prior query and depth results for unitary synthesis.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation for minor revision. The report lists no major comments, so we have nothing to address point by point. We will incorporate any minor suggestions into the revised manuscript.

Circularity Check

0 steps flagged

No significant circularity; derivations reduce to external Grover search

full rationale

The paper establishes its Õ(2^{n/2}) upper bounds via explicit reductions of unitary implementation to the standard Grover search algorithm (an externally verified primitive) together with a linear-depth arbitrary-state-preparation subroutine that is constructed from one- and two-qubit gates without reference to the target bounds. The matching lower bound applies only to a restricted class of implementations and does not rely on any self-referential definitions, fitted parameters, or self-citation chains. All modeling assumptions (oracle access, ancilla count) are stated explicitly and do not presuppose the claimed results. No load-bearing step reduces to a prior result by the same author or to a tautological renaming.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard correctness of Grover's algorithm and the conventional quantum circuit model with one- and two-qubit gates; these are drawn from prior literature rather than introduced here. No free parameters, ad-hoc axioms, or new entities are invoked in the abstract.

axioms (2)
  • standard math Correctness and query complexity of Grover's search algorithm
    The proofs reduce the unitary implementation problem to Grover search, relying on its established properties.
  • domain assumption Standard quantum circuit model allowing one- and two-qubit gates plus ancillae
    Used to define the depth measure and the exact implementation in part (ii).

pith-pipeline@v0.9.0 · 5676 in / 1684 out tokens · 34437 ms · 2026-05-24T13:23:19.677434+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Nonstabilizerness Mpemba Effects

    quant-ph 2026-05 unverdicted novelty 7.0

    In U(1)-symmetric random circuits, initial states with lower stabilizer Rényi entropy generate nonstabilizerness faster than those with higher entropy, with the effect also depending on spatial charge structure and ex...

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · cited by 1 Pith paper · 7 internal anchors

  1. [1]

    Open problems related to quantum query complexity

    Scott Aaronson. “Open problems related to quantum query complexity”. Sec. 6. 2021. url: https://www.scottaaronson.com/papers/open.pdf (p. 1). 16

    work page 2021

  2. [2]

    The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

    Scott Aaronson. “The complexity of quantum states and transformations: from quan- tum money to black holes”. 2016. arXiv: 1607.05256 (pp. 1, 2, 10)

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  3. [3]

    Quantum versus classical proofs and advice

    Scott Aaronson and Greg Kuperberg. “Quantum versus classical proofs and advice”. In: Theory Comput. 3.7 (2007), pp. 129–157. doi: 10.4086/toc.2007.v003a007 . arXiv: quant-ph/0604056 (p. 1)

    work page doi:10.4086/toc.2007.v003a007 2007

  4. [4]

    Quantum lower bounds by quantum arguments

    Andris Ambainis. “Quantum lower bounds by quantum arguments”. In: J. Comput. System Sci. 64.4 (2002), pp. 750–767. doi: 10.1006/jcss.2002.1826. arXiv: quant- ph/0002066 (pp. 5, 8)

    work page doi:10.1006/jcss.2002.1826 2002

  5. [5]

    Quantum Amplitude Amplification and Estimation

    Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. “Quantum amplitude amplification and estimation”. In: Quantum computation and information . Vol. 305. Contemp. Math. Amer. Math. Soc., 2002, pp. 53–74. doi: 10.1090/conm/305/05215. arXiv: quant-ph/0005055 (p. 7)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1090/conm/305/05215 2002

  6. [6]

    The Solovay-Kitaev algorithm

    Christopher M. Dawson and Michael A. Nielsen. “The Solovay–Kitaev algorithm”. In: Quantum Inf. Comput. 6.1 (2006), pp. 81–95. arXiv: quant-ph/0505030 (p. 3)

    work page internal anchor Pith review Pith/arXiv arXiv 2006

  7. [7]

    Quantum random access memory

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. “Quantum random access memory”. In: Phys. Rev. Lett. 100.16 (2008), p. 160501. doi: 10.1103/PhysRevLett. 100.160501. arXiv: 0708.1879 (p. 2)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett 2008

  8. [8]

    Matrix computations

    Gene H Golub and Charles F Van Loan. Matrix computations . JHU press, 2013 (p. 12)

    work page 2013

  9. [9]

    Counting, Fanout, and the Complexity of Quantum ACC

    Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. “Count- ing, fanout, and the complexity of quantum ACC”. In: Quantum Inf. Comput. 2.1 (2002), pp. 35–65. arXiv: quant-ph/0106017 (pp. 4, 16)

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  10. [10]

    Almost optimal lower bounds for small depth circuits

    Johan H˚ astad. “Almost optimal lower bounds for small depth circuits”. In: STOC. 1986, pp. 6–20. doi: 10.1145/12130.12132 (p. 4)

    work page doi:10.1145/12130.12132 1986

  11. [11]

    Quantum Fan -out is Powerful

    Peter Høyer and Robert ˇSpalek. “Quantum fan-out is powerful”. In: Theory Comput. 1.5 (2005), pp. 81–103. doi: 10.4086/toc.2005.v001a005 (p. 4)

    work page doi:10.4086/toc.2005.v001a005 2005

  12. [12]

    John Wiley & Sons, 2005

    S´ andor Imre and Ferenc Bal´ azs.Quantum Computing and Communications: an engi- neering approach. John Wiley & Sons, 2005. Chap. 7. doi: 10.1002/9780470869048 (p. 7)

    work page doi:10.1002/9780470869048 2005

  13. [13]

    Quan- tum search-to-decision reductions and the state synthesis problem

    Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. “Quan- tum search-to-decision reductions and the state synthesis problem”. In:CCC. Vol. 234. 2022, 5:1–5:19. doi: 10.4230/lipics.ccc.2022.5. arXiv: 2111.02999 (p. 3)

    work page doi:10.4230/lipics.ccc.2022.5 2022

  14. [14]

    Boolean function complexity

    Stasys Jukna. Boolean function complexity. Vol. 27. Algorithms and Combinatorics. Advances and frontiers. Springer, Heidelberg, 2012. doi: 10 . 1007 / 978 - 3 - 642 - 24508-4 (p. 4)

    work page 2012

  15. [15]

    On a method of circuit synthesis

    Oleg Lupanov. “On a method of circuit synthesis”. In: Izvestia VUZ 1 (1958), pp. 120–140. doi: 10.2307/2271493 (p. 4). 17

    work page doi:10.2307/2271493 1958

  16. [16]

    Inverting a permutation is as hard as unordered search

    Ashwin Nayak. “Inverting a permutation is as hard as unordered search”. In: Theory Comput. 7 (2011), pp. 19–25. doi: 10.4086/toc.2011.v007a002. arXiv: 1007.2899 (pp. 5, 8)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4086/toc.2011.v007a002 2011

  17. [17]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum In- formation: 10th Anniversary Edition . Cambridge University Press, 2010. doi: 10. 1017/CBO9780511976667 (pp. 3, 5, 7, 11)

    work page 2010

  18. [18]

    Efficient Quantum State Synthesis with One Query

    Gregory Rosenthal. “Efficient Quantum State Synthesis with One Query”. 2023. arXiv: 2306.01723 (pp. 2, 10)

    work page arXiv 2023

  19. [19]

    The synthesis of two-terminal switching circuits

    Claude Shannon. “The synthesis of two-terminal switching circuits”. In: Bell System Tech. J. 28 (1949), pp. 59–98. doi: 10.1002/j.1538-7305.1949.tb03624.x (p. 4)

    work page doi:10.1002/j.1538-7305.1949.tb03624.x 1949

  20. [20]

    Asymp- totically optimal circuit depth for quantum state preparation and general unitary synthesis

    Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. “Asymp- totically optimal circuit depth for quantum state preparation and general unitary synthesis”. In: IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. (2023). doi: 10.1109/TCAD.2023.3244885. arXiv: 2108.06150 (pp. 3, 4)

    work page doi:10.1109/tcad.2023.3244885 2023

  21. [21]

    Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

    Yasuhiro Takahashi and Seiichiro Tani. “Collapse of the hierarchy of constant-depth exact quantum circuits”. In: Comput. Complexity 25.4 (2016), pp. 849–881. doi: 10.1007/s00037-016-0140-0. arXiv: 1112.6063 (p. 4)

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00037-016-0140-0 2016

  22. [22]

    Personal communication

    Nathan Wiebe. Personal communication. 2021 (p. 7)

    work page 2021

  23. [23]

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

    Pei Yuan and Shengyu Zhang. “Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits”. In: Quantum 7 (2023), p. 956. doi: 10.22331/q-2023-03-20-956 . arXiv: 2202.11302 (pp. 3, 4)

    work page doi:10.22331/q-2023-03-20-956 2023

  24. [24]

    Quantum state preparation with optimal circuit depth: Implementations and applications

    Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. “Quantum state preparation with optimal circuit depth: Implementations and applications”. In:Physical Review Letters 129.23 (2022), p. 230504. doi: 10.1103/PhysRevLett.129.230504 . arXiv: 2201. 11495 (p. 4). 18

    work page doi:10.1103/physrevlett.129.230504 2022