# Techniques: The Power of Shallow-depth Toffoli and Qudit Quantum Circuits

## What the paper contributes (one paragraph)

This is a quantum circuit complexity paper (arXiv:2404.18104) that proves new unconditional separations between constant-depth quantum circuits and constant-depth classical circuits, and new collapses among constant-depth quantum circuit classes. It separates constant-depth quantum circuits with quantum advice from the classical class of constant-depth circuits with MOD_p gates, and separates QAC0 augmented with mid-circuit measurement and classical fanout from the same class, the first such separation for a shallow class without quantum fanout that uses only finite gate sets. To do this the authors build several constructive primitives: a constant-depth qudit GHZ state preparation gadget from poor-man's cat states on balanced binary trees, a constant-depth implementation of threshold gates from Fourier transforms over Abelian groups (showing QNC0[p] = QTC0), and an exact decomposition of qudit operations into qubit circuits with only constant-factor overhead. They also bound the problems classically, showing the separation is tight for AC0[p].

## Techniques offered

- **Constant-depth qudit GHZ state preparation** - prepares high-dimensional GHZ states in constant depth using poor-man's cat states on balanced binary trees plus mid-circuit measurement and classical-fanout corrections, supplying a measurement-based resource-state preparation gadget for shallow circuits.
  - guarantee: static construction; constant depth and polynomial size GHZ preparation realisable by QAC0 with classical fanout (and equivalently by interleaved shallow quantum and AC0 classical layers), no statistical bound claimed.
  - quote: "To achieve these qudit GHZ states, we use a specialized entanglement structure built upon poor-man's cat states, as referenced in \cite{Watts19,Watts23,Liu2022depthefficient}."
- **Constant-depth threshold-gate compilation via Fourier transforms over Abelian groups** - implements quantum threshold gates in constant depth from qudit modular and fanout gates using Fourier transforms over Abelian groups, supplying a compilation route that proves QNC0[p] = QTC0 for prime-dimensional systems.
  - guarantee: static proof of computational equivalence (hierarchy collapse iQNC0[p] = iQTC0) for all primes p; exact, not approximate.
  - quote: "Specifically, our quantum circuits are constructed using Fourier transforms over Abelian groups and this approach allows the creation of circuits for functions over finite fields of the form $\mathbb{F}_p^n \rightarrow \mathbb{F}_p$."
- **Exact qudit-to-qubit circuit decomposition** - maps constant-depth prime-dimensional qudit circuits onto tensor products of qubits via exact unitary decomposition with only a multiplicative gate-count increase, supplying a compilation method to realise qudit protocols on qubit hardware.
  - guarantee: static proof; exact unitary decomposition preserving constant depth with constant-factor (multiplicative) overhead, no error introduced.
  - quote: "This result is achieved by mapping qudit operations onto tensor products of qubits. The qudit operations are produced using exact unitary decomposition methods, as previously demonstrated \cite{reck94,Barenco95}."

## Where it could apply

- Target primitive(s): sampling and shallow-circuit relation problems; the threshold-gate and qudit-to-qubit methods bear on quantum subroutines of QPE-style algorithms such as the factoring subroutine noted in the paper.
- Target application group(s): platforms_tooling; error_correction (the paper notes qudit encodings may aid error-correction schemes).
- Code family / hardware assumptions: prime-dimensional qudit hardware and platforms supporting native multi-qubit Toffoli gates; results transfer to standard qubit hardware via the exact decomposition.

## Caveats

This is primarily a theoretical complexity paper; its central results are unconditional class separations (fQNC0/qpoly not contained in AC0[p]; QAC0 with classical fanout not contained in AC0[p]) and class collapses, which are proofs about computational power rather than capabilities directly suppliable to an external vendor or application result. The three suppliable items above are the constructive gadgets and compilation methods used inside those proofs; they assume idealised, often infinite-size gate sets, carry no noise or fault-tolerance analysis, and the separations target only constant-depth classical adversaries.