Depth-Optimal Quantum Compilation

1 Introduction

• Logarithmic-width multi-qubit gates enable constant-depth arbitrary single-qubit synthesis, whereas bounded-width gates require Θ(log log(1/ε))-depth, which is optimal.The paper frames this width–depth tradeoff as the answer to whether fixed-gate compilation can preserve circuit depth.Source: §1 · p. 3, §1.2.1 · p. 7

1.2 Main Results and Technical Overview

• For decision computation, Hadamard, X, and generalized Toffoli gates suffice for depth-preserving real simulation by preserving final acceptance probability rather than the full complex state.Handling phase information in parallel avoids the serialization caused by a shared real-encoding ancilla.Source: §1 · p. 4

1.1 The Standard, Universal, and Real Circuit Hierarchies

• The standard, universal, and real hierarchies vary their single-qubit gates, while the paper distinguishes unitary synthesis from real simulations that preserve bounded-error decision probabilities.The universal hierarchy uses {H, T, X}; the real hierarchy further restricts this to {H, X}.Source: §1.1 · pp. 6–7

1.2 Main Results and Technical Overview

• The overview identifies reusable catalyst states, Fan-Out elimination, real simulation, and a structured Fourier and scalar Forrelation representation as tools for extending the synthesis results to circuits.The Forrelation representation expresses single-output acceptance bias with only a constant-factor increase in the number of layers.Source: §1 · p. 5, §1.2 · p. 7

1.2.1 Depth-Optimal Single-Qubit Synthesis

• With {H, T, CNOT}, arbitrary single-qubit unitaries can be cleanly ε-approximated in depth O(log log(1/ε)); width-O(log(1/ε)) generalized Toffoli gates and wider Fan-Out permit constant depth.The constant-depth construction uses O(log(1/ε)) gates and Oγ(log1+γ(1/ε)) clean ancillae, for every fixed γ ∈ (0, 1).Source: §1.2.1 · p. 7
• For every fixed finite bounded-arity gate set, worst-case depth Ω(log log(1/ε)) is necessary to approximate every single-qubit Rz rotation, even with arbitrarily many initialized ancillae.The lower bound does not require ancillae to be restored at the end.Source: §1.2.1 · p. 8

1.2.2 Depth-Preserving Compilation with Restricted Multi-Qubit Gates

• Generalized Toffoli gates alone suffice for constant-depth synthesis by replacing its polylogarithmic-width Fan-Out operations with constant-depth implementations.For fixed c, β > 0, Fan-Out on O(log^c n) targets has a polynomial-size constant-depth implementation over Hadamard and generalized Toffoli gates with coherent error at most n^-β.Source: §1 · p. 4, §1.2.2 · p. 9
• Coherent Fan-Out gadgets can replace primitive Fan-Out in the single-qubit synthesizer, yielding a fixed-gate compiler without asymptotically increasing QAC or QTC depth.The gadgets coherently approximate Fan-Out on arbitrary inputs and approximately restore their implementation ancillae.Source: §1.2.2 · p. 9
• Reusable catalyst preparation adds depth O(log log((w + 2)/ε)) once, enabling compilation with additive depth overhead and universal Fan-Out hierarchy collapse for D(n) = Ω(log log n).The catalyst bank is reused across computation layers, so its preparation error is incurred once rather than accumulating; the bounded-arity Fan-Out constant-depth collapse remains open.Source: §1.2.2 · p. 10

1.2.3 Depth-Preserving Real Simulation

• Depth-d circuits admit real simulations of depth O(d+1) in bounded-width models and O(d + log log(s/ε)) in QUNC and QUNCf.These simulations preserve classical-input acceptance probabilities up to ε; bounded-arity simulations use a reusable catalyst, whose preparation adds only O(log log(s/ε)) depth.Source: §1.2.3 · pp. 10–11

1.2.4 Structured Fourier Circuits and Scalar Forrelation

• For every D(n) ≥1, QRNCf[D] = FHA3,f[D], QRACf[D] = FHAf[D], and QRTCf[D] = FHTf[D], with depth preserved up to a constant factor.The disjoint-block structured phases encode the parallel structure of the original circuits.Source: §1.2.4 · p. 12
• A structured Fourier circuit with ℓ phase layers has an exact scalar Forrelation representation using O(ℓ+1) phase functions from the same family.The nonlinear phases are fixed by the circuit and input dependence occurs only through affine terms in the first and last phase layers; the bounded-error decision gap is preserved.Source: §1.2.4 · p. 13

1.3 Discussion and Open Problems

• The paper leaves open whether bounded-arity Fan-Out equalities hold at constant depth and whether its wide reversible operations yield practical fault-tolerant runtime or space–time savings.Generalized Toffoli and other wide operations may incur substantial T-depth, T-count, routing, or magic-state costs when compiled to Clifford+T.Source: §1.3 · p. 14
• The paper asks whether Parity or Majority lies outside QRAC0 = FHA[1], which would imply corresponding longstanding lower bounds for QAC0.The proposed route studies constant-fold structured Forrelation with disjoint AND phase blocks and affine boundary phases.Source: §1.3 · p. 14

3 Block-Encoding Based Single-Qubit Gate Synthesis

• One round of oblivious amplitude amplification removes the block encoding’s factor of 1/2, recovering the target rotation.The construction separates block encoding from a fixed amplification procedure.Source: §3 · pp. 15–16
• Four nonnegative dyadic weights encode the real and imaginary parts of half the target phase rotation using fixed unitaries.Their interval sizes partition a uniform superposition over computational-basis addresses; the resulting distinguished block approximates half of Rz(θ).Source: §3 · pp. 15–16
• The construction chooses integer interval sizes, implements interval-controlled SELECT with reversible comparisons, and amplifies the resulting block encoding.Its depth depends on a constant number of reversible comparisons and computational-basis reflections.Source: §3 · p. 16

3.1 Dyadic Approximation of 1

• The four coefficients are rounded to multiples of 2^-m while preserving their total sum, yielding nonnegative integer interval sizes.The coefficient representation encodes the real and imaginary parts through differences between paired weights.Source: §3.1 · pp. 16–17

3.2.1 O(log(m))-Depth, O(m)-Space Implementation via {X, CNOT, Toffoli}

• For every m-bit input and hardwired M, the value-threshold function is computed exactly and cleanly with {X, CNOT, Toffoli} gates in O(log m) depth, O(m) size, and O(m) space.A balanced tree combines two-bit summaries of equality and less-than relations; the comparison summary at a block makes its internal bits unnecessary at later levels.Source: §3.2.1 · pp. 17–18

3.2.2 Constant-Depth Implementation with Large Fan-Out and Toffoli

• For constant k, wider merges compute the value-threshold function exactly and cleanly in O(k) depth, O_k(m) size, and O_k(m^(1+1/(2k−1))) space.The construction uses Fan-Out and Toffoli gates with widths bounded by the branching factor; temporary workspace is cleaned and reused between levels.Source: §3.2.2 · pp. 19, 21
• The wide-gate construction replaces each binary comparison merge with a wider merge, combining child equality and less-than summaries in parallel.Fan-Out supplies copies of shared equality bits so the Toffoli operations can run on disjoint qubits.Source: §3.2.2 · pp. 19–20

3.3 Oblivious Amplitude Amplification

• OAA alternates the underlying unitary with reflections about a fixed ancilla-flagged good subspace, amplifying that component without reflecting about or knowing the data-register state.This makes OAA useful for block encodings, where the desired operator occupies a distinguished ancilla block.Source: §3.3 · p. 21

3.3.1 Exact OAA: 1 2U 7→U up to a fixed sign

• When the distinguished block is U/2 for unitary U, one OAA step yields −U, with ancillas exactly restored to |0a⟩ and no measurement or postselection.The minus sign is a fixed global phase and can be removed exactly.Source: §3.3.1 · p. 22

3.3.2 Robust OAA for an approximate 1 2Rz(θ) block

• For an approximate 1/2 Rz(θ) block, one OAA step bounds the amplified-block error and the squared leakage outside the all-zero ancilla subspace by 13δ².The leakage bound holds for every unit input; the full isometry guarantee uses one fixed global phase and holds uniformly, including inputs entangled with a reference system.Source: §3.3.2 · pp. 22–23

3.3.3 Coherent Implementation of the OAA Procedure

• The OAA procedures are coherent, but implementing the all-zero-subspace reflection takes constant depth with generalized Toffoli gates and O(log(a + 1)) depth with bounded-arity gates.In the approximate case, small leakage may remain; the analysis controls the complete joint state rather than measuring ancillas.Source: §3.3.3 · pp. 23–24

3.4.1 Approximate Synthesis of Arbitrary Rz(θ) Gates

• O(log log(1/ε)) depth suffices to synthesize Rz(θ) with bounded-width gates, using a dyadic approximation, reversible comparisons, and one OAA step.For m = Θ(log(1/ε)), the comparison and reflection steps have depth O(log m).Source: §3.4.1 · p. 24
• The Rz block encoding coherently partitions a uniform address superposition into four intervals and conditionally applies I, −I, −iZ, or iZ before OAA removes the factor of 1/2.The interval labels and comparison workspace are uncomputed; the address register’s all-zero block encodes the approximate rotation.Source: §3.4.1 · pp. 25–26
• With logarithmic-width generalized Toffoli and sublogarithmic-width Fan-Out gates, the Rz synthesizer has constant depth, O(log(1/ε)) gates, and O(log^(1+γ)(1/ε)) workspace.The construction uses a fixed phase φ = π and has error at most ε.Source: §3.4.1 · p. 27

3.4.2 Approximate Synthesis of Any Single-Qubit Unitary

• Any single-qubit unitary reduces to three Rz rotations and Hadamard gates, reusing the same clean workspace while the three rotation errors add.The reduction uses a three-step hybrid argument and preserves the fully unitary, clean-ancilla synthesis guarantee.Source: §3.4.2 · pp. 27–28

4 A Lower-Bound Establishing QUNC Depth Optimality

• For finite gate sets of width at most r, worst-case depth for ε-approximating every Rz(θ) is Ω(log log(1/ε)), even with arbitrarily many clean ancillas that need not be restored.This is not a lower bound for every individual angle.Source: §4 · pp. 28–30
• A depth-d circuit’s output light cone contains at most r^d input wires, limiting the number of distinct channels; combining this count with the packing bound gives the depth lower bound.Gates outside the output light cone do not change the induced output channel.Source: §4 · pp. 29–30
• At precision ε, Θ(1/ε) pairwise more-than-2ε-separated rotations require at least Θ(1/ε) distinct output channels to approximate the full family.The separation is witnessed in diamond norm, so a single channel cannot approximate two rotations in the packing.Source: §4 · p. 30

5 Preparing the Kim–Laakkonen Catalyst

• A single eigenstate catalyst |ψ1⟩ suffices for the phase-gate family, replacing an angle-independent bank of b eigenstates; the paper prepares this fixed catalyst directly.The catalyst enables the online phase-kickback step, while ordinary circuits still need to construct it from |0⟩-initialized ancillae.Source: §5 · p. 30

5.1 The Kim–Laakkonen Eigenstate Catalyst

• The catalyst state is prepared from b independent single-qubit phase states in parallel, followed by a basis relabeling; choosing b = Θ(log(1/ε)) and factor error η = Θ(ε/b) gives total preparation error at most ε and depth O(log log(1/ε)).Padding by one basis label contributes trace-distance error 2^−b/2.Source: §5.1 · pp. 31–32

5.2 Basis Permutations

• Every b-bit basis permutation has an exact clean implementation with depth O(log b) and gate count and workspace O(b2^b); with generalized Toffoli gates, the construction becomes constant-depth with the same asymptotic size and workspace.The logarithmic-depth construction uses a one-hot encoding, parallel conjunction trees, and parity lookups.Source: §5.2 · pp. 32–33

5.3 Catalyst Preparation

• The general clean preparation uses depth O(log b + log log(1/η)) and size w2^O(b) + O(wb log(1/η)).Its two error sources are phase-state synthesis and the amplitude on one extra padded basis vector.Source: §5.3 · pp. 33–34
• For any w ≥ 1 and ε ∈ (0, 1), w universal catalysts can be prepared with trace-distance error at most ε using b = O(log(w/ε)); gate count and workspace are polynomial in w and 1/ε.The construction prepares copies in parallel, so increasing their number affects size and workspace but not depth.Source: §5.3 · p. 35

6 Approximate Polylogarithmic Fan-Out

• Fixed-polylogarithmic-width Fan-Out gates in the specified QAC^f synthesis circuits can be compiled into QAC circuits with the same asymptotic depth, polynomial size, and inverse-polynomial error.The approximation is coherent and clean, approximately restoring zero-initialized workspace; the result does not imply a general QAC^f collapse.Source: §6 · p. 35

6.1 Prior Results

• The nekomata construction prepares two equally weighted endpoint branches, encoding input Parity as their relative phase before uncomputing and testing whether preparation returns to zero.Hadamard conjugation then gives Fan-Out.Source: §6 · p. 35
• The singleton-grid construction uses q(t + 1) qubits and O(q(t + 1)) Hadamard and generalized Toffoli gates in constant depth.Its target column is designed to place nearly equal probability on the all-zero and all-one strings, making the grid state close to a nekomata.Source: §6.1 · pp. 36–37
• A nekomata-to-Parity reduction uses two preparation and two inverse-preparation calls, plus O(A + L) additional Hadamard and generalized Toffoli gates at constant additional depth.It approximately returns the preparation register to zero.Source: §6.1 · p. 37

6.2 Universal Polylogarithmic Fan-Out

• Logarithmic-width Fan-Out can be implemented in constant depth over Hadamard and generalized Toffoli gates with inverse-polynomial error and polynomial resources.A copying tree composes these gadgets to reach any fixed polylogarithmic target count while preserving constant depth and polynomial size.Source: §6.2 · pp. 38–40
• A copying tree extends logarithmic-width Fan-Out to polylogarithmically many targets in constant depth by using Θ(log n)-target branches across constantly many levels.The construction replaces each tree Fan-Out gate with a constant-depth implementation and runs disjoint gates within each level in parallel.Source: §6.1 · p. 38, §6.2 · p. 40

7.1 Immediate Consequences of Single-Qubit Synthesis

• Direct compilation gives depth O(d log log(s/ε)) and gate count and workspace O(s log((s + 2)/ε)); with generalized Toffoli and Fan-Out, depth is O(d).The bounded-error decision consequence includes QNC0 = QUNC0; the constant-depth claim is decision-specific and does not approximate the full unitary.Source: §7 · p. 41, §7.1 · p. 42

7.2 Depth-Preserving Single-Qubit Gate Synthesis in QUAC0

• QAC circuits admit clean full-unitary approximation over H, T, and generalized Toffoli gates at depth O(d), with size and workspace polynomial in s and 1/ε.The construction removes the polylogarithmic-width Fan-Out used during single-qubit synthesis by replacing it with constant-depth implementations.Source: §7.2 · pp. 43–44

7.1 Immediate Consequences of Single-Qubit Synthesis

• For bounded-error decision problems, the section establishes depth-preserving universalization of QAC and QTC at every fixed depth exponent k ≥ 0.The direct bounded-width simulations incur O(log log n) depth per original layer, while generalized Toffoli and Fan-Out allow constant-depth replacements in QAC0f and QTC0f.Source: §7.1 · p. 43, §7.2 · p. 45

7.3 Additive-Depth Compilation in QUNCf with a Catalyst

• For QNCf circuits, catalytic universalization gives depth D + log log r + w + 2, with size and workspace polynomial in s and 1/δ.The catalyst bank is reused across layers and its preparation contributes only once; the section also leaves constant-depth universalization of QNC0f open.Source: §7.3 · p. 46
• The online simulation has depth O(D), and its error bound depends on initial catalyst-preparation error rather than the number of bank reuses.The catalyst is restored exactly after each ideal use, allowing the same bank to be reused across layers.Source: §7.3 · pp. 47–48
• The catalyst factory and online controlled maps use polynomially many gates and ancillae in circuit size and inverse error.The factory contributes O(log b + log log(1/η)) depth, while the online simulation has depth O(D).Source: §7.3 · p. 48
• For polynomial-size circuit families, catalyst preparation adds O(log log n) depth at inverse-polynomial accuracy, yielding total depth O(D(n)) when D(n) = Ω(log log n).The construction retains polynomial size and gives the unitary-synthesis equality; sufficiently small constant compilation error also preserves bounded-error completeness and soundness.Source: §7.3 · p. 48
• When D(n) = Ω(log log n), the bounded-error decision classes in the Fan-Out hierarchies coincide, including for D(n) = log^k n with fixed k ≥ 1.Exact constant-depth simulations first place QACf and QTCf circuits in QNCf; arbitrary single-qubit gates can then be removed with an additive O(log log n) depth cost.Source: §7.3 · pp. 48–49

• The simulation targets bounded-error decision computation, and bounded-arity QUNC and QUNCf use a reusable real catalyst with additive O(log log(s/ε)) preparation depth.The proof outline separates wide-gate simulation from bounded-arity simulation using exact synthesis and a reusable real catalyst.Source: §8 · pp. 49–50
• Earlier real simulations encode real and imaginary amplitudes in a shared auxiliary system, which can force parallel nonreal gates to interact sequentially.The Pauli-transfer representation instead encodes density matrices by real Pauli coefficients.Source: §8 · pp. 49–50
• The Pauli-transfer representation enables locality-preserving real simulation of shallow circuits, with induced gate transformations acting only on corresponding label registers.This preserves the original circuit's locality and parallelism, unlike realification with one shared auxiliary register.Source: §8 · pp. 49–50
• The new ingredient is implementing induced Pauli-transfer transformations in Hadamard-only shallow models, including generalized Toffoli through a structured reflection and coherent agreement test.Fan-Out acts as a signed permutation of Pauli labels; Threshold circuits are handled through the Fan-Out model.Source: §8 · p. 50
• Theorem 12 simulates depth-d circuits in the listed universal–real circuit pairs using depth O(d + 1) and size poly(s, 1/ε).The theorem applies when s ≥ 2 bounds the original circuit's gate count and width.Source: §8 · p. 50

• A q-qubit density matrix's 4^q real Pauli coefficients are coherently stored as amplitudes on only 2q label qubits.The label pair for each original qubit jointly identifies I, Z, X, or Y; phase information is carried by real Pauli coefficients.Source: §8.1 · pp. 50–51
• A computational-basis input has a depth-one encoded preparation using Hadamards, and the designated output's acceptance probability can be read out with a constant-size QRNC0 circuit.The readout uses the output qubit's two Pauli-label qubits and one computational-basis measurement.Source: §8.1 · pp. 51–52
• Conjugation by a gate on r original qubits induces a real orthogonal transformation acting only on their 2r associated label qubits.Disjoint gates therefore remain disjoint in the encoded computation.Source: §8.1 · pp. 51–52
• The encoded Hadamard acts as a SWAP followed by CZ on its two label qubits.It exchanges the X and Z components and adds a minus sign to the Y label.Source: §8.1 · p. 52
• The encoded T gate acts trivially when a = 0 and applies Ry(π/2) to the b-label when a = 1.Thus the T gate's complex phase becomes a controlled real rotation on Pauli-label space.Source: §8.1 · pp. 52–53

• The encoded T action is a controlled Ry(π/2) rotation, and real rotations can be synthesized without reintroducing T-gates.The real-rotation construction replaces complex SELECT branches with branches from the Hadamard-only gate set; the dyadic block encoding, amplification, and Fan-Out compilation otherwise carry over.Source: §8.2 · pp. 53–54
• The real-rotation guarantee compares full data–ancilla isometries, so it remains valid with an arbitrary reference system entangled with the acted-on register.Fresh clean ancillae are used for each approximate primitive, and a telescoping hybrid bounds total error by the sum of individual errors.Source: §8.2 · p. 53
• The constant-depth real-rotation construction uses dyadic block encoding, oblivious amplitude amplification, and Fan-Out compilation, with the only additional primitives being small Fan-Out gates for interval predicates.Its ideal-Fan-Out implementation has clean-input error less than 9δ < η/2, and replacing Fan-Out yields a constant-depth QRAC implementation.Source: §8.2 · p. 54
• For QRNC, balanced CNOT and bounded-Toffoli trees implement copying, interval predicates, and reflections at depth O(log log(4/η)).This bounded-arity construction has poly(log(1/η)) size and ancillae.Source: §8.2 · p. 54
• For every η ∈ (0, 1/2), the encoded T action has clean-input operator error at most η with constant-depth QRAC implementation and poly(1/η) size and ancillae.The QRNC implementation has depth O(log log(4/η)) and poly(log(1/η)) size and ancillae.Source: §8.2 · p. 54

8.3 Fan-Out and Threshold Gates

• Exact encoded Fan-Out has a constant-depth QRNCf implementation using O(m^2) gates and clean ancillae.Its Pauli-transfer action permutes labels and attaches a sign; the label permutation uses Fan-Out and Hadamard-conjugated Parity.Source: §8.3 · p. 55
• The encoded Fan-Out sign is implemented exactly in constant depth by parallel CZ and CCZ phases on copied label bits, using O(m^2) gates and clean ancillae.The copies are uncomputed after the diagonal phases, and CCZ is Hadamard-conjugated ordinary Toffoli.Source: §8.3 · p. 55
• Fan-Out on m targets admits a constant-depth QRTC implementation with clean-input operator error at most η and poly(m, 1/η) gates and clean ancillae.The construction implements the required phase using Threshold gates and uses the Grier–Morris nekomata construction.Source: §8.3 · p. 56
• Depth O(d + 1) and polynomial size and ancillae suffice to simulate Threshold circuits in QRTC, with the same conclusion for circuits without Fan-Out.The construction replaces primitive Fan-Out gates with constant-depth approximations and bounds the resulting acceptance error.Source: §8.3 · pp. 56–57
• The reduction is asymmetric: eliminating Fan-Out uses general Threshold gates and therefore does not simulate QUAC by QRAC.The stronger gate-restricted simulation requires implementing encoded generalized Toffoli without general Threshold gates.Source: §8.3 · p. 57

8.4.1 Identifying the Pauli-Transfer Reflection

• The generalized CZ reflection leaves the first Pauli label unchanged and negates states characterized by local inactive-position checks and agreement of active Y-eigenvalues.If active labels disagree, paired buckets detect an opposite-label singleton pair with probability at least 1/32 when m ≤ B < 2m; the construction scans bucket counts and repeats tests to reduce misses.Source: §8.4.1 · pp. 59–60

8.4.2 Exact-One Tests and W-State Preparation

• EXACT1 tests identify singleton buckets, and W-state preparation assigns positions uniformly among buckets in superposition.The EXACT1 test has an exact constant-depth polynomial-size clean reversible implementation using QRAC gates and O(log(q))-Fan-Out; W-state preparation is compiled using real-rotation synthesis.Source: §8.4.2 · pp. 60–61

8.4.3 One-Hot Controlled SWAP

• An exact clean constant-depth QRAC circuit performs an enabled one-hot controlled SWAP, acting as identity when disabled and swapping the uniquely selected data qubit when enabled.This combines candidate swaps that share a target without executing them in parallel.Source: §8.4.3 · pp. 61–62

8.4.4 Parallel Encoding and Comparison of Y -Labels

• Orthogonal Y-eigenstates admit exact repetition encoding, and an enabled constant-depth comparison marks whether two labels disagree while acting trivially when disabled.The repetition encoding uses Fan-Out of width O(M).Source: §8.4.4 · pp. 62–63

8.4.5 Constructing the Encoded Reflection

• A constant-depth QRAC circuit implements encoded generalized Toffoli with size and clean-ancilla count poly(r, 1/η).The construction combines local inactive-position checks with a paired-bucket test for disagreement among active Y-labels.Source: §8.4.5 · p. 64
• For each bucket pair, singleton tests enable extraction and comparison of the two data qubits’ Y-eigenvalues, so a comparison bit witnesses opposite eigenvalues among active positions.Bucket assignments remain coherent, and repetition-encoded qubits let comparisons for different assignments run in parallel.Source: §8.4.5 · p. 64
• R = ⌈64 ln(4/η)⌉ repetitions are used per bucket count; each repetition detects an existing disagreement with probability at least 1/32 for a suitable bucket count.The sign can be wrong only if every repetition misses an existing disagreement; the resulting error analysis bounds the cleanup error.Source: §8.4.5 · p. 65
• All repetitions, bucket counts, and bucket pairs run in parallel, giving constant depth with ideal auxiliary gates and polynomial gate and ancilla counts.The required Fan-Out width is M = RL = O(log^2 N); data slots use O(r^2R) qubits.Source: §8.4.5 · p. 65
• The compiled implementation of OCZ_r has clean-input error at most η, and exact encoded Hadamard conjugation converts it to the encoded generalized Toffoli.The compilation error is bounded by η/2 using fresh clean ancillae for each replacement, including inverse occurrences.Source: §8.4.5 · p. 65

8.5 Completing the Real Circuit Simulation

• Encoded Hadamard and Pauli gates are exact, while encoded T and generalized Toffoli gates use clean-input approximations with fresh ancillae.The approximation guarantees apply even when the gate registers are entangled with the rest of the computation.Source: §8.5 · p. 65
• Depth O(d + 1) and polynomial size and ancilla counts suffice for the resulting QRAC simulation.Replacing disjoint gates uses separate label registers and ancillae, so each original layer incurs only constant-factor depth overhead.Source: §8.5 · p. 66
• The same depth and error bounds extend to QUACf circuits by exactly replacing each original Fan-Out with its encoded implementation.Auxiliary Fan-Out gates may remain as primitives in the target QRACf model.Source: §8.5 · p. 66

8.6 Bounded-Arity Circuits and Reusable Catalysts

• The earlier QUAC-to-QRAC construction does not preserve bounded arity because its encoded generalized Toffoli implementation itself requires generalized Toffoli gates.A bounded-arity source requires a separate construction exploiting the constant arity of every multiqubit gate.Source: §8.6 · p. 66
• Depth O(d + log log(s/ε)) and size poly(s, log(1/ε)) suffice for the bounded-arity real simulation, including circuits with primitive Fan-Out.The theorem applies to QUNC and QUNCf, with target classes QRNC and QRNCf, respectively.Source: §8.6 · pp. 66–67
• A bank of Hadamard-eigenstate catalysts is reused across layers to implement encoded T gates, making its nonconstant preparation depth additive rather than multiplicative in circuit depth.Each catalyst is returned unchanged by the controlled-H construction.Source: §8.6 · pp. 66–67
• The catalyst bank is prepared in parallel with joint state error at most ε/2, and unitary evolution preserves that initial Euclidean error during reuse.The final acceptance probability differs from the ideal encoded computation by at most ε.Source: §8.6 · p. 67

Real Fan-Out and Threshold Hierarchies

• For every depth bound D(n) ≥1, the real Fan-Out and Threshold hierarchies collapse to the corresponding standard and universal decision classes.The proof combines fixed-gate compilation, real simulation, and the inclusions among gate sets.Source: §8.7 · pp. 67–68

Real Generalized-Toffoli Hierarchy

• For every fixed k ≥0, QACk, QUACk, and QRACk have equal bounded-error decision power, including for the constant-depth Parity problem.Consequently, constant-depth Parity lower bounds against QAC suffice to address circuits using only H, X, and generalized Toffoli gates.Source: §8.7 · p. 68

Real Bounded-Arity Hierarchies

• When D(n) = Ω(log log n), bounded-arity real simulation preserves the asymptotic depth bound because its catalyst preparation costs O(log log n) depth.The bounded-arity Fan-Out hierarchy joins the wide-gate collapse at these depth bounds.Source: §8.7 · pp. 68–69

Constant-Depth Bounded-Arity Decision Classes

• For single-output constant-depth bounded-arity decision, QNC0 = QUNC0 = QRNC0 follows from the output's constant-size backward light cone.The resulting function of constantly many input bits can be computed exactly by a constant-size reversible circuit.Source: §8.7 · p. 68
• The constant-depth bounded-arity equality concerns single-output decision classes, not full-state, unitary, or joint-output-distribution simulation.The separate constant-depth result does not follow from the real simulation, whose catalyst preparation has nonconstant depth.Source: §8.7 · pp. 68–69

Full Real Fan-Out Hierarchy

• For bounded-arity circuits with Fan-Out, the section establishes collapse only when D(n) = Ω(log log n), not at constant depth.Primitive Fan-Out can give one output qubit a polynomial-size backward light cone, so the constant-size truth-table argument does not apply.Source: §8.7 · p. 69

9.1 The Structured Fourier Hierarchy

• A structured Fourier circuit alternates partial Hadamard layers with phase layers built from permitted Boolean block functions on pairwise-disjoint blocks.Parallel diagonal gates combine their Boolean phase functions by XOR; the named phase families retain the multi-qubit gate restrictions of the shallow-depth hierarchy.Source: §9.1 · pp. 70–71
• Real shallow-depth circuit models correspond exactly to structured Fourier circuits over their paired phase families, with O(d + 1) phase layers in either conversion.The conversions preserve the unitary exactly and have polynomial cost in width and description length.Source: §9.1 · p. 72, Table 3 · p. 72
• For standard and universal circuit models, structured Fourier representations preserve designated-output acceptance probability within ε using O(d + 1) or O(d + log log(s/ε)) phase layers, respectively.The standard-model representations have polynomial size and width; the universal-model bounds include the additive log-log term.Source: §9.1 · p. 73

The Fan-Out and Threshold families satisfy

• The Fan-Out and Threshold families satisfy the stated hierarchy equalities for every D(n) ≥1, while the bounded-arity Fan-Out collapse requires D(n) = Ω(log log n).Without Fan-Out, the separate constant-depth QNC0 result is only a single-output decision equality and does not extend to arbitrary positive depths.Source: The Fan-Out and Threshold families… · p. 73

9.2 From Structured Fourier Circuits to Forrelation

• A scalar Forrelation instance can encode a structured Fourier circuit's designated-output acceptance bias using O(d + 1) phase functions from the same restricted family.The full-Hadamard conversion preserves the allowed phase family; only the first and last phase functions depend on the input, through addition of a linear function.Source: §9.2 · p. 74
• For standard circuit models, each input determines a scalar Forrelation value within 2ε of the circuit's acceptance-bias expression, using polynomial width and phase-list size.The lists derive from one fixed list by adding the input-dependent linear term to its first and last phases.Source: §9.2 · p. 75
• The QAC0 Parity question becomes a constant-gap sign condition on circuit-generated Forrelation values with disjoint AND blocks.At each input length, the circuit and nonlinear blocks are fixed, while the input enters only through the two boundary phase layers.Source: §9.2 · p. 75