The power of constant-depth quantum circuits of unbounded size

Technical Summary: The Power of Constant-Depth Quantum Circuits of Unbounded Size

Problem Statement
The paper investigates the computational power of quantum circuits when restrictions on circuit size and ancillary space are removed. In classical complexity, the class $AC^0$ (constant-depth circuits with unbounded fan-in AND/OR gates) cannot compute parity. However, if the polynomial size restriction is lifted, every Boolean function can be computed in constant depth via Disjunctive Normal Form (DNF) constructions. The authors ask whether a similar phenomenon holds for quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates (unbounded size $QAC^0$). Specifically, can every unitary operation be implemented exactly in constant depth if the circuit size and the number of ancillary qubits are unrestricted?

The authors frame this inquiry through four increasingly general tasks:

1. Computing membership in any set $L \subseteq \{0, 1\}^n$.
2. Implementing any permutation of computational basis states.
3. Preparing any pure quantum state.
4. Implementing any arbitrary unitary on every input state.

Methodology
The authors employ a combination of reversible classical circuit constructions, probabilistic classical techniques adapted to the quantum domain, and quantum teleportation protocols.

• Reversible Classical Constructions: The authors first establish that arbitrary permutations of bitstrings can be implemented in constant depth using Toffoli and fanout gates. This is achieved via an "indicator encoding" scheme: the input is mapped to a $2^n$-dimensional indicator vector (where exactly one entry is 1), manipulated, and then decoded back to the original string. This allows for the parallel evaluation of all possible input strings.
• Probabilistic to Quantum Adaptation: To prepare arbitrary probability distributions and pure quantum states, the authors adapt a classical probabilistic construction. This involves sampling bits independently to encode a distribution based on the position of the first '1'. In the quantum setting, this is made coherent by applying inverse rotations to qubits following the first '1' to return them to $|0\rangle$ without destroying the superposition.
• Gate Set Extensions: While the primary gate set includes single-qubit gates and generalised Toffoli gates, the authors utilize fanout gates as a conceptual tool. They cite results by Grier, Morris, and Wu [GMW26] and Rosenthal [Ros20] to show that fanout can be implemented exactly in constant depth using only the primary gate set, albeit with a potential increase in circuit size to doubly exponential bounds.
• Reductions for Unitaries: For the implementation of arbitrary unitaries, the authors do not provide a direct construction. Instead, they offer several equivalent formulations and reductions. These include reducing unitary implementation to:
  • Cloning vectors of a specified orthonormal basis.
  • Permuting lists of basis vectors.
  • Decoding basis labels.
  • Implementing unitaries with unit row and column sums (via the Idel-Wolf normal form).
  • Implementing traceless unitary involutions (using one additional clean qubit).
• Port-Based Teleportation (PBT): To approach the implementation of arbitrary unitaries without unitary corrections dependent on the specific gate, the authors utilize Port-Based Teleportation. They construct a unitary circuit that performs PBT using maximally entangled states (or Choi states of the target unitary) and a joint measurement, followed by port selection.

Key Contributions and Results

1. Exact Constant-Depth Constructions for Specific Tasks:

   • Permutations: Arbitrary permutations of computational basis states can be implemented in constant depth (depth $\le 20$) using $O(n2^n)$ gates and ancillary qubits.
   • Diagonal Unitaries: Arbitrary diagonal unitaries can be implemented in constant depth (depth 7) by computing indicators, applying phases in parallel, and uncomputing.
   • State Preparation: Arbitrary pure quantum states can be prepared in constant depth (depth $\le 37$) using $O(4^n)$ qubits and $O(n2^n)$ gates. All ancillary qubits are returned to zero.
   • Fanout Implementation: Fanout can be implemented exactly in constant depth using only single-qubit and generalised Toffoli gates, though this may require doubly exponential size.

2. Reductions for Arbitrary Unitaries:
   The paper demonstrates that implementing arbitrary unitaries in constant depth is equivalent to implementing any of several specific operations (e.g., cloning basis vectors, decoding labels, or implementing traceless involutions). This reframes the open problem of arbitrary unitary implementation into a set of equivalent structural challenges.

3. Adaptive Measurements and Gate Teleportation:
   The authors show that if adaptive intermediate measurements are allowed, any gate at level $\ell$ of the Clifford hierarchy can be implemented with depth $O(\ell)$. Furthermore, arbitrary unitary implementation reduces to implementing traceless unitary involutions in this adaptive model.

4. Port-Based Teleportation Approximation:
   The authors construct a unitary circuit for Port-Based Teleportation (PBT) for an input dimension $d$ and $M \ge d^2 - 1$ ports.

   • Depth: The circuit depth is $O(\sqrt{d})$, which is independent of the number of ports $M$.
   • Fidelity: The entanglement fidelity is bounded by $F_e \ge (1 - \frac{d^2-1}{2M})^2$.
   • Accuracy vs. Depth: For any fixed input dimension $d$, the approximation can be made arbitrarily accurate by increasing $M$ without increasing the circuit depth. However, the dependence on the input dimension $d$ remains; whether a depth bound independent of $d$ can be achieved remains an open question.
   • Implementation: The circuit uses only single-qubit and generalised Toffoli gates and requires no intermediate measurements.

Significance and Claims
The paper establishes that removing size and ancillary space restrictions allows constant-depth quantum circuits to perform tasks that are generally impossible in polynomial-size constant-depth models, such as arbitrary state preparation and permutation of basis states. This connects quantum state preparation directly to reversible classical computation and probability distribution preparation.

However, the paper maintains a modest stance regarding the implementation of arbitrary unitaries. While it provides exact constant-depth constructions for permutations, diagonal unitaries, and state preparation, the implementation of general unitaries remains an open problem. The authors provide equivalent characterizations of this problem but do not resolve it.

The primary contribution regarding general unitaries is the PBT construction. The authors demonstrate that for any fixed input dimension, arbitrary unitaries can be approximated with arbitrary precision without increasing the circuit depth by increasing the number of ports. However, the depth of this construction scales as $O(\sqrt{d})$ with the input dimension $d$. The authors explicitly state that whether this dependence on $d$ can be removed (i.e., achieving a depth bound independent of $d$) remains an open question. The work highlights that the fundamental difficulty in constant-depth unitary implementation lies not in producing an arbitrary output from a fixed input, but in prescribing the action on every input state simultaneously while preserving unitarity.