Circuits over the fixed gate set preserve total probability
ProvedOAI.ExactQuantumFactoring.outputState_normSq_sumLet be any circuit over the fixed alphabet of gates: NOT, CNOT, Toffoli, Hadamard and the phase gate , each optionally inverted and optionally given one extra control. Then for every input length and integer , the output state satisfies
Each gate matrix is unitary on its wires, and acting on distinct wires while fixing all other wires gives a unitary on the full space. Products of unitaries preserve the norm, and the initial basis vector has norm . Consequently, success probability exactly is equivalent to zero amplitude on every incorrect output.
Formalization Note Circuits, gates, the output state, the output decoding outputList and CorrectEncoding are those of the published definition ExactQuantumFactoring. A basis state is a function from wires to Booleans, and the output state is a complex vector indexed by basis states.
import Mathlib import Definitions.Def_ExactQuantumFactoring namespace OAI namespace ExactQuantumFactoring open scoped BigOperators
/-- **Circuits preserve total probability.** Every circuit over the fixed 20-gate alphabet acts
unitarily, so the output state on any classical input has total squared amplitude `1`. -/
theorem outputState_normSq_sum (c : Circuit) (ℓ N : ℕ) :
∑ x : Basis c.qubits, Complex.normSq (c.outputState ℓ N x) = 1 := by
sorry
end ExactQuantumFactoring
end OAI