Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§1 example 2: discrete logarithm from a rank-two stabilizer

Open
QAlgorithms.Papers.Independent.Intakethird100.P03.discrete_log_reduction

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

prove2quantum

Let qqq be prime, let ζ\zetaζ generate the unit group modulo qqq, and let ggg be a unit. Suppose an integer basis BBB is supplied for

P={(u,v)∈Z2:ζugv=1}.P=\{(u,v)\in\mathbb Z^2:\zeta^u g^v=1\}.P={(u,v)∈Z2:ζugv=1}.

One classical procedure, polynomial in the binary input length and chosen before q,ζ,g,Bq,\zeta,g,Bq,ζ,g,B, returns an integer mmm such that

0≤m<q−1,(m,−1)∈P,ζm=g.0\le m<q-1,\qquad (m,-1)\in P,\qquad \zeta^m=g.0≤m<q−1,(m,−1)∈P,ζm=g.

For q=2q=2q=2, the representative is necessarily zero. This identifies the exact information extracted from a stabilizer basis.

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.4, example 2: one classical polynomial-time procedure extracts m modulo q-1
from a basis of P, with (m,-1) in P and zeta^m=g. q=2 returns the representative zero. -/
theorem discrete_log_reduction :
    ∃ extract : List Bool → List Bool, QAlgorithms.Complexity.PolyTimeComputable extract ∧
      ∀ (q : ℕ), Nat.Prime q → ∀ (zeta g : (ZMod q)ˣ), orderOf zeta = q - 1 →
      ∀ B : Matrix (Fin 2) (Fin 2) ℤ, IsLatticeBasis B →
      (∀ v : Fin 2 → ℤ, v ∈ columnLattice B ↔ zeta ^ (v 0) * g ^ (v 1) = 1) →
      ∃ m : ℕ, m < q - 1 ∧
        extract (discreteLogInput q zeta g B) = encodeNatural m ∧
        (![((m : ℕ) : ℤ), -1] : Fin 2 → ℤ) ∈ columnLattice B ∧ zeta ^ m = g := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P03

end
Source
Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026v1, PDF p. 4, §1 example 2: discrete logarithm from a rank-two stabilizer
Read-back

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

There exists a function extract\mathrm{extract}extract from finite Boolean lists to finite Boolean lists that is Turing-machine computable in polynomial time with identity input and output encodings, such that for every prime natural number qqq, every pair of units ζ,g\zeta,gζ,g of Z/qZ\mathbb Z/q\mathbb ZZ/qZ with ζ\zetaζ of multiplicative order q−1q-1q−1, and every integer 2×22\times22×2 matrix BBB whose multiplication map on Z2\mathbb Z^2Z2 is injective, the following implication holds: if, for every v=(v0,v1)∈Z2v=(v_0,v_1)\in\mathbb Z^2v=(v0​,v1​)∈Z2, membership in {Bc:c∈Z2}\{Bc:c\in\mathbb Z^2\}{Bc:c∈Z2} is equivalent to ζv0gv1=1\zeta^{v_0}g^{v_1}=1ζv0​gv1​=1, then there exists a natural number m<q−1m<q-1m<q−1 such that extract\mathrm{extract}extract applied to the encoded input (q,ζ,g,B)(q,\zeta,g,B)(q,ζ,g,B) returns the natural-number encoding of mmm, the integer vector (m,−1)(m,-1)(m,−1) belongs to {Bc:c∈Z2}\{Bc:c\in\mathbb Z^2\}{Bc:c∈Z2}, and ζm=g\zeta^m=gζm=g. Negative exponents in the hypothesis are taken in the unit group. The encoded input concatenates natural-number encodings of qqq and the representatives of ζ,g\zeta,gζ,g in {0,…,q−1}\{0,\ldots,q-1\}{0,…,q−1}, then the natural-number encoding of 222 and signed encodings of B00,B10,B01,B11B_{00},B_{10},B_{01},B_{11}B00​,B10​,B01​,B11​. A natural number ttt is encoded by the least-significant-first binary digits of t+1t+1t+1, prefixed by their length in true bits and one false bit; an integer zzz is encoded by the bit indicating z<0z<0z<0 followed by the natural-number encoding of ∣z∣|z|∣z∣. The hypotheses allow q=2q=2q=2 and exclude q=0,1q=0,1q=0,1; no behavior is specified on inputs failing the hypotheses.

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