Uniform finite circuits, bit computation, spectral reductions and conditional marginals
DefinitionTFIMPhaseDiagram_Classical_Supplement_computationBinary words encode integers by a self-delimiting length and binary payload, rationals by sign, numerator and denominator, and dense symmetric-matrix inputs in row order. Classical bit computation uses actual finite multistack machines with step-count witnesses from Mathlib, on the same binary languages as the published and definitions. The local has polynomially many unbiased random bits, a polynomial-time machine, no false acceptance and acceptance probability at least on members.
A finite quantum program is a list of addressed gates. Execution multiplies the actual embedded gate matrices in execution order on the zero basis state, then traces out workspace qubits. All gates, output qubits and ancillas are charged, separately from classical generation; invalid decoded instructions are identity. For the real-arithmetic formulation, the published charged RAM prints such a circuit in its natural registers. The averaged state is an entrywise integral of its actual reduced density matrices, with integrability required by the preparation predicate. For the bit formulation, an actual multistack machine prints a self-delimiting circuit code. Computational-basis measurement and rational output decoding define the approximation success probability.
The spectral promise is for symmetric , , with target . A hardness witness supplies two polynomial-time query printers and a polynomial-time decision postprocessor for every binary language, correct on every pair of accurate answers. Rational inputs witness hardness of the real problem; the constant-bit restriction also requires zero diagonal.
For Theorem 34, partial assignments are functions to optional bits, where absence means an unassigned spin. Their diagonal projectors equal the source products, including the identity for the empty assignment. The bundle uses the actual half exponential and
A marginal estimator is an executed finite-bit machine on every partial pair and every padded random tape, with nonnegative estimates, the exact source relative accuracy and failure . Circuit generation takes unary resource bounds so its polynomial time is charged in those bounds. Arbitrary real target accuracies are passed through a logarithmic binary precision index without restricting their domain. The source's even Trotter mesh is defined exactly, using .
import Definitions.Def_TFIMPhaseDiagram_Classical_ram
import Definitions.Def_TFIMPhaseDiagram_Classical_traceSetup
import Definitions.Def_PvsNP
import Definitions.Def_ShiBQP_Core
set_option autoImplicit false
open MeasureTheory
open scoped BigOperators
noncomputable section
namespace TFIMPhaseDiagram.Classical.Supplement
attribute [local instance] Classical.propDecidable
abbrev Word := List Bool
/-- Self-delimiting binary integers: unary length, separator, binary payload. -/
def natCode (n : ℕ) : Word := List.replicate (Nat.bits n).length true ++ [false] ++ Nat.bits n
def readNat (w : Word) : ℕ × Word :=
let k := (w.takeWhile id).length
((((w.drop (k+1)).take k).foldr (fun b a => (if b then 1 else 0)+2*a) 0), w.drop (2*k+1))
def readNats : ℕ → Word → List ℕ
| 0, _ => []
| k+1, w => if w = [] then [] else (readNat w).1 :: readNats k (readNat w).2
def ratCode (q : ℚ) : Word := (decide (q < 0)) :: (natCode q.num.natAbs ++ natCode q.den)
def readRat (w : Word) : ℚ × Word :=
let p := readNat (w.drop 1)
let q := readNat p.2
((if w.headD false then -1 else 1) * (p.1 : ℚ) / max 1 q.1, q.2)
def estimate (w : Word) : ℝ := (readRat w).1
def pairCode (p : Word × Word) : Word :=
List.replicate p.1.length true ++ [false] ++ p.1 ++ p.2
/-- Runtime is supplied by an actual finite multistack machine, not by a free cost label. -/
abbrev BitMachine (f : Word → Word) :=
Turing.TM2ComputableInTime (id : Word → Word) (id : Word → Word) f
def PolyTimeWords (f : Word → Word) : Prop := PvsNP.PolyTimeComputable f
/-- Raw Clifford+T circuit code: (0,i,_) is H_i, (1,i,_) is T_i,
(2,i,j) is CNOT(i,j). Invalid addresses/tags act as identity. This total decoder
never produces a nonunitary gate or postselection. -/
structure FiniteCircuit where
ancillas : ℕ
gates : List (ℕ × ℕ × ℕ)
def triples : List ℕ → List (ℕ × ℕ × ℕ)
| a :: i :: j :: rest => (a,i,j) :: triples rest
| _ => []
def circuitDecode (w : Word) : FiniteCircuit :=
let p := readNat w
⟨p.1, triples (readNats p.2.length p.2)⟩
def circuitCode (c : FiniteCircuit) : Word :=
natCode c.ancillas ++ c.gates.flatMap (fun g => natCode g.1 ++ natCode g.2.1 ++ natCode g.2.2)
def singleGate {m : ℕ} (U : Matrix Bool Bool ℂ) (i : Fin m) : QMat m :=
fun y z => if ∀ j, j ≠ i → y j = z j then U (y i) (z i) else 0
def gateMatrix (m : ℕ) (g : ℕ × ℕ × ℕ) : QMat m :=
if hi : g.2.1 < m then
let i : Fin m := ⟨g.2.1,hi⟩
if g.1 = 0 then singleGate QAlgorithms.hadamard i
else if g.1 = 1 then singleGate QAlgorithms.gateT i
else if hj : g.2.2 < m then
let j : Fin m := ⟨g.2.2,hj⟩
if g.1 = 2 ∧ i ≠ j then
fun y z => if y = Function.update z j (xor (z j) (z i)) then 1 else 0
else 1
else 1
else 1
def circuitUnitary (n : ℕ) (c : FiniteCircuit) : QMat (n+c.ancillas) :=
(c.gates.map (gateMatrix (n+c.ancillas))).reverse.prod
def circuitAmplitude (n : ℕ) (c : FiniteCircuit) (z : Bits (n+c.ancillas)) : ℂ :=
circuitUnitary n c z (fun _ => false)
/-- Actual execution on |0...0>, followed by tracing out all workspace qubits. -/
def circuitDensity (n : ℕ) (c : FiniteCircuit) : QMat n :=
fun x y => ∑ a : Bits c.ancillas,
circuitAmplitude n c (Fin.append x a) * star (circuitAmplitude n c (Fin.append y a))
def circuitCost (n : ℕ) (c : FiniteCircuit) : ℕ := n+c.ancillas+c.gates.length
def bitList {n : ℕ} (x : Bits n) : Word := (List.finRange n).map x
/-- A deterministic classical compiler prints a finite circuit; its output register
is measured in the computational basis, then decoded as a rational number. -/
def quantumEstimateProbability (code : Word) (A : ℝ → Prop) : ℝ :=
let p := readNat code
let n := p.1
let c := circuitDecode p.2
∑ x : Bits n, if A (estimate (bitList x)) then (circuitDensity n c x x).re else 0
/-- Uniform one-sided randomized polynomial time over the same languages as PvsNP.NP. -/
def RP : Set (Language Bool) :=
{L | ∃ (f : Word → Word) (p : Polynomial ℕ), PolyTimeWords f ∧ ∀ w : Word,
let R := p.eval w.length
(w ∈ L → (2:ℝ)/3 ≤ (∑ ω : Bits R,
if (f (pairCode (w,bitList ω))).headD false then (1:ℝ) else 0) / 2^R) ∧
(w ∉ L → ∀ ω : Bits R, (f (pairCode (w,bitList ω))).headD false = false)}
structure RationalInstance where
n : ℕ
J : Matrix (Fin n) (Fin n) ℚ
def instanceCode (I : RationalInstance) : Word :=
natCode I.n ++ (List.finRange I.n).flatMap (fun i =>
(List.finRange I.n).flatMap (fun j => ratCode (I.J i j)))
def realJ (I : RationalInstance) : Matrix (Fin I.n) (Fin I.n) ℝ := fun i j => I.J i j
def spectralPromise (η b' : ℝ) (I : RationalInstance) : Prop :=
0 < I.n ∧ (realJ I).IsSymm ∧ η / Real.tanh η < spectralWidth (realJ I) ∧
spectralWidth (realJ I) < b'
def spectralTarget (η : ℝ) (I : RationalInstance) : ℂ :=
partition (realJ I) (fun _ => 0) (fun _ => η)
def goodSpectralAnswer (η c : ℝ) (I : RationalInstance) (w : Word) : Prop :=
ExpApprox (c*I.n) (estimate w) (spectralTarget η I)
def rationalBits (q : ℚ) : ℕ := (Nat.bits q.num.natAbs).length + (Nat.bits q.den).length + 1
def constantBitPromise (B : ℕ) (I : RationalInstance) : Prop :=
(∀ i, I.J i i = 0) ∧ ∀ i j, rationalBits (I.J i j) ≤ B
/-- Concrete nonadaptive two-query polynomial-time approximation reduction.
The query printers and decision postprocessor are genuine bit machines. Every
accurate pair of replies must decide the input, not just a favorable oracle. -/
def ApproxNPHard (η b' c : ℝ) (restriction : RationalInstance → Prop) : Prop :=
∀ L : Language Bool, L ∈ PvsNP.NP →
∃ (Q₁ Q₂ : Word → RationalInstance) (D : Word → Word),
Nonempty (Turing.TM2ComputableInPolyTime (id : Word → Word) instanceCode Q₁) ∧
Nonempty (Turing.TM2ComputableInPolyTime (id : Word → Word) instanceCode Q₂) ∧
PolyTimeWords D ∧
(∀ w, spectralPromise η b' (Q₁ w) ∧ restriction (Q₁ w) ∧
spectralPromise η b' (Q₂ w) ∧ restriction (Q₂ w)) ∧
∀ w a₁ a₂, goodSpectralAnswer η c (Q₁ w) a₁ → goodSpectralAnswer η c (Q₂ w) a₂ →
(w ∈ L ↔ (D (pairCode (w,pairCode (a₁,a₂)))).headD false = true)
def RandomizedSpectralSolver (η b' c : ℝ) (restriction : RationalInstance → Prop) : Prop :=
∃ (f : Word → Word) (p : Polynomial ℕ), PolyTimeWords f ∧
∀ I, spectralPromise η b' I → restriction I →
let R := p.eval (instanceCode I).length
(2:ℝ)/3 < (∑ ω : Bits R,
if goodSpectralAnswer η c I (f (pairCode (instanceCode I,bitList ω))) then (1:ℝ) else 0) / 2^R
def quantumWordCost (code : Word) : ℕ :=
let p := readNat code
p.1 + (circuitDecode p.2).ancillas + (circuitDecode p.2).gates.length
def QuantumSpectralSolver (η b' c : ℝ) (restriction : RationalInstance → Prop) : Prop :=
∃ (f : Word → Word) (C d : ℕ), PolyTimeWords f ∧
(∀ w, quantumWordCost (f w) ≤ C*(1+w.length)^d) ∧
∀ I, spectralPromise η b' I → restriction I →
(2:ℝ)/3 < quantumEstimateProbability (f (instanceCode I))
(fun a => ExpApprox (c*I.n) a (spectralTarget η I))
/-- Ancilla and gate counts are charged as well as classical generation. The real
compiler is the published finite RAM, whose natural registers contain a circuit. -/
def ramCircuit (P : RAMProgram) (input : List ℝ) (budget : ℕ)
(ω : MatMulTimeLP.Tape) : FiniteCircuit :=
let s := ramState P input ω budget
⟨s.N 0, (List.range (s.N 1)).map (fun j => (s.N (3*j+2),s.N (3*j+3),s.N (3*j+4)))⟩
def quantumInput {n : ℕ} (J : Matrix (Fin n) (Fin n) ℝ) (h η : Fin n → ℝ) (e : ℝ) : List ℝ :=
[(n:ℝ),e] ++ MatMulTimeLP.matToList J ++ MatMulTimeLP.vecToList h ++ MatMulTimeLP.vecToList η
def averagedRAMState (n : ℕ) (P : RAMProgram) (input : List ℝ) (budget : ℕ) : QMat n :=
fun x y => ∫ ω, circuitDensity n (ramCircuit P input budget ω) x y ∂MatMulTimeLP.tapeLaw
def PreparesReal {n : ℕ} (P : RAMProgram) (input : List ℝ) (B : ℕ) (ρ : QMat n) (e : ℝ) : Prop :=
Admissible P ∧ HaltsWithin P input B ∧
(∀ ω, circuitCost n (ramCircuit P input B ω) ≤ B) ∧
(∀ x y, Integrable (fun ω => circuitDensity n (ramCircuit P input B ω) x y) MatMulTimeLP.tapeLaw) ∧
schattenOne (averagedRAMState n P input B - ρ) ≤ e
def prepBudget {n : ℕ} (C d : ℕ) (J : Matrix (Fin n) (Fin n) ℝ)
(h η : Fin n → ℝ) (e : ℝ) : ℕ :=
C * ⌈(1+n+maxEntry J+maxField h+maxField η+e⁻¹)^d⌉₊
def precisionBits (e : ℝ) : ℕ := ⌈Real.log (1/e) / Real.log 2⌉₊+1
def rationalInput {n : ℕ} (J : Matrix (Fin n) (Fin n) ℚ) (h η : Fin n → ℚ) (k : ℕ) : Word :=
natCode n ++ natCode k ++ (List.finRange n).flatMap (fun i =>
(List.finRange n).flatMap (fun j => ratCode (J i j))) ++
(List.finRange n).flatMap (fun i => ratCode (h i) ++ ratCode (η i))
def inputBitsBound {n : ℕ} (b : ℕ) (J : Matrix (Fin n) (Fin n) ℚ) (h η : Fin n → ℚ) : Prop :=
(∀ i j, rationalBits (J i j) ≤ b) ∧ (∀ i, rationalBits (h i) ≤ b ∧ rationalBits (η i) ≤ b)
/-- Empty spins are genuinely unassigned; no conditioning on zero mass is assumed. -/
abbrev PartialSpins (n : ℕ) := Fin n → Option Bool
def partialProjector {n : ℕ} (a : PartialSpins n) : QMat n :=
Matrix.diagonal (fun x => if ∀ i, ∀ v, a i = some v → x i = v then 1 else 0)
def gibbsOf {n : ℕ} (H : QMat n) : QMat n :=
(Matrix.trace (matrixExp H))⁻¹ • matrixExp H
def halfExponential {n : ℕ} (H R : QMat n) : QMat n := matrixExp ((1/2:ℂ) • (H+R))
def marginal {n : ℕ} (H R : QMat n) (l r : PartialSpins n) : ℝ :=
let U := halfExponential H R
(Matrix.trace (partialProjector l * U * partialProjector r * U) / Matrix.trace (U*U)).re
def partialCode {n : ℕ} (a : PartialSpins n) : Word :=
(List.finRange n).flatMap (fun i =>
match a i with
| none => [false,false]
| some false => [true,false]
| some true => [true,true])
def estimatorInput {n : ℕ} (l r : PartialSpins n) (ω : Word) : Word :=
natCode n ++ partialCode l ++ partialCode r ++ ω
/-- The finite-precision estimator promised in footnote 14. Every random tape
and every pair of partial configurations is executed by the supplied bit machine. -/
def MarginalEstimator {n : ℕ} (f : Word → Word) (M : BitMachine f) (T R : ℕ)
(H A : QMat n) (e : ℝ) : Prop :=
R ≤ T ∧ (∀ l r : PartialSpins n, ∀ ω : Bits R,
M.time (estimatorInput l r (bitList ω)).length ≤ T ∧
0 ≤ estimate (f (estimatorInput l r (bitList ω)))) ∧
∀ l r : PartialSpins n,
1-e/(16*4^n) ≤ (∑ ω : Bits R,
if ExpApprox (e^2/(256*n)) (estimate (f (estimatorInput l r (bitList ω))))
(marginal H A l r) then (1:ℝ) else 0) / 2^R
def compilerInput (n T R k : ℕ) : Word :=
List.replicate n true ++ [false] ++ List.replicate T true ++ [false] ++
List.replicate R true ++ [false] ++ List.replicate k true
/-- Exact source proof parameters, including the even mesh and zero-safe error allocations. -/
def bridgeAccuracy (n : ℕ) (e : ℝ) : ℝ := e^2/(256*n)
def bridgeFailure (n : ℕ) (e : ℝ) : ℝ := e/(16*4^n)
def prepMesh {n : ℕ} (J : Matrix (Fin n) (Fin n) ℝ) (h η : Fin n → ℝ) (e : ℝ) : ℕ :=
let c := rowNorm J + maxField h + maxField η + 1
let ε := bridgeAccuracy n e
2 * ⌈500 * max ((n:ℝ)*c^2/ε) (Real.rpow ((n:ℝ)*c/ε) (3/2))⌉₊
end TFIMPhaseDiagram.Classical.Supplement