§3: exact recovery of a permutation eigenphase
OpenQAlgorithms.Papers.Independent.Intakethird100.P03.rational_phase_reconstructionLet be rational with denominator at most , and suppose a measurement returns the dyadic code with . If its circular distance from satisfies
then is the unique normalized rational phase of denominator at most within that distance. One classical polynomial-time procedure, chosen before , maps the full -bit dyadic word to the exact numerator/denominator encoding of .
The zero phase is included, and the dyadic numerator need not be coprime to its denominator. The fixed-width input has length , so polynomial-time reconstruction has the source's bit-cost meaning.
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.18: unique exact rational recovery from a 2n+1-bit dyadic measurement within
2^(-2n-1) on the phase circle, in polynomial time. The zero phase is included. -/
theorem rational_phase_reconstruction :
∃ recover : List Bool → List Bool, QAlgorithms.Complexity.PolyTimeComputable recover ∧
∀ (n numerator : ℕ), numerator < 2 ^ (2 * n + 1) →
∀ phi : ℚ, 0 ≤ phi → phi < 1 → phi.den ≤ 2 ^ n →
phaseDistance ((numerator : ℝ) / (2 : ℝ) ^ (2 * n + 1)) (phi : ℝ) ≤
1 / (2 : ℝ) ^ (2 * n + 1) →
recover (rationalRecoveryInput n numerator) = encodeRational phi ∧
∀ psi : ℚ, 0 ≤ psi → psi < 1 → psi.den ≤ 2 ^ n →
phaseDistance ((numerator : ℝ) / (2 : ℝ) ^ (2 * n + 1)) (psi : ℝ) ≤
1 / (2 : ℝ) ^ (2 * n + 1) → psi = phi := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P03
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exists a function from finite Boolean strings to finite Boolean strings that is computable in polynomial time by a Turing machine and has the following property. For every pair of natural numbers with , and every rational number satisfying , whose positive reduced denominator is at most , if
where , then , applied to true bits followed by one false bit and the -bit, most-significant-bit-first representation of , returns the prescribed encoding of . Moreover, every rational satisfying , reduced denominator at most , and the same non-strict distance bound equals . The prescribed rational encoding concatenates the encoding of the signed reduced numerator with that of the positive reduced denominator: a signed integer is encoded by its negativity bit followed by the natural-number encoding of its absolute value, and a natural number is encoded by taking the least-significant-bit-first binary digits of , prefixing as many true bits as there are digits, and then one false bit. The statement includes and equality in the distance bound. It imposes no output requirement when no qualifying rational exists or on strings outside the specified inputs.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.