Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2.4.1: independent repetition and majority amplification

Open
QAlgorithms.Papers.Independent.Intakethird100.P03.amplification

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Suppose a QQQ circuit on a classical input computes a promised mmm-bit function with worst-case error at most 0<ϵ<1/20<\epsilon<1/20<ϵ<1/2. Repeat it r>0r>0r>0 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 rrr and the original circuit and register sizes. Its output law is exactly that of independent original outcomes followed by majority. For every valid input,

Pr⁡[error or failure]≤∑2j≥r(rj)ϵj(1−ϵ)r−j≤λr,λ=2ϵ(1−ϵ)<1.\Pr[\text{error or failure}]\le\sum_{2j\ge r}\binom rj\epsilon^j(1-\epsilon)^{r-j}\le\lambda^r, \qquad\lambda=2\sqrt{\epsilon(1-\epsilon)}<1.Pr[error or failure]≤2j≥r∑​(jr​)ϵj(1−ϵ)r−j≤λr,λ=2ϵ(1−ϵ)​<1.

For every polynomial t(n)t(n)t(n) and fixed ϵ\epsilonϵ, a polynomially bounded positive repetition count makes λr(n)≤e−t(n)\lambda^{r(n)}\le e^{-t(n)}λr(n)≤e−t(n).

The majority computation and fresh work are charged; the construction copies classical inputs and does not clone quantum states.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
Formal statement
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
Source
Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026v1, PDF p. 11, §2.4.1: independent repetition and majority amplification
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

Define a(ϵ)=2ϵ(1−ϵ)a(\epsilon)=2\sqrt{\epsilon(1-\epsilon)}a(ϵ)=2ϵ(1−ϵ)​ and

B(r,ϵ)=∑0≤j≤rr≤2j(rj)ϵj(1−ϵ)r−j,B(r,\epsilon)= \sum_{\substack{0\le j\le r\\r\le 2j}} \binom rj\epsilon^j(1-\epsilon)^{r-j},B(r,ϵ)=0≤j≤rr≤2j​∑​(jr​)ϵj(1−ϵ)r−j,

so the sum includes j=r/2j=r/2j=r/2 when rrr is even. The theorem asserts the conjunction of the following two statements. First, there exists a polynomial ppp with natural-number coefficients such that, for every n,m,w∈Nn,m,w\in\mathbb Nn,m,w∈N, every circuit ccc on n+wn+wn+w qubits whose gates are arbitrary unitary one-qubit gates, controlled-NOT gates, or three-qubit Toffoli gates, every output-wire injection o:{0,…,m−1}↪{0,…,n+w−1}o:\{0,\ldots,m-1\}\hookrightarrow\{0,\ldots,n+w-1\}o:{0,…,m−1}↪{0,…,n+w−1}, every set NNN of nnn-bit strings, every function FFF from nnn-bit strings to mmm-bit strings, and every real 0<ϵ<1/20<\epsilon<1/20<ϵ<1/2, suppose that, for every x∈Nx\in Nx∈N, the sum of squared output amplitudes of ccc, started in ∣x,0w⟩|x,0^w\rangle∣x,0w⟩, over strings whose restriction to ooo equals F(x)F(x)F(x), is at least 1−ϵ1-\epsilon1−ϵ. Then, for every natural r>0r>0r>0, there exist W∈NW\in\mathbb NW∈N, a circuit cmajc_{\mathrm{maj}}cmaj​ over the same gate set on n+Wn+Wn+W qubits, and an injection omajo_{\mathrm{maj}}omaj​ selecting m+1m+1m+1 output wires, such that both the number of gates in cmajc_{\mathrm{maj}}cmaj​ and WWW are at most p(r(n+m+w+∣c∣+1))p(r(n+m+w+|c|+1))p(r(n+m+w+∣c∣+1)); for every nnn-bit input xxx and every (m+1)(m+1)(m+1)-bit output yyy, its output weight at yyy equals

∑(si)i<r1{maj⁡(si)=y}∏i<r(∑z: z∘o=si∣(Uc∣x,0w⟩)z∣2),\sum_{(s_i)_{i<r}} \mathbf 1_{\{\operatorname{maj}(s_i)=y\}} \prod_{i<r} \left(\sum_{z:\,z\circ o=s_i}|(U_c|x,0^w\rangle)_z|^2\right),(si​)i<r​∑​1{maj(si​)=y}​i<r∏​(z:z∘o=si​∑​∣(Uc​∣x,0w⟩)z​∣2),

where maj⁡(si)\operatorname{maj}(s_i)maj(si​) is the unique strictly-majority mmm-bit string followed by true, or 0m0^m0m followed by false if no strict majority exists; for every x∈Nx\in Nx∈N, the output weight at F(x)F(x)F(x) followed by true is at least 1−B(r,ϵ)1-B(r,\epsilon)1−B(r,ϵ); and B(r,ϵ)≤a(ϵ)rB(r,\epsilon)\le a(\epsilon)^rB(r,ϵ)≤a(ϵ)r and a(ϵ)<1a(\epsilon)<1a(ϵ)<1. Here circuit matrices apply the listed gates in order, each gate acting on its injected wires and leaving the other bits unchanged, and ∣c∣|c|∣c∣ is the list length. The equality of output weights holds also for inputs outside NNN; NNN may be empty, and n,m,wn,m,wn,m,w may be zero whenever the required injections exist. Second, for every real 0<ϵ<1/20<\epsilon<1/20<ϵ<1/2 and every polynomial ttt with natural-number coefficients, there exist a function R:N→NR:\mathbb N\to\mathbb NR:N→N and a polynomial ppp with natural-number coefficients such that, for every n∈Nn\in\mathbb Nn∈N, including n=0n=0n=0,

0<R(n),R(n)≤p(n),a(ϵ)R(n)≤exp⁡(−t(n)).0<R(n),\qquad R(n)\le p(n),\qquad a(\epsilon)^{R(n)}\le \exp(-t(n)).0<R(n),R(n)≤p(n),a(ϵ)R(n)≤exp(−t(n)).
Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me