§2.4.1: independent repetition and majority amplification
OpenQAlgorithms.Papers.Independent.Intakethird100.P03.amplificationSuppose a circuit on a classical input computes a promised -bit function with worst-case error at most . Repeat it times on fresh memories with the same classical input, and return a strict majority, flagging the absence of a majority as failure. This computation has a circuit with gate count and work bounded by one polynomial in and the original circuit and register sizes. Its output law is exactly that of independent original outcomes followed by majority. For every valid input,
For every polynomial and fixed , a polynomially bounded positive repetition count makes .
The majority computation and fresh work are charged; the construction copies classical inputs and does not clone quantum states.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
noncomputable section
open scoped Matrix ComplexConjugate Kronecker
namespace QAlgorithms.Papers.Independent.Intakethird100.P03
open QAlgorithms.Papers.Independent.Renew46.P01 (cleanVector)
attribute [local instance] Classical.propDecidable
/-- PDF p.11: independent repetition and charged majority computation, the explicit
binomial/exponential bound, and polynomial overhead for exp(-poly(n)) error. -/
theorem amplification :
(∃ p : Polynomial ℕ, ∀ (n m w : ℕ) (c : Circuit kitaevGateBasis (n + w))
(out : Fin m ↪ Fin (n + w)) (N : Set (Qubits n)) (F : Qubits n → Qubits m)
(epsilon : ℝ), 0 < epsilon → epsilon < 1 / 2 →
Computes c.unitary out N F epsilon → ∀ r : ℕ, 0 < r →
∃ (W : ℕ) (cmajority : Circuit kitaevGateBasis (n + W)) (outmajority : Fin (m + 1) ↪ Fin (n + W)),
cmajority.size ≤ p.eval (r * (n + m + w + c.size + 1)) ∧
W ≤ p.eval (r * (n + m + w + c.size + 1)) ∧
(∀ x y, probEvent (act cmajority.unitary (inputState x W))
(fun z => z ∘ outmajority = y) = repeatedMajorityLaw c.unitary out r x y) ∧
(∀ x ∈ N, 1 - majorityTail r epsilon ≤
probEvent (act cmajority.unitary (inputState x W))
(fun z => z ∘ outmajority = Fin.snoc (F x) true)) ∧
majorityTail r epsilon ≤ amplificationRate epsilon ^ r ∧
amplificationRate epsilon < 1) ∧
(∀ epsilon : ℝ, 0 < epsilon → epsilon < 1 / 2 → ∀ t : Polynomial ℕ,
∃ (R : ℕ → ℕ) (p : Polynomial ℕ), ∀ n : ℕ,
0 < R n ∧ R n ≤ p.eval n ∧
amplificationRate epsilon ^ R n ≤ Real.exp (-((t.eval n : ℕ) : ℝ))) := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Define and
so the sum includes when is even. The theorem asserts the conjunction of the following two statements. First, there exists a polynomial with natural-number coefficients such that, for every , every circuit on qubits whose gates are arbitrary unitary one-qubit gates, controlled-NOT gates, or three-qubit Toffoli gates, every output-wire injection , every set of -bit strings, every function from -bit strings to -bit strings, and every real , suppose that, for every , the sum of squared output amplitudes of , started in , over strings whose restriction to equals , is at least . Then, for every natural , there exist , a circuit over the same gate set on qubits, and an injection selecting output wires, such that both the number of gates in and are at most ; for every -bit input and every -bit output , its output weight at equals
where is the unique strictly-majority -bit string followed by true, or followed by false if no strict majority exists; for every , the output weight at followed by true is at least ; and and . Here circuit matrices apply the listed gates in order, each gate acting on its injected wires and leaving the other bits unchanged, and is the list length. The equality of output weights holds also for inputs outside ; may be empty, and may be zero whenever the required injections exist. Second, for every real and every polynomial with natural-number coefficients, there exist a function and a polynomial with natural-number coefficients such that, for every , including ,
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.