arXiv:1112.6063

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

Yasuhiro Takahashi, Seiichiro Tani

Published Dec 28, 2011• 0 citations

Abstract

We study the quantum complexity class QNC^0_f of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates (called QNC^0_f circuits). Our main result is that the quantum OR operation is in QNC^0_f, which is an affirmative answer to the question of Hoyer and Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC^0 \subsetneq AC^0 \subsetneq TC^0, our result with Hoyer and Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC^0_f = QAC^0_f = QTC^0_f. Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This implies the size difference between the QNC^0_f and QTC^0_f circuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC^0_f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC^0_f oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC^0_f circuit with gates for the quantum Fourier transform.

DOI: 10.48550/arxiv.1112.6063

Related papers

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

Yasuhiro Takahashi, Seiichiro Tani

IEEE Conference on Computational Complexity (CCC)Jun 1, 201312 citations

Quantum Threshold Is Powerful

Daniel Grier, Jackson Morris

arXiv:2411.04953Leibniz international proceedings in informaticsNov 7, 20241 citation

Worst-case depth hierarchy for shallow quantum circuits

Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian +1 more

quant-pharXiv:2606.16425Jun 16, 20260 citations

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits

Alex B. Grilo, Elham Kashefi, Damian Markham +1 more

arXiv:2404.18104ACM Transactions on Quantum ComputingMay 18, 20263 citations

Quantum Threshold Is Powerful

Grier, Daniel, Morris, Jackson

Jan 1, 20250 citations

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

quant-pharXiv:2609.34659Sep 29, 20260 citations

arXiv:1112.6063

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

Yasuhiro Takahashi, Seiichiro Tani

Published Dec 28, 2011• 0 citations

arXiv HTML PDF

Abstract

DOI: 10.48550/arxiv.1112.6063

Related papers

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

Yasuhiro Takahashi, Seiichiro Tani

We study the quantum complexity class QNC0fof quantum operations implement able exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in QNC0f, which is an affirmative answer to the question of Hoyer and Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC0⊊ AC0⊊ TC0, our result with Hoyer and Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC0f= QAC0f= QTC0f. Then, we show that there exists a constant-depth sub quadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the QNC0fand QTC0fcircuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC0f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC0foracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC0fcircuit with gates for the quantum Fourier transform.We study the quantum complexity class QNC0fof quantum operations implement able exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in QNC0f, which is an affirmative answer to the question of Hoyer and Spalek. In sharp contrast to the strict hierarchy of the classical complexity classes: NC0⊊ AC0⊊ TC0, our result with Hoyer and Spalek's one implies the collapse of the hierarchy of the corresponding quantum ones: QNC0f= QAC0f= QTC0f. Then, we show that there exists a constant-depth sub quadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the QNC0fand QTC0fcircuits for implementing the same quantum operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in QNC0f, there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a QNC0foracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a QNC0fcircuit with gates for the quantum Fourier transform.

IEEE Conference on Computational Complexity (CCC)Jun 1, 201312 citations

Quantum Threshold Is Powerful

Daniel Grier, Jackson Morris

In 2005, Høyer and Špalek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean functions as well as the quantum Fourier transform. They also asked what other multi-qubit gates could rival Fanout in terms of computational power, and suggested that the quantum Threshold gate might be one such candidate. Threshold is the gate that indicates if the Hamming weight of a classical basis state input is greater than some target value. We prove that Threshold is indeed powerful - there are polynomial-size constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity. Our proof is a generalization of a proof by Rosenthal that exponential-size constant-depth circuits with generalized Toffoli gates can compute Fanout. Our construction reveals that other quantum gates able to "weakly approximate" Parity can also be used as substitutes for Fanout.In 2005, Høyer and Špalek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean functions as well as the quantum Fourier transform. They also asked what other multi-qubit gates could rival Fanout in terms of computational power, and suggested that the quantum Threshold gate might be one such candidate. Threshold is the gate that indicates if the Hamming weight of a classical basis state input is greater than some target value. We prove that Threshold is indeed powerful - there are polynomial-size constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity. Our proof is a generalization of a proof by Rosenthal that exponential-size constant-depth circuits with generalized Toffoli gates can compute Fanout. Our construction reveals that other quantum gates able to "weakly approximate" Parity can also be used as substitutes for Fanout.

arXiv:2411.04953Leibniz international proceedings in informaticsNov 7, 20241 citation

Worst-case depth hierarchy for shallow quantum circuits

Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian +1 more

Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$ . For each $d\ge 12$ , we construct a family of two-round interactive problems on which no depth- $(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$ , yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$ . A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$ , establishing a genuinely quantum hierarchy.Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.

quant-pharXiv:2606.16425Jun 16, 20260 citations

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits

Alex B. Grilo, Elham Kashefi, Damian Markham +1 more

The relevance of shallow-depth quantum circuits has recently increased, mainly due to their applicability to near-term devices. In this context, one of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. Our first contribution in this work is to prove new separations between classical and quantum constant-depth circuits. Firstly, we show a separation between constant-depth quantum circuits with quantum advice $\mathsf {QNC}^0/\mathsf {qpoly}$ , and $\mathsf {AC}^0[p]$ , which is the class of classical constant-depth circuits with unbounded-fan in and $\mathsf {MOD}_{p}$ gates. Additionally, we show a separation between $\mathsf {QAC}^0$ , the circuit class containing Toffoli gates with unbounded control, and $\mathsf {AC}^0[p]$ , when $\mathsf {QAC}^0$ is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between $\mathsf {AC}^0[p]$ and $[\mathsf {QNC}^0, \mathsf {AC}^0]^2$ , i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider $\mathsf {QNC}^0$ circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that $\mathsf {QNC}^0[p]=\mathsf {QTC}^0$ . Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.The relevance of shallow-depth quantum circuits has recently increased, mainly due to their applicability to near-term devices. In this context, one of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. Our first contribution in this work is to prove new separations between classical and quantum constant-depth circuits. Firstly, we show a separation between constant-depth quantum circuits with quantum advice $\mathsf {QNC}^0/\mathsf {qpoly} $ , and $\mathsf {AC}^0[p] $ , which is the class of classical constant-depth circuits with unbounded-fan in and $\mathsf {MOD}_{p} $ gates. Additionally, we show a separation between $\mathsf {QAC}^0 $ , the circuit class containing Toffoli gates with unbounded control, and $\mathsf {AC}^0[p] $ , when $\mathsf {QAC}^0 $ is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between $\mathsf {AC}^0[p] $ and $[\mathsf {QNC}^0, \mathsf {AC}^0]^2 $ , i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider $\mathsf {QNC}^0 $ circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that $\mathsf {QNC}^0[p]=\mathsf {QTC}^0 $ . Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.

arXiv:2404.18104ACM Transactions on Quantum ComputingMay 18, 20263 citations

Quantum Threshold Is Powerful

Grier, Daniel, Morris, Jackson

Jan 1, 20250 citations

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$ , it $\varepsilon$ -approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$ -width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$ , and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$ , and we prove a matching $Ω(\log\log(1/\varepsilon))$ -depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$ -depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth- $d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$ , and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity $\notin$ QAC $^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$ , and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

quant-pharXiv:2609.34659Sep 29, 20260 citations

\mathsf{QNC}^0

. For each

d\ge 12

, we construct a family of two-round interactive problems on which no depth-

(d-1)

quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than

d

by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every

d

, yielding a hierarchy of problems that show unconditional quantum advantage of

\mathsf{QNC}^0

over

\mathsf{NC}^0

. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within

\mathsf{QNC}^0

, establishing a genuinely quantum hierarchy.

\mathsf {QNC}^0/\mathsf {qpoly}

, and

\mathsf {AC}^0[p]

, which is the class of classical constant-depth circuits with unbounded-fan in and

\mathsf {MOD}_{p}

gates. Additionally, we show a separation between

\mathsf {QAC}^0

, the circuit class containing Toffoli gates with unbounded control, and

\mathsf {AC}^0[p]

, when

\mathsf {QAC}^0

is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between

\mathsf {AC}^0[p]

and

[\mathsf {QNC}^0, \mathsf {AC}^0]^2

, i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider

\mathsf {QNC}^0

circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that

\mathsf {QNC}^0[p]=\mathsf {QTC}^0

. Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.

δ>0

, it

\varepsilon

-approximates an arbitrary single-qubit gate using

O(\log^{1+δ}(1/\varepsilon))

clean ancillae, Hadamard and

T

single-qubit gates,

O(\log(1/\varepsilon))

-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard,

T

, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth

O(\log\log(1/\varepsilon))

, and we prove a matching

Ω(\log\log(1/\varepsilon))

-depth lower bound. Overall, we establish that

Θ(\log\log(1/\varepsilon))

-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-

d

QAC circuit can be simulated in depth

O(d)

using only Hadamard,

X

, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity

\notin

QAC

^0

to proving a Parity lower bound against circuits consisting only of Hadamard,

X

, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.