Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Circuits with Unbounded Fan-out

Peter Høyer, Robert Špalek

Published Jan 1, 2002• 0 citations
OpenAlex

Abstract

Abstract. We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNC 0 f) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[q], and counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetical operations, phase estimation, and the quantum Fourier transform can also be approximated in constant depth. 1

Related papers

Quantum Circuits with Unbounded Fan-out

Peter Høyer, Robert Špalek

We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by $\mathrm{QNC}_{\mathrm{f}}^0$) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.

arXiv:quant-ph/0208043•Theory of Computing•Jan 1, 2005•90 citations

Quantum Fanout is Powerful

Peter Høyer, Robert Špalek

We demonstrate that the unbounded fan-out gate is very powerful.Constantdepth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNC 0 f ) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting.Classically, we need logarithmic depth even if we can use unbounded fan-in gates.If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth.Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.

Theory of Computing•Jan 1, 2005•48 citations

The power of constant-depth quantum circuits of unbounded size

Sergii Strelchuk, Sathyawageeswar Subramanian, Máté Weisz

Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension $d$ and $M\geq d^2-1$ ports, we construct a unitary circuit of depth $O(\sqrt d)$, independent of $M$ and including resource preparation and port selection, with entanglement fidelity at least $(1-(d^2-1)/(2M))^2$. Thus, at fixed $d$, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on $d$ can also be removed remains open.

quant-pharXiv:2609.40294•Oct 1, 2026•0 citations

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

Yasuhiro Takahashi, Seiichiro Tani

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.

arXiv:1112.6063•Dec 28, 2011•0 citations

Counting, fanout and the complexity of quantum ACC

F. Green, Steven Homer, Cristopher Moore +1 more

We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], the analog of the class ACC[q] where Mod_q gates are also allowed. We prove that parity or fanout allows us to construct quantum MOD_q gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q,p > 1, MOD_q is equivalent to MOD_p (up to constant depth and polynomial size). This implies that QAC^0 with unbounded fanout gates, denoted QACwf^0, is the same as QACC[q] and QACC for all q. Since \ACC[p] \ne ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages closely related to QACC[2] and show that restricted versions of them can be simulated by polynomial-size circuits. With further restrictions, language classes related to QACC[2] operators can be simulated by classical threshold circuits of polynomial size and constant depth.

Quantum Information and Computation•Jan 1, 2002•51 citations

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.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2013•12 citations
Abstract. We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNC 0 f) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[q], and counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetical operations, phase estimation, and the quantum Fourier transform can also be approximated in constant depth. 1
We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNCf0\mathrm{QNC}_{\mathrm{f}}^0QNCf0​) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.
We demonstrate that the unbounded fan-out gate is very powerful.Constantdepth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNC 0 f ) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[t], and Counting.Classically, we need logarithmic depth even if we can use unbounded fan-in gates.If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth.Sorting, arithmetic operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension ddd and M≥d2−1M\geq d^2-1M≥d2−1 ports, we construct a unitary circuit of depth O(d)O(\sqrt d)O(d​), independent of MMM and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2(1-(d^2-1)/(2M))^2(1−(d2−1)/(2M))2. Thus, at fixed ddd, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on ddd can also be removed remains open.
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.
We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], the analog of the class ACC[q] where Mod_q gates are also allowed. We prove that parity or fanout allows us to construct quantum MOD_q gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q,p > 1, MOD_q is equivalent to MOD_p (up to constant depth and polynomial size). This implies that QAC^0 with unbounded fanout gates, denoted QACwf^0, is the same as QACC[q] and QACC for all q. Since \ACC[p] \ne ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages closely related to QACC[2] and show that restricted versions of them can be simulated by polynomial-size circuits. With further restrictions, language classes related to QACC[2] operators can be simulated by classical threshold circuits of polynomial size and constant depth.
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.