Theorem 13 — constant-depth QRAC approximation of encoded generalized Toffoli
OpenDepthOptQC.Synth.Supplement.theorem_13p2o-gran-per-chapterp2o-plan-paperp2o-v1pauli-transfer-matrixquantum-circuitsquantum-information
There are uniform constants and such that, for every and , a QRAC circuit of depth at most acts on the Pauli-label qubits and fresh clean ancillas, with size and at most , and satisfies
Here acts on physical qubits with controls, and .
The theorem approximates the real Pauli-transfer action, not the physical Toffoli matrix.
Differences from the source:
- reading: constant depth and → uniform witnesses chosen before ; reason: explicit asymptotic quantifiers
- encoding: adjacent label pairs → all labels followed by all labels; reason: a fixed permutation of the same qubits
- encoding: a supremum over the unit sphere → a bound for every unit vector; reason: these are equivalent, and the universal form avoids introducing a totalized real supremum
Preamble
import Definitions.Def_DepthOptQC_Synth_Supplement_pauliTransfer set_option autoImplicit false
Formal statement
namespace DepthOptQC.Synth.Supplement
open QAlgorithms DepthOptQC.Synth
/-- **Theorem 13 (Encoded Generalized Toffoli)** — Vasconcelos, arXiv:2609.34659, p.63,
Eq. (306). The Pauli-transfer action of the `r`-qubit generalized Toffoli has a constant-depth,
polynomial-size clean QRAC approximation, including `r=1`, where the physical gate is `X`.
**Formalization Note.** The input has `2r` Pauli-label qubits; this is not an approximation of the
physical `r`-qubit Toffoli matrix. No global phase is allowed in the displayed clean-input bound. -/
theorem theorem_13 :
∃ K : ℝ, 0 < K ∧ ∃ k : ℕ,
∀ r : ℕ, (hr : 0 < r) → ∀ η : ℝ, 0 < η → η < 1 / 2 →
∃ A : ℕ, ∃ Otilde : LayeredCircuit qracGateSet ((r + r) + A),
(Otilde.depth : ℝ) ≤ K ∧
(Otilde.size : ℝ) ≤ K * ((r : ℝ) + 1 / η) ^ k ∧
(A : ℝ) ≤ K * ((r : ℝ) + 1 / η) ^ k ∧
∀ φ : EuclideanSpace ℂ (Qubits (r + r)), ‖φ‖ = 1 →
‖act Otilde.unitary (zeroAncillaVec φ A) -
zeroAncillaVec (act (generalizedToffoliTransfer r hr) φ) A‖ ≤ η := by sorry
end DepthOptQC.Synth.Supplement
Source
Vasconcelos, Depth-Optimal Quantum Compilation, arXiv:2609.34659, Theorem 13, p.63 (PDF p.65), Eq. (306)