Theorem 12 — depth-preserving real decision simulation
OpenDepthOptQC.Synth.Supplement.theorem_12computational-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationreal-quantum-circuits
Uniform constants and work simultaneously for the four model pairs
If is a depth- circuit in the universal member of a pair and bounds both its gate count and width, then for every there is a circuit in the corresponding real class with depth at most and size at most , such that
for every classical input .
This result preserves the designated-output decision probability; it does not claim operator-norm approximation of the original complex unitary.
Differences from the source:
- reading: and → uniform witnesses shared by all four finite model pairs; reason: explicit meaning of the printed asymptotics
- encoding: circuit class notation → exact layered gate alphabets, fresh zero workspace and a designated output field; reason: operational expansion of Definitions 1–3 and Eq. (1)
Preamble
import Definitions.Def_DepthOptQC_Synth_Supplement_CircuitModel set_option autoImplicit false
Formal statement
namespace DepthOptQC.Synth.Supplement
open QAlgorithms
/-- **Theorem 12 (Depth-Preserving Real Decision Simulation)** — Vasconcelos,
arXiv:2609.34659, p.49, Eq. (230). Each of QUAC, QUACf, QUTC and QUTCf has an acceptance-preserving
simulation in the corresponding real model QRAC, QRACf, QRTC or QRTCf, with constant-factor depth
and polynomial size.
**Formalization Note.** `WideModel` indexes all four pairs. The compiled circuit is selected before
the classical input; only designated-output acceptance probability, not the full unitary, is
approximated. -/
theorem theorem_12 :
∃ K : ℝ, 0 < K ∧ ∃ k : ℕ,
∀ (M : WideModel) (n d s : ℕ) (C : DecisionCircuit (universalWideGateSet M) n),
2 ≤ s → C.depth = d → C.size ≤ s → C.width ≤ s →
∀ ε : ℝ, 0 < ε → ε < 1 / 2 →
∃ Ctilde : DecisionCircuit (realWideGateSet M) n,
(Ctilde.depth : ℝ) ≤ K * (d + 1) ∧
(Ctilde.size : ℝ) ≤ K * ((s : ℝ) + 1 / ε) ^ k ∧
∀ x : Qubits n, |Ctilde.acceptance x - C.acceptance x| ≤ ε := by sorry
end DepthOptQC.Synth.Supplement
Source
Vasconcelos, Depth-Optimal Quantum Compilation, arXiv:2609.34659, Theorem 12, p.49 (PDF p.51), Eq. (230)