Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Quantum measurements and the Abelian Stabilizer Problem

Definition
QAlgorithms_Papers_Independent_Intakethird100_P03

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

prove2quantum

The objects the formalized statements of Quantum measurements and the Abelian Stabilizer Problem (arXiv:quant-ph/9511026) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • ASPAction: PDF p.3: an action on a uniquely encoded subset, with no membership algorithm. The total black box has unrestricted behavior outside M.
  • stabilizer: PDF pp.3–4: the stabilizer is constructed from the action and the given point.
  • integerBits: PDF p.3, reasonable coding: one sign bit and a self-delimited binary magnitude. This explicit length differs by a constant factor from ordinary signed integer coding.
  • latticeBasisBits: PDF p.4: total bit length of the columns of an additive lattice basis.
  • orderAction: PDF p.4, example 1: the integer-power action on the residue ring.
  • andTau: PDF p.11: Toffoli, with controls on the first two wires.
  • notTau: PDF p.8: the XOR lift of NOT, distinct from the single-wire NOT.
  • cTauBasis: PDF p.8: C_tau includes copy/XOR in addition to the XOR lifts of NOT and AND.
  • rBasis: PDF p.8: the classical reversible basis R.
  • kitaevGateBasis: PDF p.11: all one-qubit unitaries, CNOT and Toffoli; not a finite gate set.
  • OrthogonalProjectorFamily: PDF pp.10,15: finite orthogonal families, encoded by their orthogonal projectors. No completeness assumption is imposed. Zero projectors are harmless.
  • OrthogonalProjectorFamily.support: PDF pp.10,15: projection onto the measured support N.
  • subspaceProbability: PDF p.9, equation (8): Born probability for a subspace projector.
  • Computes: PDF p.11, Definition 3: the output register, rather than the whole memory, is measured. Inputs outside the promise are unconstrained.
  • PartialUnitary: PDF p.12: a genuine partial unitary is an isometry equivalence between subspaces.
  • PartialUnitary.inverse: PDF p.12: partial inverse, with domain and range swapped.
  • PartialApprox: PDF p.12: precision on the intended domain, including BOTH subspace inclusions. The printed undefined A is read as U_tilde, as forced by the preceding definition.
  • PartialUnitary.apply: A total evaluation helper for a partial unitary, using projection onto its domain. It is NOT asserted to be a full unitary. Only valid-domain evaluations are used below.
  • partialRun: PDF p.12: a compatible sequence is evaluated in chronological order.
  • PartialSequenceApprox: PDF p.12: the full precision relation for two valid partial-operation sequences on specified initial domains. Besides the vector bound, both the initial-domain and composite-range inclusions are required. Validity of both chains is supplied by uses.
  • binaryAngle: PDF p.14: the exactly represented finite binary angle, first bit of weight 1/2.
  • rotatedZero: PDF p.14: |x> tensored with the real rotation of |0>.
  • randomBitBell: PDF p.14: the Bell state produced by copying a Hadamard bit with CNOT.
  • garbageState: PDF pp.14–15: the physical output when basis input x produces (G(x),g(x)).
  • coherentImage: PDF pp.14–15: the ideal coherent image before discarding work.
  • phaseAncilla: PDF p.16: the eigenphase ancilla block H diag(1,lambda) H.
  • eigenphaseTest: PDF p.16, equation (16): H, controlled U, H; target is the second factor.
  • measurementMatrix: PDF p.15, Definition 5: measurement operator on N tensor D, extended by identity on the unmeasured orthogonal complement. This extension is also used in Theorem 2.
  • eigenspaceOutcomeProbability: PDF p.15: conditional probability, with ordered output wires C and zero work D.
  • firstMeasurement: PDF pp.16–17: first measurement lifted to distinct ancillary factor D'.
  • secondMeasurement: PDF pp.16–17: second measurement lifted to distinct ancillary factor D''.
  • inputXorMatrix: PDF p.16: XOR a retained input word into the first n wires of fresh computer memory; the remaining w wires are untouched. This is a product of n CNOTs.
  • copyInputMatrix: PDF p.16: the actual input-copy operator, with retained input first and fresh computation memory second. It does not clone an unknown quantum state.
  • majorityCode: PDF p.11: strict majority, with an explicit failure flag when no majority exists. The final bit is true exactly when a majority was found.
  • majorityTail: PDF p.11: binomial upper tail includes ties (2j >= r).
  • amplificationRate: PDF p.11: the exponential rate for fixed base error epsilon.
  • repeatedMajorityLaw: PDF p.11: the exact law of majority of independent computations on fresh memories. Only a classical input x is copied; no unknown quantum state is cloned.
  • cyclicFourierVector: PDF p.21, equation (22): the source's positive-sign, normalized cyclic Fourier vector embedded in n residue qubits. q>=1 and q<=2^n are imposed by its uses.
  • outerMap: Rank-one map |v><u|, used to construct the ideal partial maps (23) and (24).
  • cyclicFourierMatrix: PDF p.21, equation (22): the cyclic QFT, with zero action outside its valid subspace. This is a partial-isometry matrix, not a claimed full-space unitary.
  • idealQ: PDF p.21, equation (23): constructed linear extension |psi_a,0> -> |psi_a,a>. Its conjugate transpose is its inverse on the indicated range.
  • idealTswapped: PDF p.21, equation (24), registers [Y,X]: |0,a> -> |psi_a,a>.
  • xorIntoSecond: PDF p.21, equation (25): tau_n[X,Y] adds X into Y.
  • xorIntoFirst: PDF p.21, equation (25): tau_n[Y,X] adds Y into X.
  • encodeNatural: PDF p.4: explicit self-delimiting binary natural coding, with a unary length prefix. Its length is logarithmic in t+1, rather than unary in t.
  • encodeInteger: PDF p.4: signed integer coding, preserving every integer entry exactly.
  • encodeBasis: PDF p.4: a dimension-prefixed, column-major encoding of an integer basis matrix.
  • columnLattice: PDF p.4: the subgroup generated by the columns, as a set of integer vectors.
  • IsLatticeBasis: PDF p.4: independence of the k columns, hence a basis of its full-rank lattice.
  • IsCanonicalBasis: PDF p.4, equation (1): canonical upper triangular COLUMN basis for the same subgroup. The above-diagonal entry is reduced modulo m_ii, not m_jj.
  • canonicalBasis: PDF p.4: the uniquely specified canonical matrix, with an explicit zero fallback on invalid inputs. The following theorem proves existence and uniqueness on every valid input.
  • discreteLogInput: PDF p.4, example 2: a primitive root and unit are encoded by their unique residues, followed by the supplied rank-two lattice basis.
  • phaseDistance: PDF pp.16,18: distance of real phases modulo one, in [0,1/2].
  • encodeRational: PDF p.18: normalized rational-phase output coding.
  • rationalRecoveryInput: PDF p.18: a dyadic measurement word has exactly 2n+1 bits, even when its numerator has leading zeros. Unary n and this fixed width make the input length O(n+1).
  • PartialUnitary.matrix: PDF pp.12–13: matrix of the partial isometry, zero on the orthogonal complement. It remains a partial gate: ValidPartialExecution checks every call's intended domain.
  • PartialOracleStep: PDF p.13: a Q operation or one plain call of a named n-wire partial oracle. There is no free controlled call and no free inverse oracle.
  • PartialOracleStep.matrix: PDF p.13: lift the known operation or the partial oracle to its ordered distinct wires.
  • partialOracleMatrix: PDF p.13: chronological operation list, with the oracle supplied only to the evaluator.
  • partialOracleCount: PDF p.13: syntactic plain-oracle count, including calls whose matrix happens to be Q.
  • ValidPartialExecution: PDF pp.12–13: each partial call is defined on the entire incoming vector, including entanglement with other wires. For the zero-extended isometry this is equivalent to norm preservation at that call, hence to membership in its lifted domain.
  • ControlledDomain: PDF p.13, equation (13): the two control slices must both belong to N. The controlled range is |0>N direct-sum |1>M, not B^1 tensor M when N differs from M.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Complexity
import Definitions.Def_QAlgorithms_Defs_Basic
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_QAlgorithms_Defs_Information
import Definitions.Def_QAlgorithms_Defs_Measurement
import Definitions.Def_QAlgorithms_Defs_MatrixDistances
import Definitions.Def_QAlgorithms_Papers_Independent_Renew46_P01

/-!
Statements from Kitaev, quant-ph/9511026v1. All page references are PDF pages.
Paper-local interfaces have complete bodies; target proofs are deliberately omitted.
Compilation is pending the separate mechanical handoff.
-/

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.3: an action on a uniquely encoded subset, with no membership algorithm.
The total black box has unrestricted behavior outside M. -/
structure ASPAction (k n : ℕ) (M : Set (Qubits n)) where
  run : (Fin k → ℤ) → Qubits n → Qubits n
  preserves : ∀ g x, x ∈ M → run g x ∈ M
  zero : ∀ x, x ∈ M → run 0 x = x
  add : ∀ g h x, x ∈ M → run (g + h) x = run g (run h x)

/-- PDF pp.3–4: the stabilizer is constructed from the action and the given point. -/
def stabilizer {k n : ℕ} {M : Set (Qubits n)} (A : ASPAction k n M)
    (a : Qubits n) (ha : a ∈ M) : AddSubgroup (Fin k → ℤ) where
  carrier := {g | A.run g a = a}
  zero_mem' := A.zero a ha
  add_mem' := by
    intro g h hg hh
    change A.run (g + h) a = a
    rw [A.add g h a ha, hh, hg]
  neg_mem' := by
    intro g hg
    change A.run (-g) a = a
    have h := A.add (-g) g a ha
    rw [neg_add_cancel, A.zero a ha, hg] at h
    exact h.symm

/-- PDF p.3, reasonable coding: one sign bit and a self-delimited binary magnitude.
This explicit length differs by a constant factor from ordinary signed integer coding. -/
def integerBits (z : ℤ) : ℕ := 2 * (Nat.log2 (z.natAbs + 1) + 1) + 1

/-- PDF p.4: total bit length of the columns of an additive lattice basis. -/
def latticeBasisBits {k : ℕ} {S : AddSubgroup (Fin k → ℤ)}
    (b : (Fin k → ℤ) ≃+ S) : ℕ :=
  ∑ i, ∑ j, integerBits ((b (Pi.single i (1 : ℤ))).val j)

example : integerBits 0 = 3 := by decide

example {k n : ℕ} {M : Set (Qubits n)} (A : ASPAction k n M)
    (a : Qubits n) (ha : a ∈ M) : (0 : Fin k → ℤ) ∈ stabilizer A a ha :=
  (stabilizer A a ha).zero_mem

/-- PDF p.4, example 1: the integer-power action on the residue ring. -/
def orderAction {q : ℕ} (g : (ZMod q)ˣ) (m : ℤ) (x : ZMod q) : ZMod q :=
  ((g ^ m : (ZMod q)ˣ) : ZMod q) * x

example {q : ℕ} (g : (ZMod q)ˣ) (x : ZMod q) : orderAction g 0 x = x := by
  simp [orderAction]

/-- PDF p.11: Toffoli, with controls on the first two wires. -/
def andTau : Gate :=
  ⟨3, fun y x => if y = ![x 0, x 1, xor (x 2) (x 0 && x 1)] then 1 else 0⟩

/-- PDF p.8: the XOR lift of NOT, distinct from the single-wire NOT. -/
def notTau : Gate := Gate.ofMatrix2
  (fun y x => if y = (x.1, xor x.2 (!x.1)) then 1 else 0)

/-- PDF p.8: C_tau includes copy/XOR in addition to the XOR lifts of NOT and AND. -/
def cTauBasis : Set Gate := {notTau, andTau, Gate.ofMatrix2 cnot}

/-- PDF p.8: the classical reversible basis R. -/
def rBasis : Set Gate := {Gate.ofMatrix1 pauliX, Gate.ofMatrix2 cnot, andTau}

/-- PDF p.11: all one-qubit unitaries, CNOT and Toffoli; not a finite gate set. -/
def kitaevGateBasis : Set Gate :=
  {g | g.arity = 1 ∧ g.IsUnitary} ∪ {Gate.ofMatrix2 cnot, andTau}

/-- PDF p.13, Definition 4: frozen clean padding leaves a zero-width register unchanged. -/
example (v : EuclideanSpace ℂ (Qubits 0)) (z : Qubits 0) : cleanVector 0 v z = v z := by
  simp [QAlgorithms.Papers.Independent.Renew46.P01.cleanVector]

example (x : Qubits 3) : andTau.mat ![x 0, x 1, xor (x 2) (x 0 && x 1)] x = 1 := by
  simp [andTau]

/-- PDF pp.10,15: finite orthogonal families, encoded by their orthogonal projectors.
No completeness assumption is imposed. Zero projectors are harmless. -/
structure OrthogonalProjectorFamily (I : Type*) [Fintype I] [DecidableEq I] (r : ℕ) where
  proj : Fin r → Matrix I I ℂ
  hermitian : ∀ v, (proj v).IsHermitian
  idempotent : ∀ v, proj v * proj v = proj v
  orthogonal : ∀ v u, v ≠ u → proj v * proj u = 0

/-- PDF pp.10,15: projection onto the measured support N. -/
def OrthogonalProjectorFamily.support {I : Type*} [Fintype I] [DecidableEq I] {r : ℕ}
    (O : OrthogonalProjectorFamily I r) : Matrix I I ℂ := ∑ v, O.proj v

/-- PDF p.9, equation (8): Born probability for a subspace projector. -/
def subspaceProbability {I : Type*} [Fintype I] (rho P : Matrix I I ℂ) : ℝ :=
  (rho * P).trace.re

example {I : Type*} [Fintype I] (rho : Matrix I I ℂ) :
    subspaceProbability rho 0 = 0 := by simp [subspaceProbability]

/-- PDF p.11, Definition 3: the output register, rather than the whole memory,
is measured. Inputs outside the promise are unconstrained. -/
def Computes {n m w : ℕ} (U : Matrix (Qubits (n + w)) (Qubits (n + w)) ℂ)
    (out : Fin m ↪ Fin (n + w)) (N : Set (Qubits n)) (F : Qubits n → Qubits m)
    (epsilon : ℝ) : Prop :=
  ∀ x ∈ N, 1 - epsilon ≤ probEvent (act U (inputState x w)) (fun z => z ∘ out = F x)

example {n m w : ℕ} (U : Matrix (Qubits (n + w)) (Qubits (n + w)) ℂ)
    (out : Fin m ↪ Fin (n + w)) (F : Qubits n → Qubits m) (e : ℝ) :
    Computes U out ∅ F e := by simp [Computes]

/-- PDF p.12: a genuine partial unitary is an isometry equivalence between subspaces. -/
structure PartialUnitary (I : Type*) [Fintype I] where
  domain : Submodule ℂ (EuclideanSpace ℂ I)
  range : Submodule ℂ (EuclideanSpace ℂ I)
  iso : domain ≃ₗᵢ[ℂ] range

/-- PDF p.12: partial inverse, with domain and range swapped. -/
def PartialUnitary.inverse {I : Type*} [Fintype I] (U : PartialUnitary I) : PartialUnitary I :=
  ⟨U.range, U.domain, U.iso.symm⟩

/-- PDF p.12: precision on the intended domain, including BOTH subspace inclusions.
The printed undefined A is read as U_tilde, as forced by the preceding definition. -/
def PartialApprox {I : Type*} [Fintype I] (V U : PartialUnitary I) (delta : ℝ) : Prop :=
  ∃ hdom : U.domain ≤ V.domain, U.range ≤ V.range ∧
    ∀ (x : EuclideanSpace ℂ I) (hx : x ∈ U.domain),
      ‖(V.iso ⟨x, hdom hx⟩ : EuclideanSpace ℂ I) -
        (U.iso ⟨x, hx⟩ : EuclideanSpace ℂ I)‖ ≤ delta * ‖x‖

/-- A total evaluation helper for a partial unitary, using projection onto its domain.
It is NOT asserted to be a full unitary. Only valid-domain evaluations are used below. -/
def PartialUnitary.apply {I : Type*} [Fintype I] (U : PartialUnitary I)
    (x : EuclideanSpace ℂ I) : EuclideanSpace ℂ I :=
  (U.iso (U.domain.orthogonalProjectionOnto x) : EuclideanSpace ℂ I)

/-- PDF p.12: a compatible sequence is evaluated in chronological order. -/
def partialRun {I : Type*} [Fintype I] (us : List (PartialUnitary I))
    (x : EuclideanSpace ℂ I) : EuclideanSpace ℂ I :=
  us.foldl (fun v U => U.apply v) x

example {I : Type*} [Fintype I] (x : EuclideanSpace ℂ I) : partialRun [] x = x := rfl

/-- PDF p.12: the full precision relation for two valid partial-operation sequences
on specified initial domains. Besides the vector bound, both the initial-domain and
composite-range inclusions are required. Validity of both chains is supplied by uses. -/
def PartialSequenceApprox {I : Type*} [Fintype I]
    (V U : List (PartialUnitary I))
    (N Ntilde : Submodule ℂ (EuclideanSpace ℂ I)) (delta : ℝ) : Prop :=
  N ≤ Ntilde ∧
    (∀ x ∈ N, ∃ y ∈ Ntilde, partialRun U x = partialRun V y) ∧
    ∀ x ∈ N, ‖partialRun V x - partialRun U x‖ ≤ delta * ‖x‖

example {I : Type*} [Fintype I] (N : Submodule ℂ (EuclideanSpace ℂ I)) :
    PartialSequenceApprox [] [] N N 0 := by
  refine ⟨le_rfl, ?_, ?_⟩
  · intro x hx
    exact ⟨x, hx, rfl⟩
  · intro x hx
    simp [partialRun]

/-- PDF p.14: the exactly represented finite binary angle, first bit of weight 1/2. -/
def binaryAngle {b : ℕ} (x : Qubits b) : ℝ :=
  2 * Real.pi * ∑ i : Fin b, if x i then 1 / (2 : ℝ) ^ (i.val + 1) else 0

/-- PDF p.14: |x> tensored with the real rotation of |0>. -/
def rotatedZero {b : ℕ} (x : Qubits b) : EuclideanSpace ℂ (Qubits (b + 1)) :=
  WithLp.toLp 2 fun z => if Fin.init z = x then
    (if z (Fin.last b) then (Real.sin (binaryAngle x) : ℂ)
      else (Real.cos (binaryAngle x) : ℂ)) else 0

example : binaryAngle (fun _ : Fin 0 => false) = 0 := by simp [binaryAngle]

/-- PDF p.14: the Bell state produced by copying a Hadamard bit with CNOT. -/
def randomBitBell : EuclideanSpace ℂ (Bool × Bool) :=
  act cnot (tensorVec (act hadamard (ket false)) (ket false))

/-- PDF pp.14–15: the physical output when basis input x produces (G(x),g(x)). -/
def garbageState {I J K : Type*} [Fintype I] [DecidableEq J] [DecidableEq K]
    (G : I → J) (g : I → K) (c : EuclideanSpace ℂ I) : EuclideanSpace ℂ (J × K) :=
  ∑ x, c x • ket (G x, g x)

/-- PDF pp.14–15: the ideal coherent image before discarding work. -/
def coherentImage {I J : Type*} [Fintype I] [DecidableEq J]
    (G : I → J) (c : EuclideanSpace ℂ I) : EuclideanSpace ℂ J := ∑ x, c x • ket (G x)

/-- PDF p.16: the eigenphase ancilla block H diag(1,lambda) H. -/
def phaseAncilla (phi : ℝ) : Matrix Bool Bool ℂ :=
  hadamard * Matrix.diagonal (fun b : Bool => if b then Complex.exp (2 * Real.pi * phi * Complex.I)
    else 1) * hadamard

/-- PDF p.16, equation (16): H, controlled U, H; target is the second factor. -/
def eigenphaseTest {I : Type*} [Fintype I] [DecidableEq I] (U : Matrix I I ℂ) :
    Matrix (Bool × I) (Bool × I) ℂ :=
  (hadamard ⊗ₖ (1 : Matrix I I ℂ)) * controlled U * (hadamard ⊗ₖ (1 : Matrix I I ℂ))

/-- PDF p.15, Definition 5: measurement operator on N tensor D, extended by identity
on the unmeasured orthogonal complement. This extension is also used in Theorem 2. -/
def measurementMatrix {I J : Type*} [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J]
    {r : ℕ} (O : OrthogonalProjectorFamily I r) (V : Fin r → Matrix J J ℂ) : Matrix (I × J) (I × J) ℂ :=
  (∑ v, O.proj v ⊗ₖ V v) + ((1 - O.support) ⊗ₖ (1 : Matrix J J ℂ))

/-- PDF p.15: conditional probability, with ordered output wires C and zero work D. -/
def eigenspaceOutcomeProbability {r d m : ℕ} (V : Fin r → Matrix (Qubits d) (Qubits d) ℂ)
    (C : Fin m ↪ Fin d) (v : Fin r) (y : Qubits m) : ℝ :=
  probEvent (act (V v) (zeroKet d)) (fun z => z ∘ C = y)

/-- PDF pp.16–17: first measurement lifted to distinct ancillary factor D'. -/
def firstMeasurement {I J K : Type*} [Fintype I] [DecidableEq I]
    [Fintype J] [DecidableEq J] [Fintype K] [DecidableEq K] {r : ℕ}
    (O : OrthogonalProjectorFamily I r) (V : Fin r → Matrix J J ℂ) : Matrix (I × (J × K)) (I × (J × K)) ℂ :=
  measurementMatrix O (fun v => V v ⊗ₖ (1 : Matrix K K ℂ))

/-- PDF pp.16–17: second measurement lifted to distinct ancillary factor D''. -/
def secondMeasurement {I J K : Type*} [Fintype I] [DecidableEq I]
    [Fintype J] [DecidableEq J] [Fintype K] [DecidableEq K] {r : ℕ}
    (O : OrthogonalProjectorFamily I r) (V : Fin r → Matrix K K ℂ) : Matrix (I × (J × K)) (I × (J × K)) ℂ :=
  measurementMatrix O (fun v => (1 : Matrix J J ℂ) ⊗ₖ V v)

example {I J : Type*} [Fintype I] [DecidableEq I] [Fintype J] [DecidableEq J] :
    measurementMatrix (I := I) (J := J)
      (⟨Fin.elim0, by intro v; exact Fin.elim0 v, by intro v; exact Fin.elim0 v,
        by intro v; exact Fin.elim0 v⟩ : OrthogonalProjectorFamily I 0) Fin.elim0 = 1 := by
  simp [measurementMatrix, OrthogonalProjectorFamily.support, Matrix.one_kronecker_one]

/-- PDF p.16: XOR a retained input word into the first n wires of fresh
computer memory; the remaining w wires are untouched. This is a product of n CNOTs. -/
def inputXorMatrix {n : ℕ} (w : ℕ) (x : Qubits n) :
    Matrix (Qubits (n + w)) (Qubits (n + w)) ℂ :=
  fun y z => if y = (fun i => xor (z i) (Fin.append x (fun _ : Fin w => false) i))
    then 1 else 0

/-- PDF p.16: the actual input-copy operator, with retained input first and
fresh computation memory second. It does not clone an unknown quantum state. -/
def copyInputMatrix (n w : ℕ) :
    Matrix (Qubits n × Qubits (n + w)) (Qubits n × Qubits (n + w)) ℂ :=
  fun y z => if y.1 = z.1 then inputXorMatrix w z.1 y.2 z.2 else 0

example {n : ℕ} (w : ℕ) (x : Qubits n) (z : Qubits (n + w)) :
    inputXorMatrix w x
      (fun i => xor (z i) (Fin.append x (fun _ : Fin w => false) i)) z = 1 := by
  simp [inputXorMatrix]

/-- PDF p.11: strict majority, with an explicit failure flag when no majority exists.
The final bit is true exactly when a majority was found. -/
def majorityCode {r m : ℕ} (ys : Fin r → Qubits m) : Qubits (m + 1) :=
  if h : ∃ y : Qubits m, r < 2 * (Finset.univ.filter (fun i => ys i = y)).card then
    Fin.snoc h.choose true else Fin.snoc (fun _ => false) false

/-- PDF p.11: binomial upper tail includes ties (2j >= r). -/
def majorityTail (r : ℕ) (epsilon : ℝ) : ℝ :=
  ∑ j ∈ (Finset.range (r + 1)).filter (fun j => r ≤ 2 * j),
    (Nat.choose r j : ℝ) * epsilon ^ j * (1 - epsilon) ^ (r - j)

/-- PDF p.11: the exponential rate for fixed base error epsilon. -/
def amplificationRate (epsilon : ℝ) : ℝ := 2 * Real.sqrt (epsilon * (1 - epsilon))

/-- PDF p.11: the exact law of majority of independent computations on fresh memories.
Only a classical input x is copied; no unknown quantum state is cloned. -/
def repeatedMajorityLaw {n m w : ℕ}
    (U : Matrix (Qubits (n + w)) (Qubits (n + w)) ℂ)
    (out : Fin m ↪ Fin (n + w)) (r : ℕ) (x : Qubits n) (y : Qubits (m + 1)) : ℝ :=
  ∑ ys : Fin r → Qubits m, if majorityCode ys = y then
    ∏ i, probEvent (act U (inputState x w)) (fun z => z ∘ out = ys i) else 0

example (ys : Fin 0 → Qubits 1) : majorityCode ys (Fin.last 1) = false := by
  unfold majorityCode
  split
  next h => simp at h
  next => rw [Fin.snoc_last]

/-- PDF p.21, equation (22): the source's positive-sign, normalized cyclic Fourier vector
embedded in n residue qubits. q>=1 and q<=2^n are imposed by its uses. -/
def cyclicFourierVector (n q : ℕ) (a : Fin q) : EuclideanSpace ℂ (Qubits n) :=
  ∑ b : Fin q, qftMatrix q b a • ket (natToBits n b.val)

/-- Rank-one map |v><u|, used to construct the ideal partial maps (23) and (24). -/
def outerMap {I : Type*} (v u : EuclideanSpace ℂ I) : Matrix I I ℂ :=
  fun i j => v i * conj (u j)

/-- PDF p.21, equation (22): the cyclic QFT, with zero action outside its valid subspace.
This is a partial-isometry matrix, not a claimed full-space unitary. -/
def cyclicFourierMatrix (n q : ℕ) : Matrix (Qubits n) (Qubits n) ℂ :=
  ∑ a : Fin q, outerMap (cyclicFourierVector n q a) (ket (natToBits n a.val))

/-- PDF p.21, equation (23): constructed linear extension |psi_a,0> -> |psi_a,a>.
Its conjugate transpose is its inverse on the indicated range. -/
def idealQ (n q : ℕ) : Matrix (Qubits n × Qubits n) (Qubits n × Qubits n) ℂ :=
  ∑ a : Fin q, outerMap
    (tensorVec (cyclicFourierVector n q a) (ket (natToBits n a.val)))
    (tensorVec (cyclicFourierVector n q a) (zeroKet n))

/-- PDF p.21, equation (24), registers [Y,X]: |0,a> -> |psi_a,a>. -/
def idealTswapped (n q : ℕ) : Matrix (Qubits n × Qubits n) (Qubits n × Qubits n) ℂ :=
  ∑ a : Fin q, outerMap
    (tensorVec (cyclicFourierVector n q a) (ket (natToBits n a.val)))
    (tensorVec (zeroKet n) (ket (natToBits n a.val)))

/-- PDF p.21, equation (25): tau_n[X,Y] adds X into Y. -/
def xorIntoSecond (n : ℕ) : Matrix (Qubits n × Qubits n) (Qubits n × Qubits n) ℂ :=
  fun y x => if y = (x.1, fun i => xor (x.2 i) (x.1 i)) then 1 else 0

/-- PDF p.21, equation (25): tau_n[Y,X] adds Y into X. -/
def xorIntoFirst (n : ℕ) : Matrix (Qubits n × Qubits n) (Qubits n × Qubits n) ℂ :=
  fun y x => if y = ((fun i => xor (x.1 i) (x.2 i)), x.2) then 1 else 0

example (n : ℕ) : cyclicFourierVector n 1 0 = ket (natToBits n 0) := by
  simp [cyclicFourierVector, qftMatrix, Fin.sum_univ_one]

/-- PDF p.4: explicit self-delimiting binary natural coding, with a unary length prefix.
Its length is logarithmic in t+1, rather than unary in t. -/
def encodeNatural (t : ℕ) : List Bool :=
  let bs := Nat.bits (t + 1)
  List.replicate bs.length true ++ [false] ++ bs

/-- PDF p.4: signed integer coding, preserving every integer entry exactly. -/
def encodeInteger (z : ℤ) : List Bool := decide (z < 0) :: encodeNatural z.natAbs

/-- PDF p.4: a dimension-prefixed, column-major encoding of an integer basis matrix. -/
def encodeBasis {k : ℕ} (B : Matrix (Fin k) (Fin k) ℤ) : List Bool :=
  encodeNatural k ++ ((List.ofFn fun j =>
    (List.ofFn fun i => encodeInteger (B i j)).flatten).flatten)

/-- PDF p.4: the subgroup generated by the columns, as a set of integer vectors. -/
def columnLattice {k : ℕ} (B : Matrix (Fin k) (Fin k) ℤ) : Set (Fin k → ℤ) :=
  Set.range (fun c => B.mulVec c)

/-- PDF p.4: independence of the k columns, hence a basis of its full-rank lattice. -/
def IsLatticeBasis {k : ℕ} (B : Matrix (Fin k) (Fin k) ℤ) : Prop :=
  Function.Injective (fun c => B.mulVec c)

/-- PDF p.4, equation (1): canonical upper triangular COLUMN basis for the same subgroup.
The above-diagonal entry is reduced modulo m_ii, not m_jj. -/
def IsCanonicalBasis {k : ℕ} (B C : Matrix (Fin k) (Fin k) ℤ) : Prop :=
  IsLatticeBasis C ∧ columnLattice C = columnLattice B ∧
  (∀ i j, j < i → C i j = 0) ∧ (∀ i, 0 < C i i) ∧
  (∀ i j, i < j → 0 ≤ C i j ∧ C i j < C i i)

/-- PDF p.4: the uniquely specified canonical matrix, with an explicit zero fallback
on invalid inputs. The following theorem proves existence and uniqueness on every valid input. -/
def canonicalBasis {k : ℕ} (B : Matrix (Fin k) (Fin k) ℤ) : Matrix (Fin k) (Fin k) ℤ :=
  if h : ∃ C, IsCanonicalBasis B C then h.choose else 0

example : encodeNatural 0 = [true, false, true] := rfl

example : encodeInteger 0 = [false, true, false, true] := rfl

/-- PDF p.4, example 2: a primitive root and unit are encoded by their unique residues,
followed by the supplied rank-two lattice basis. -/
def discreteLogInput (q : ℕ) (zeta g : (ZMod q)ˣ) (B : Matrix (Fin 2) (Fin 2) ℤ) : List Bool :=
  encodeNatural q ++ encodeNatural (zeta : ZMod q).val ++
    encodeNatural (g : ZMod q).val ++ encodeBasis B

/-- PDF pp.16,18: distance of real phases modulo one, in [0,1/2]. -/
def phaseDistance (x y : ℝ) : ℝ := min (Int.fract (x - y)) (1 - Int.fract (x - y))

/-- PDF p.18: normalized rational-phase output coding. -/
def encodeRational (r : ℚ) : List Bool := encodeInteger r.num ++ encodeNatural r.den

/-- PDF p.18: a dyadic measurement word has exactly 2n+1 bits, even when its numerator
has leading zeros. Unary n and this fixed width make the input length O(n+1). -/
def rationalRecoveryInput (n numerator : ℕ) : List Bool :=
  List.replicate n true ++ [false] ++ List.ofFn (natToBits (2 * n + 1) numerator)

example (x : ℝ) : phaseDistance x x = 0 := by simp [phaseDistance]

/-- PDF pp.12–13: matrix of the partial isometry, zero on the orthogonal complement.
It remains a partial gate: ValidPartialExecution checks every call's intended domain. -/
def PartialUnitary.matrix {I : Type*} [Fintype I] [DecidableEq I] (U : PartialUnitary I) :
    Matrix I I ℂ := fun i j => U.apply (ket j) i

/-- PDF p.13: a Q operation or one plain call of a named n-wire partial oracle.
There is no free controlled call and no free inverse oracle. -/
inductive PartialOracleStep (n total : ℕ) where
  | known (g : GateApp kitaevGateBasis total)
  | call (wires : Fin n ↪ Fin total)

/-- PDF p.13: lift the known operation or the partial oracle to its ordered distinct wires. -/
def PartialOracleStep.matrix {n total : ℕ} (U : PartialUnitary (Qubits n)) :
    PartialOracleStep n total → Matrix (Qubits total) (Qubits total) ℂ
  | .known g => embedOp g.gate.mat g.wires
  | .call wires => embedOp U.matrix wires

/-- PDF p.13: chronological operation list, with the oracle supplied only to the evaluator. -/
def partialOracleMatrix {n total : ℕ} (c : List (PartialOracleStep n total))
    (U : PartialUnitary (Qubits n)) : Matrix (Qubits total) (Qubits total) ℂ :=
  (c.map (PartialOracleStep.matrix U)).reverse.prod

/-- PDF p.13: syntactic plain-oracle count, including calls whose matrix happens to be Q. -/
def partialOracleCount {n total : ℕ} (c : List (PartialOracleStep n total)) : ℕ :=
  c.countP (fun s => match s with | .known _ => false | .call _ => true)

/-- PDF pp.12–13: each partial call is defined on the entire incoming vector, including
entanglement with other wires. For the zero-extended isometry this is equivalent to norm
preservation at that call, hence to membership in its lifted domain. -/
def ValidPartialExecution {n total : ℕ} (c : List (PartialOracleStep n total))
    (U : PartialUnitary (Qubits n)) (v : EuclideanSpace ℂ (Qubits total)) : Prop :=
  ∀ j : Fin c.length, match c.get j with
    | .known _ => True
    | .call wires =>
      let incoming := act (partialOracleMatrix (c.take j.val) U) v
      ‖act (embedOp U.matrix wires) incoming‖ = ‖incoming‖

/-- PDF p.13, equation (13): the two control slices must both belong to N.
The controlled range is |0>N direct-sum |1>M, not B^1 tensor M when N differs from M. -/
def ControlledDomain {n : ℕ} (U : PartialUnitary (Qubits n))
    (v : EuclideanSpace ℂ (Qubits (n + 1))) : Prop :=
  ∀ b : Bool, (WithLp.toLp 2 (fun x : Qubits n => v (Fin.cons b x))) ∈ U.domain

example {n total : ℕ} (U : PartialUnitary (Qubits n)) :
    partialOracleMatrix ([] : List (PartialOracleStep n total)) U = 1 := rfl

example {n total : ℕ} : partialOracleCount ([] : List (PartialOracleStep n total)) = 0 := rfl

end QAlgorithms.Papers.Independent.Intakethird100.P03
Source
Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026v1, https://arxiv.org/abs/quant-ph/9511026v1
Read-back

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

QAlgorithms.Papers.Independent.Intakethird100.P03.ASPAction

For natural numbers k,nk,nk,n, including zero, and a set M⊆{0,1}nM\subseteq\{0,1\}^nM⊆{0,1}n, an ASPAction(k,n,M)\mathrm{ASPAction}(k,n,M)ASPAction(k,n,M) consists of a total function run⁡:Zk×{0,1}n→{0,1}n\operatorname{run}:\mathbb Z^k\times\{0,1\}^n\to\{0,1\}^nrun:Zk×{0,1}n→{0,1}n satisfying the following conditions: for every g,h∈Zkg,h\in\mathbb Z^kg,h∈Zk and x∈Mx\in Mx∈M, one has run⁡(g,x)∈M\operatorname{run}(g,x)\in Mrun(g,x)∈M, run⁡(0,x)=x\operatorname{run}(0,x)=xrun(0,x)=x, and run⁡(g+h,x)=run⁡(g,run⁡(h,x))\operatorname{run}(g+h,x)=\operatorname{run}(g,\operatorname{run}(h,x))run(g+h,x)=run(g,run(h,x)), where addition in Zk\mathbb Z^kZk is coordinatewise. These conditions impose no requirements on inputs x∉Mx\notin Mx∈/M; when MMM is empty, all three conditions are vacuous.

QAlgorithms.Papers.Independent.Intakethird100.P03.Computes

For natural numbers n,m,wn,m,wn,m,w, a complex matrix UUU indexed by the bit strings of length n+wn+wn+w, an injection out:{0,…,m−1}→{0,…,n+w−1}\mathrm{out}:\{0,\ldots,m-1\}\to\{0,\ldots,n+w-1\}out:{0,…,m−1}→{0,…,n+w−1}, a subset N⊆{0,1}nN\subseteq\{0,1\}^nN⊆{0,1}n, a function F:{0,1}n→{0,1}mF:\{0,1\}^n\to\{0,1\}^mF:{0,1}n→{0,1}m, and a real number ϵ\epsilonϵ, the defined property means that

∀x∈N,1−ϵ≤∑z∈{0,1}n+wzout(i)=F(x)i for every i<m∣(U∣x,0w⟩)z∣2.\forall x\in N,\qquad 1-\epsilon\le \sum_{\substack{z\in\{0,1\}^{n+w}\\ z_{\mathrm{out}(i)}=F(x)_i\ \text{for every }i<m}} \left|(U|x,0^w\rangle)_z\right|^2.∀x∈N,1−ϵ≤z∈{0,1}n+wzout(i)​=F(x)i​ for every i<m​∑​∣(U∣x,0w⟩)z​∣2.

Here ∣x,0w⟩|x,0^w\rangle∣x,0w⟩ is the coordinate vector at xxx followed by www false bits, and UUU acts by ordinary matrix-vector multiplication. This definition imposes no unitarity condition on UUU and no restriction on ϵ\epsilonϵ. It is vacuously satisfied when NNN is empty. All lengths may be 000; when m=0m=0m=0, every zzz satisfies the output condition.

QAlgorithms.Papers.Independent.Intakethird100.P03.ControlledDomain

For every natural number nnn, every partial unitary UUU consisting of an isometry between complex subspaces D,R⊆C{0,1}nD,R\subseteq\mathbb C^{\{0,1\}^n}D,R⊆C{0,1}n, and every vector v∈C{0,1}n+1v\in\mathbb C^{\{0,1\}^{n+1}}v∈C{0,1}n+1, this predicate says that both vectors

vb(x)=v(b,x),b∈{false,true},v_b(x)=v(b,x),\qquad b\in\{\mathrm{false},\mathrm{true}\},vb​(x)=v(b,x),b∈{false,true},

belong to DDD, where (b,x)(b,x)(b,x) is the bit string whose first bit is bbb and whose remaining nnn bits are xxx. Neither slice nor the full vector is required to be normalized or nonzero. For n=0n=0n=0, each slice has one coordinate, indexed by the unique empty bit string, and both resulting vectors must still belong to DDD.

QAlgorithms.Papers.Independent.Intakethird100.P03.IsCanonicalBasis

For every natural number kkk and integer k×kk\times kk×k matrices BBB and CCC, this predicate requires that multiplication by CCC be injective on Zk\mathbb Z^kZk; that {Cc:c∈Zk}={Bc:c∈Zk}\{Cc:c\in\mathbb Z^k\}=\{Bc:c\in\mathbb Z^k\}{Cc:c∈Zk}={Bc:c∈Zk}; that Cij=0C_{ij}=0Cij​=0 whenever j<ij<ij<i; that Cii>0C_{ii}>0Cii​>0 for every iii; and that 0≤Cij<Cii0\le C_{ij}<C_{ii}0≤Cij​<Cii​ whenever i<ji<ji<j. In particular, the upper off-diagonal entry CijC_{ij}Cij​ is bounded by the diagonal entry in its own row. When k=0k=0k=0, all these conditions hold for the empty matrices.

QAlgorithms.Papers.Independent.Intakethird100.P03.IsLatticeBasis

For every natural number kkk and every integer k×kk\times kk×k matrix BBB, this predicate means that multiplication by BBB is injective on integer vectors: for every c,d∈Zkc,d\in\mathbb Z^kc,d∈Zk, if ∑jBijcj=∑jBijdj\sum_jB_{ij}c_j=\sum_jB_{ij}d_j∑j​Bij​cj​=∑j​Bij​dj​ for every iii, then c=dc=dc=d. For k=0k=0k=0, this condition holds for the unique empty matrix.

QAlgorithms.Papers.Independent.Intakethird100.P03.OrthogonalProjectorFamily

For a finite type III with decidable equality and a natural number rrr, an object of this structure consists of complex matrices Pv∈CI×IP_v\in\mathbb C^{I\times I}Pv​∈CI×I, indexed by 0≤v<r0\le v<r0≤v<r, together with the requirements that Pv†=PvP_v^\dagger=P_vPv†​=Pv​ and Pv2=PvP_v^2=P_vPv2​=Pv​ for every vvv, and PvPu=0P_vP_u=0Pv​Pu​=0 whenever v≠uv\ne uv=u. There is no requirement that these matrices sum to the identity, have positive rank, or be distinct. Zero projectors are allowed. When r=0r=0r=0, the family is empty and all requirements are vacuous; III may also be empty.

QAlgorithms.Papers.Independent.Intakethird100.P03.OrthogonalProjectorFamily.support

For every finite type III with decidable equality, every natural number rrr, and every family O=(Pv)v=0r−1O=(P_v)_{v=0}^{r-1}O=(Pv​)v=0r−1​ of complex I×II\times II×I matrices satisfying Pv†=PvP_v^\dagger=P_vPv†​=Pv​, Pv2=PvP_v^2=P_vPv2​=Pv​, and PvPu=0P_vP_u=0Pv​Pu​=0 for distinct indices, its support is defined to be the matrix

support⁡(O)=∑v=0r−1Pv.\operatorname{support}(O)=\sum_{v=0}^{r-1}P_v.support(O)=v=0∑r−1​Pv​.

The family is not required to sum to the identity. For r=0r=0r=0, this definition gives the zero matrix, and the index type III is allowed to be empty.

QAlgorithms.Papers.Independent.Intakethird100.P03.PartialApprox

For any finite index type III, let VVV and UUU be partial unitaries on CI\mathbb C^ICI: each consists of domain and range complex subspaces DV,RVD_V,R_VDV​,RV​ and DU,RUD_U,R_UDU​,RU​, together with complex-linear isometric isomorphisms v:DV→RVv:D_V\to R_Vv:DV​→RV​ and u:DU→RUu:D_U\to R_Uu:DU​→RU​. For any real number δ\deltaδ, the relation defined here holds precisely when DU⊆DVD_U\subseteq D_VDU​⊆DV​, RU⊆RVR_U\subseteq R_VRU​⊆RV​, and

∥v(x)−u(x)∥≤δ∥x∥for every x∈DU.\|v(x)-u(x)\|\le \delta\|x\|\qquad\text{for every }x\in D_U.∥v(x)−u(x)∥≤δ∥x∥for every x∈DU​.

The norms are the Euclidean norms in the ambient space CI\mathbb C^ICI. No nonnegativity condition on δ\deltaδ is included; if δ<0\delta<0δ<0, the inequality can hold only when DU={0}D_U=\{0\}DU​={0}. Empty III is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P03.PartialOracleStep.matrix

For natural numbers n,Tn,Tn,T and a partial unitary UUU on the complex space indexed by nnn-bit strings, this definition assigns a complex matrix on TTT-bit strings to each step. Write UUU as an isometry u:D→Ru:D\to Ru:D→R between subspaces and let Mab=(u(PDeb))aM_{ab}=(u(P_D e_b))_aMab​=(u(PD​eb​))a​, where PDP_DPD​ is orthogonal projection onto DDD and ebe_beb​ is the coordinate basis vector. A known step uses its stored gate matrix and wire injection; its gate is either an arbitrary one-wire unitary, controlled NOT, or the three-wire permutation (a,b,c)↦(a,b,cxor(a∧b))(a,b,c)\mapsto(a,b,c\mathbin{\mathrm{xor}}(a\land b))(a,b,c)↦(a,b,cxor(a∧b)). A call step uses MMM and its stored injection. In either case, embedding a matrix BBB on kkk wires along an injection w:{0,…,k−1}↪{0,…,T−1}w:\{0,\ldots,k-1\}\hookrightarrow\{0,\ldots,T-1\}w:{0,…,k−1}↪{0,…,T−1} means assigning the entry

Ey,z={By∘w, z∘w,yq=zq for every q∉range⁡(w),0,otherwise,E_{y,z}= \begin{cases} B_{y\circ w,\,z\circ w},&y_q=z_q\text{ for every }q\notin\operatorname{range}(w),\\ 0,&\text{otherwise}, \end{cases}Ey,z​={By∘w,z∘w​,0,​yq​=zq​ for every q∈/range(w),otherwise,​

for TTT-bit strings y,zy,zy,z. The definition applies without any condition on the state supplied to this matrix, and includes zero-wire registers.

QAlgorithms.Papers.Independent.Intakethird100.P03.PartialOracleStep

For every pair of natural numbers n,Tn,Tn,T, this inductive definition specifies a type of steps with two constructors. A known step contains a gate ggg, a proof that it belongs to the prescribed gate set, and an injective assignment of its input wires to the TTT available wires. A gate consists of a natural-number arity kkk and a complex matrix indexed by kkk-bit strings. The prescribed set contains every unitary gate of arity 111, the two-wire gate sending (a,b)(a,b)(a,b) to (a,bxora)(a,b\mathbin{\mathrm{xor}}a)(a,bxora), and the three-wire gate sending (a,b,c)(a,b,c)(a,b,c) to (a,b,cxor(a∧b))(a,b,c\mathbin{\mathrm{xor}}(a\land b))(a,b,cxor(a∧b)); the latter two have matrix entries 111 at the indicated output for each input and 000 elsewhere. A call step contains only an injection from the nnn oracle wires into the TTT available wires. No oracle or state is stored in a call step. Zero values of nnn and TTT are included: a call has no possible wire injection when n>Tn>Tn>T, whereas for n=0n=0n=0 its wire assignment is the empty injection.

QAlgorithms.Papers.Independent.Intakethird100.P03.PartialSequenceApprox

For any finite index type III, possibly empty, let E=CIE=\mathbb C^IE=CI with its Euclidean norm. A partial unitary consists of two complex linear subspaces D,R⊆ED,R\subseteq ED,R⊆E and a complex linear isometric isomorphism u:D→Ru:D\to Ru:D→R; its application to an arbitrary vector x∈Ex\in Ex∈E means u(PDx)u(P_Dx)u(PD​x), where PDP_DPD​ is orthogonal projection onto DDD. For any finite lists V,UV,UV,U of such partial unitaries, any subspaces N,N~⊆EN,\widetilde N\subseteq EN,N⊆E, and any real δ\deltaδ, the defined condition is the conjunction

N⊆N~,∀x∈N ∃y∈N~: RU(x)=RV(y),∀x∈N: ∥RV(x)−RU(x)∥≤δ∥x∥,N\subseteq\widetilde N,\qquad \forall x\in N\ \exists y\in\widetilde N:\ R_U(x)=R_V(y),\qquad \forall x\in N:\ \|R_V(x)-R_U(x)\|\le\delta\|x\|,N⊆N,∀x∈N ∃y∈N: RU​(x)=RV​(y),∀x∈N: ∥RV​(x)−RU​(x)∥≤δ∥x∥,

where RUR_URU​ and RVR_VRV​ apply the entries of the corresponding list in list order, projecting onto each entry’s domain before applying its isomorphism. The lists need not have equal lengths, and an empty list acts as the identity. The existentially chosen yyy need not equal xxx. No sign restriction is imposed on δ\deltaδ; if δ<0\delta<0δ<0, the displayed norm bound can hold only when N={0}N=\{0\}N={0}.

QAlgorithms.Papers.Independent.Intakethird100.P03.PartialUnitary.apply

For any finite index type III, any partial unitary UUU consisting of complex subspaces DU,RU⊆CID_U,R_U\subseteq\mathbb C^IDU​,RU​⊆CI and a complex-linear isometric isomorphism u:DU→RUu:D_U\to R_Uu:DU​→RU​, and any vector x∈CIx\in\mathbb C^Ix∈CI, this definition returns

u(PDUx),u(P_{D_U}x),u(PDU​​x),

viewed as a vector in CI\mathbb C^ICI, where PDUP_{D_U}PDU​​ is the orthogonal projection onto DUD_UDU​. Thus the operation is defined for every ambient vector, including vectors outside the domain; it sends vectors orthogonal to the domain to zero. The index type III may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P03.PartialUnitary.inverse

For every finite type III and every partial unitary consisting of complex linear subspaces D,R⊆CID,R\subseteq\mathbb C^ID,R⊆CI and a bijective complex linear isometry T:D→RT:D\to RT:D→R, its inverse is defined to be the partial unitary with domain RRR, range DDD, and isometry T−1:R→DT^{-1}:R\to DT−1:R→D. This definition also applies to zero subspaces and to an empty index type III.

QAlgorithms.Papers.Independent.Intakethird100.P03.PartialUnitary.matrix

For every finite type III equipped with decidable equality and every partial unitary UUU on CI\mathbb C^ICI, consisting of complex linear subspaces D,R⊆CID,R\subseteq\mathbb C^ID,R⊆CI and a surjective complex linear isometry u:D→Ru:D\to Ru:D→R, this definition assigns the I×II\times II×I complex matrix

Mij=(u(PDej))i,M_{ij}=\bigl(u(P_D e_j)\bigr)_i,Mij​=(u(PD​ej​))i​,

where PDP_DPD​ is orthogonal projection onto DDD, eje_jej​ has coordinate 111 at jjj and 000 elsewhere, and vectors in RRR are viewed as vectors in CI\mathbb C^ICI. Thus the matrix represents the map that first projects onto the domain and then applies the isometry; the domain need not be the whole space. The finite type III may be empty, in which case this is the empty matrix.

QAlgorithms.Papers.Independent.Intakethird100.P03.PartialUnitary

For a finite type III, an object of this structure consists of two complex linear subspaces D,R⊆CID,R\subseteq\mathbb C^ID,R⊆CI, called its domain and range, together with a bijective complex linear isometry T:D→RT:D\to RT:D→R, where both subspaces inherit the Euclidean norm. Neither subspace is required to be the whole ambient space or to be nonzero. The index type III may be empty, in which case both subspaces are necessarily the zero space. The structure specifies the isometry on DDD, without specifying an action on vectors outside DDD.

QAlgorithms.Papers.Independent.Intakethird100.P03.ValidPartialExecution

For natural numbers n,Tn,Tn,T, a finite list c=[s0,…,sℓ−1]c=[s_0,\ldots,s_{\ell-1}]c=[s0​,…,sℓ−1​] of steps on TTT wires, a partial unitary UUU on the space indexed by nnn-bit strings, and any vector v∈C{0,1}Tv\in\mathbb C^{\{0,1\}^T}v∈C{0,1}T, this predicate requires norm preservation at every call step and places no requirement at known steps. More precisely, write UUU as an isometry u:D→Ru:D\to Ru:D→R between subspaces and let MMM represent uPDuP_DuPD​, with PDP_DPD​ the orthogonal projection onto DDD. For a call at position jjj with wire injection www, let vjv_jvj​ be the result of applying the first jjj step matrices to vvv in list order; the requirement is

∥Ew(M)vj∥=∥vj∥.\|E_w(M)v_j\|=\|v_j\|.∥Ew​(M)vj​∥=∥vj​∥.

Here Ew(B)y,z=By∘w,z∘wE_w(B)_{y,z}=B_{y\circ w,z\circ w}Ew​(B)y,z​=By∘w,z∘w​ if y,zy,zy,z agree outside the range of www, and is 000 otherwise. Call-step matrices are Ew(M)E_w(M)Ew​(M); known-step matrices are embeddings of their stored gates, which are arbitrary one-wire unitaries, controlled NOT, or (a,b,c)↦(a,b,cxor(a∧b))(a,b,c)\mapsto(a,b,c\mathbin{\mathrm{xor}}(a\land b))(a,b,c)↦(a,b,cxor(a∧b)). The incoming vector at the first position is vvv, because the empty prefix has identity matrix. There is no normalization requirement on vvv; the zero vector is included. A list with no calls, including the empty list, satisfies this predicate vacuously.

QAlgorithms.Papers.Independent.Intakethird100.P03.amplificationRate

For every real number ϵ\epsilonϵ, the amplification rate is defined by

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

There is no restriction on ϵ\epsilonϵ. The real square root is taken to be zero for negative arguments, so a(ϵ)=0a(\epsilon)=0a(ϵ)=0 when ϵ<0\epsilon<0ϵ<0 or ϵ>1\epsilon>1ϵ>1, and also at ϵ=0,1\epsilon=0,1ϵ=0,1.

QAlgorithms.Papers.Independent.Intakethird100.P03.andTau

This definition gives a gate of arity three whose complex matrix, indexed by three-bit output strings yyy and input strings xxx, has entry 111 exactly when y=(x0,x1,x2⊕(x0∧x1))y=(x_0,x_1,x_2\mathbin{\oplus}(x_0\land x_1))y=(x0​,x1​,x2​⊕(x0​∧x1​)), and entry 000 otherwise. Here ⊕\oplus⊕ is Boolean exclusive-or and ∧\land∧ is Boolean conjunction, so the first two bits are retained and the third is flipped exactly when both first bits are true.

QAlgorithms.Papers.Independent.Intakethird100.P03.binaryAngle

For every natural number bbb and every Boolean string xxx of length bbb, this definition assigns the real angle

2π∑i=0b−11{xi=true}2i+1.2\pi\sum_{i=0}^{b-1}\frac{\mathbf 1_{\{x_i=\mathrm{true}\}}}{2^{i+1}}.2πi=0∑b−1​2i+11{xi​=true}​​.

Thus the first bit receives weight 1/21/21/2, the second weight 1/41/41/4, and so on. When b=0b=0b=0, the sum is empty and the angle is zero.

QAlgorithms.Papers.Independent.Intakethird100.P03.cTauBasis

This definition gives the set consisting of three gates: the two-bit gate mapping (u,v)(u,v)(u,v) to (u,v⊕¬u)(u,v\mathbin{\oplus}\neg u)(u,v⊕¬u); the three-bit gate mapping (u,v,w)(u,v,w)(u,v,w) to (u,v,w⊕(u∧v))(u,v,w\mathbin{\oplus}(u\land v))(u,v,w⊕(u∧v)); and the two-bit gate mapping (u,v)(u,v)(u,v) to (u,v⊕u)(u,v\mathbin{\oplus}u)(u,v⊕u). Each gate’s complex matrix has entry 111 when its row string is the stated image of its column string and entry 000 otherwise; ⊕\oplus⊕, ¬\neg¬, and ∧\land∧ denote Boolean exclusive-or, negation, and conjunction.

QAlgorithms.Papers.Independent.Intakethird100.P03.canonicalBasis

For every natural number kkk and integer k×kk\times kk×k matrix BBB, this defines a matrix by choosing some integer k×kk\times kk×k matrix CCC satisfying the following conditions, if one exists: multiplication by CCC is injective on Zk\mathbb Z^kZk, its integer column span equals that of BBB, Cij=0C_{ij}=0Cij​=0 for j<ij<ij<i, every CiiC_{ii}Cii​ is positive, and 0≤Cij<Cii0\le C_{ij}<C_{ii}0≤Cij​<Cii​ for i<ji<ji<j. If no such CCC exists, the result is the zero matrix. This definition itself imposes no hypothesis on BBB and specifies no selection rule among multiple qualifying matrices.

QAlgorithms.Papers.Independent.Intakethird100.P03.coherentImage

For every finite index type III, every type JJJ equipped with decidable equality, every function G:I→JG:I\to JG:I→J, and every vector c∈CIc\in\mathbb C^Ic∈CI, this definition returns

∑x∈Ic(x) ∣G(x)⟩\sum_{x\in I}c(x)\,|G(x)\ranglex∈I∑​c(x)∣G(x)⟩

in the complex Euclidean space indexed by JJJ, where ∣j⟩|j\rangle∣j⟩ has coordinate 111 at jjj and 000 elsewhere. The type JJJ need not be finite, and neither normalization of ccc nor injectivity of GGG is assumed. Its amplitude at jjj is ∑x:G(x)=jc(x)\sum_{x:G(x)=j}c(x)∑x:G(x)=j​c(x); if III is empty, the result is zero.

QAlgorithms.Papers.Independent.Intakethird100.P03.columnLattice

For every natural number kkk and every integer k×kk\times kk×k matrix BBB, this defines the set {Bc:c∈Zk}\{Bc:c\in\mathbb Z^k\}{Bc:c∈Zk}, where (Bc)i=∑j=0k−1Bijcj(Bc)_i=\sum_{j=0}^{k-1}B_{ij}c_j(Bc)i​=∑j=0k−1​Bij​cj​. Thus all integer coefficient vectors are allowed, without any independence assumption on the columns. For k=0k=0k=0, this set contains the unique empty vector.

QAlgorithms.Papers.Independent.Intakethird100.P03.copyInputMatrix

For every pair of natural numbers n,wn,wn,w, this defines a complex matrix Cn,wC_{n,w}Cn,w​ indexed by pairs consisting of a Boolean string of length nnn and a Boolean string of length n+wn+wn+w. For row (a′,b′)(a',b')(a′,b′) and column (a,b)(a,b)(a,b), its entry is

(Cn,w)(a′,b′),(a,b)={1,a′=a and b′=b⊕(a0w),0,otherwise,(C_{n,w})_{(a',b'),(a,b)}= \begin{cases} 1,&a'=a\ \text{and}\ b'=b\mathbin{\oplus}(a0^w),\\ 0,&\text{otherwise}, \end{cases}(Cn,w​)(a′,b′),(a,b)​={1,0,​a′=a and b′=b⊕(a0w),otherwise,​

where a0wa0^wa0w is aaa followed by www false bits and ⊕\oplus⊕ is coordinatewise exclusive-or. Thus the first register is unchanged, the first nnn bits of the second register are exclusive-ored with it, and the last www bits are unchanged. No zero-initialization of either register is part of this definition. Zero values of nnn and www are included; when n=0n=0n=0, this is the identity.

QAlgorithms.Papers.Independent.Intakethird100.P03.cyclicFourierMatrix

For arbitrary natural numbers n,qn,qn,q, let [a]n[a]_n[a]n​ denote the length-nnn, most-significant-bit-first binary representation of a mod 2na\bmod 2^namod2n, and let ∣z⟩|z\rangle∣z⟩ denote the coordinate basis vector at an nnn-bit string zzz. The cyclic Fourier matrix is

Cn,q=∑a=0q−1∑b=0q−1exp⁡(2πi ba/q)q ∣[b]n⟩⟨[a]n∣.C_{n,q}= \sum_{a=0}^{q-1}\sum_{b=0}^{q-1} \frac{\exp(2\pi i\,ba/q)}{\sqrt q} \,|[b]_n\rangle\langle[a]_n|.Cn,q​=a=0∑q−1​b=0∑q−1​q​exp(2πiba/q)​∣[b]n​⟩⟨[a]n​∣.

Here ∣v⟩⟨u∣|v\rangle\langle u|∣v⟩⟨u∣ means the matrix with entries vxuy‾v_x\overline{u_y}vx​uy​​. There is no restriction 0<q≤2n0<q\le 2^n0<q≤2n: for q=0q=0q=0 the matrix is zero because the sum is empty, and for q>2nq>2^nq>2n binary encodings repeat. The case n=0n=0n=0 is included.

QAlgorithms.Papers.Independent.Intakethird100.P03.cyclicFourierVector

For natural numbers n,qn,qn,q and an integer aaa with 0≤a<q0\le a<q0≤a<q, define a complex vector indexed by nnn-bit strings by

va=∑b=0q−1exp⁡(2πi ba/q)q ∣[b]n⟩,v_a=\sum_{b=0}^{q-1} \frac{\exp(2\pi i\,ba/q)}{\sqrt q}\,|[b]_n\rangle,va​=b=0∑q−1​q​exp(2πiba/q)​∣[b]n​⟩,

where ∣z⟩|z\rangle∣z⟩ is the coordinate basis vector at the bit string zzz, and [b]n[b]_n[b]n​ is the length-nnn binary representation of b mod 2nb\bmod 2^nbmod2n, with the most significant bit first. No assumption q≤2nq\le 2^nq≤2n is made, so different summands may use the same basis vector. If q=0q=0q=0, there is no permissible index aaa; n=0n=0n=0 is allowed and has a single, empty bit string.

QAlgorithms.Papers.Independent.Intakethird100.P03.discreteLogInput

For every natural number qqq, units ζ,g\zeta,gζ,g of Z/qZ\mathbb Z/q\mathbb ZZ/qZ, and integer 2×22\times22×2 matrix BBB, this defines the concatenation of the natural-number encodings of qqq, the natural-number value of the underlying residue ζ\zetaζ, and the natural-number value of the underlying residue ggg, followed by the matrix encoding of BBB. For q>0q>0q>0, these residue values are the representatives in {0,…,q−1}\{0,\ldots,q-1\}{0,…,q−1}; when q=0q=0q=0, the residue type is Z\mathbb ZZ and its value function returns absolute value. The natural-number encoding of ttt consists of a unary length prefix of true bits, a false separator, and the binary digits of t+1t+1t+1 from least significant to most significant. The matrix encoding consists of the natural-number encoding of 222 followed by signed encodings of B00,B10,B01,B11B_{00},B_{10},B_{01},B_{11}B00​,B10​,B01​,B11​, where a signed encoding of zzz is the bit indicating z<0z<0z<0 followed by the natural-number encoding of ∣z∣|z|∣z∣. No primality or column-independence assumption is imposed by this definition.

QAlgorithms.Papers.Independent.Intakethird100.P03.eigenphaseTest

For every finite index type III equipped with decidable equality and every complex matrix UUU indexed by I×II\times II×I, this defines a matrix on {false,true}×I\{\mathrm{false},\mathrm{true}\}\times I{false,true}×I by

EU=(H⊗II) CU (H⊗II),H=12(111−1),E_U=(H\otimes I_I)\,C_U\,(H\otimes I_I), \qquad H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},EU​=(H⊗II​)CU​(H⊗II​),H=2​1​(11​1−1​),

with Boolean ordering false,true\mathrm{false},\mathrm{true}false,true, where (CU)(b,j),(b′,k)(C_U)_{(b,j),(b',k)}(CU​)(b,j),(b′,k)​ is 000 if b≠b′b\ne b'b=b′, is δjk\delta_{jk}δjk​ if b=b′=falseb=b'=\mathrm{false}b=b′=false, and is UjkU_{jk}Ujk​ if b=b′=trueb=b'=\mathrm{true}b=b′=true. No unitarity assumption on UUU is imposed, and III may be empty.

QAlgorithms.Papers.Independent.Intakethird100.P03.eigenspaceOutcomeProbability

For natural numbers r,d,mr,d,mr,d,m, write Bk={0,1}kB_k=\{0,1\}^kBk​={0,1}k, and let (Vv)v<r(V_v)_{v<r}(Vv​)v<r​ be any family of complex matrices on BdB_dBd​. Given an injection C:{0,…,m−1}↪{0,…,d−1}C:\{0,\ldots,m-1\}\hookrightarrow\{0,\ldots,d-1\}C:{0,…,m−1}↪{0,…,d−1}, an index v<rv<rv<r, and y∈Bmy\in B_my∈Bm​, this defines the real number

pV(v,y)=∑z∈Bdz∘C=y∣(Vv∣0d⟩)z∣2,p_V(v,y)= \sum_{\substack{z\in B_d\\z\circ C=y}} \left|\bigl(V_v|0^d\rangle\bigr)_z\right|^2,pV​(v,y)=z∈Bd​z∘C=y​∑​​(Vv​∣0d⟩)z​​2,

where ∣0d⟩|0^d\rangle∣0d⟩ is the coordinate vector of the all-false string and (z∘C)j=zC(j)(z\circ C)_j=z_{C(j)}(z∘C)j​=zC(j)​. Neither unitarity of VvV_vVv​ nor normalization of Vv∣0d⟩V_v|0^d\rangleVv​∣0d⟩ is assumed. The injection requires m≤dm\le dm≤d; when m=0m=0m=0, the restriction condition is automatic and the value is ∥Vv∣0d⟩∥22\|V_v|0^d\rangle\|_2^2∥Vv​∣0d⟩∥22​. When r=0r=0r=0, no argument v<rv<rv<r exists.

QAlgorithms.Papers.Independent.Intakethird100.P03.encodeBasis

For every natural number kkk and every integer k×kk\times kk×k matrix BBB, this defines a Boolean list beginning with an encoding of kkk, followed by encodings of all entries in column order: B00,B10,…,Bk−1,0B_{00},B_{10},\ldots,B_{k-1,0}B00​,B10​,…,Bk−1,0​, then the entries of column 111, and so on. The natural-number encoding of ttt consists of ∣s∣|s|∣s∣ true bits, one false bit, and sss, where sss lists the binary digits of t+1t+1t+1 from least significant to most significant. Each integer entry zzz is encoded by a sign bit, true exactly when z<0z<0z<0, followed by the natural-number encoding of ∣z∣|z|∣z∣. When k=0k=0k=0, there are no entry encodings, and the result is just the encoding of zero.

QAlgorithms.Papers.Independent.Intakethird100.P03.encodeInteger

For every integer zzz, this defines a Boolean list whose first bit is true exactly when z<0z<0z<0, followed by the natural-number encoding of ∣z∣|z|∣z∣. Explicitly, let sss be the binary digits of ∣z∣+1|z|+1∣z∣+1, listed from least significant to most significant; the remaining list consists of ∣s∣|s|∣s∣ true bits, one false bit, and then sss. Zero therefore has a false sign bit.

QAlgorithms.Papers.Independent.Intakethird100.P03.encodeNatural

For every natural number ttt, let bbb be the binary digit list of t+1t+1t+1, ordered from least significant to most significant bit, with false representing 000 and true representing 111. The encoding of ttt is the list consisting of ∣b∣|b|∣b∣ true bits, followed by one false bit, followed by bbb itself. This includes t=0t=0t=0, whose encoding is [true,false,true][\mathrm{true},\mathrm{false},\mathrm{true}][true,false,true].

QAlgorithms.Papers.Independent.Intakethird100.P03.encodeRational

For every rational number rrr, this defines the concatenation of the signed integer encoding of its reduced numerator and the natural-number encoding of its positive reduced denominator. The signed encoding of an integer zzz consists of the bit indicating z<0z<0z<0 followed by the natural-number encoding of ∣z∣|z|∣z∣. The natural-number encoding of ttt consists of ∣s∣|s|∣s∣ true bits, one false bit, and sss, where sss lists the binary digits of t+1t+1t+1 from least significant to most significant. This includes zero, whose reduced numerator is 000 and denominator is 111.

QAlgorithms.Papers.Independent.Intakethird100.P03.firstMeasurement

Let I,J,KI,J,KI,J,K be finite index types with decidable equality, let r∈Nr\in\mathbb Nr∈N, and let (Pv)v<r(P_v)_{v<r}(Pv​)v<r​ be complex matrices on III satisfying Pv†=PvP_v^\dagger=P_vPv†​=Pv​, Pv2=PvP_v^2=P_vPv2​=Pv​, and PvPu=0P_vP_u=0Pv​Pu​=0 for v≠uv\ne uv=u. Given arbitrary complex matrices (Vv)v<r(V_v)_{v<r}(Vv​)v<r​ on JJJ, this defines a matrix on I×(J×K)I\times(J\times K)I×(J×K) by

M1=∑v<rPv⊗(Vv⊗IK)+(II−∑v<rPv)⊗IJ×K.M_1=\sum_{v<r}P_v\otimes(V_v\otimes I_K) +\left(I_I-\sum_{v<r}P_v\right)\otimes I_{J\times K}.M1​=v<r∑​Pv​⊗(Vv​⊗IK​)+(II​−v<r∑​Pv​)⊗IJ×K​.

Thus the auxiliary matrix associated with vvv acts on the JJJ coordinate and leaves the KKK coordinate unchanged. The family of projectors need not sum to the identity, and no unitarity assumption is made on VvV_vVv​. Empty index types and r=0r=0r=0 are allowed; for r=0r=0r=0, the defined matrix is the identity.

QAlgorithms.Papers.Independent.Intakethird100.P03.garbageState

For every finite index type III, every pair of types J,KJ,KJ,K equipped with decidable equality, every pair of functions G:I→JG:I\to JG:I→J, g:I→Kg:I\to Kg:I→K, and every vector c∈CIc\in\mathbb C^Ic∈CI, this definition returns

∑x∈Ic(x) ∣G(x),g(x)⟩\sum_{x\in I}c(x)\,|G(x),g(x)\ranglex∈I∑​c(x)∣G(x),g(x)⟩

in the complex Euclidean space indexed by J×KJ\times KJ×K, where ∣j,k⟩|j,k\rangle∣j,k⟩ is the vector with coordinate 111 at (j,k)(j,k)(j,k) and 000 elsewhere. Neither JJJ nor KKK is required to be finite. No normalization or injectivity is assumed: the amplitude at (j,k)(j,k)(j,k) is the sum of c(x)c(x)c(x) over all xxx with G(x)=jG(x)=jG(x)=j and g(x)=kg(x)=kg(x)=k. If III is empty, the result is zero.

QAlgorithms.Papers.Independent.Intakethird100.P03.idealQ

For arbitrary natural numbers n,qn,qn,q, write [a]n[a]_n[a]n​ for the length-nnn binary representation of a mod 2na\bmod 2^namod2n, ∣z⟩|z\rangle∣z⟩ for the coordinate basis vector at zzz, and, for 0≤a<q0\le a<q0≤a<q, set

va=∑b=0q−1exp⁡(2πi ba/q)q∣[b]n⟩.v_a=\sum_{b=0}^{q-1} \frac{\exp(2\pi i\,ba/q)}{\sqrt q}|[b]_n\rangle.va​=b=0∑q−1​q​exp(2πiba/q)​∣[b]n​⟩.

The matrix called idealQ, indexed by pairs of nnn-bit strings, is

Qn,q=∑a=0q−1∣va⊗∣[a]n⟩⟩⟨va⊗∣0n⟩∣.Q_{n,q}= \sum_{a=0}^{q-1} \bigl|v_a\otimes|[a]_n\rangle\bigr\rangle \bigl\langle v_a\otimes|0^n\rangle\bigr|.Qn,q​=a=0∑q−1​​va​⊗∣[a]n​⟩⟩⟨va​⊗∣0n⟩​.

The tensor product has coordinates (v⊗u)(x,z)=vxuz(v\otimes u)_{(x,z)}=v_xu_z(v⊗u)(x,z)​=vx​uz​, and each outer product has entries equal to the target coordinate times the complex conjugate of the source coordinate. No positivity or width condition on qqq is imposed; q=0q=0q=0 gives the zero matrix, q>2nq>2^nq>2n permits repeated encodings, and n=0n=0n=0 is included.

QAlgorithms.Papers.Independent.Intakethird100.P03.idealTswapped

For arbitrary natural numbers n,qn,qn,q, write [a]n[a]_n[a]n​ for the length-nnn binary representation of a mod 2na\bmod 2^namod2n, ∣z⟩|z\rangle∣z⟩ for the coordinate basis vector at zzz, and define

va=∑b=0q−1exp⁡(2πi ba/q)q∣[b]n⟩(0≤a<q).v_a=\sum_{b=0}^{q-1} \frac{\exp(2\pi i\,ba/q)}{\sqrt q}|[b]_n\rangle \quad(0\le a<q).va​=b=0∑q−1​q​exp(2πiba/q)​∣[b]n​⟩(0≤a<q).

The matrix called idealTswapped, indexed by pairs of nnn-bit strings, is

Tn,q=∑a=0q−1∣va⊗∣[a]n⟩⟩⟨∣0n⟩⊗∣[a]n⟩∣.T_{n,q}= \sum_{a=0}^{q-1} \bigl|v_a\otimes|[a]_n\rangle\bigr\rangle \bigl\langle |0^n\rangle\otimes|[a]_n\rangle\bigr|.Tn,q​=a=0∑q−1​​va​⊗∣[a]n​⟩⟩⟨∣0n⟩⊗∣[a]n​⟩​.

Tensor coordinates are products of the two coordinates, and an outer product has entries equal to the target coordinate times the complex conjugate of the source coordinate. There is no restriction 0<q≤2n0<q\le 2^n0<q≤2n; an empty sum at q=0q=0q=0 gives zero, encodings repeat when q>2nq>2^nq>2n, and n=0n=0n=0 is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P03.inputXorMatrix

For every natural number nnn, every natural number www, and every Boolean string xxx of length nnn, this defines a complex matrix Xw,xX_{w,x}Xw,x​ whose rows and columns are indexed by Boolean strings of length n+wn+wn+w. Let x0wx0^wx0w denote xxx followed by www false bits. Its entries are

(Xw,x)y,z={1,y=z⊕(x0w),0,otherwise,(X_{w,x})_{y,z}= \begin{cases} 1,&y=z\mathbin{\oplus}(x0^w),\\ 0,&\text{otherwise}, \end{cases}(Xw,x​)y,z​={1,0,​y=z⊕(x0w),otherwise,​

where ⊕\oplus⊕ is coordinatewise Boolean exclusive-or. Thus the condition toggles the first nnn coordinates according to xxx and leaves the final www coordinates unchanged. Both n=0n=0n=0 and w=0w=0w=0 are allowed; for n=0n=0n=0 the matrix is the identity, including the one-dimensional matrix indexed by the unique empty string when also w=0w=0w=0.

QAlgorithms.Papers.Independent.Intakethird100.P03.integerBits

For every integer zzz, this definition assigns the natural number 2(⌊log⁡2(∣z∣+1)⌋+1)+12\bigl(\lfloor\log_2(|z|+1)\rfloor+1\bigr)+12(⌊log2​(∣z∣+1)⌋+1)+1, where ∣z∣|z|∣z∣ is regarded as a natural number and the logarithm is the integer base-two logarithm. The logarithm’s argument is always at least one; in particular, the value at z=0z=0z=0 is 333, and zzz and −z-z−z receive the same value.

QAlgorithms.Papers.Independent.Intakethird100.P03.kitaevGateBasis

This definition gives the union of all arity-one gates whose complex matrices are unitary with two specified gates: the arity-two gate mapping (u,v)(u,v)(u,v) to (u,v⊕u)(u,v\mathbin{\oplus}u)(u,v⊕u) and the arity-three gate mapping (u,v,w)(u,v,w)(u,v,w) to (u,v,w⊕(u∧v))(u,v,w\mathbin{\oplus}(u\land v))(u,v,w⊕(u∧v)). For each of the two specified gates, the matrix entry is 111 exactly when the output string is the stated image of the input string and is 000 otherwise; ⊕\oplus⊕ and ∧\land∧ denote Boolean exclusive-or and conjunction.

QAlgorithms.Papers.Independent.Intakethird100.P03.latticeBasisBits

For any natural number kkk, any additive subgroup S≤ZkS\leq\mathbb Z^kS≤Zk, and any additive group isomorphism b:Zk→Sb:\mathbb Z^k\to Sb:Zk→S, this definition assigns the natural number ∑i=0k−1∑j=0k−1[2(⌊log⁡2(∣(b(ei))j∣+1)⌋+1)+1]\sum_{i=0}^{k-1}\sum_{j=0}^{k-1}\left[2\bigl(\lfloor\log_2(|(b(e_i))_j|+1)\rfloor+1\bigr)+1\right]∑i=0k−1​∑j=0k−1​[2(⌊log2​(∣(b(ei​))j​∣+1)⌋+1)+1], where eie_iei​ has coordinate 111 at iii and 000 elsewhere, and b(ei)b(e_i)b(ei​) is viewed as an integer vector through the inclusion S⊆ZkS\subseteq\mathbb Z^kS⊆Zk. When k=0k=0k=0, both sums are empty and the value is zero.

QAlgorithms.Papers.Independent.Intakethird100.P03.majorityCode

For natural numbers r,mr,mr,m and any indexed collection (yi)i<r(y_i)_{i<r}(yi​)i<r​ of mmm-bit Boolean strings, this defines an (m+1)(m+1)(m+1)-bit string as follows: if some entire string y∈{0,1}my\in\{0,1\}^my∈{0,1}m occurs at strictly more than half the indices, meaning r<2∣{i<r:yi=y}∣r<2|\{i<r:y_i=y\}|r<2∣{i<r:yi​=y}∣, choose such a yyy and output its mmm bits followed by true\mathrm{true}true; if no such string exists, output mmm false bits followed by false\mathrm{false}false. A tie does not meet the strict inequality. For r=0r=0r=0, the output is the all-false (m+1)(m+1)(m+1)-bit string. For m=0m=0m=0, there is one empty input string, so the output is the one-bit string true\mathrm{true}true when r>0r>0r>0 and false\mathrm{false}false when r=0r=0r=0.

QAlgorithms.Papers.Independent.Intakethird100.P03.majorityTail

For every natural number rrr and every real number ϵ\epsilonϵ, this defines

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

The sum includes j=r/2j=r/2j=r/2 when rrr is even. There is no assumption that ϵ\epsilonϵ lies in [0,1][0,1][0,1]. The subtraction r−jr-jr−j is natural-number subtraction, and all included indices satisfy j≤rj\le rj≤r. Zero exponents have value 111, including 000^000; in particular, T(0,ϵ)=1T(0,\epsilon)=1T(0,ϵ)=1 for every real ϵ\epsilonϵ.

QAlgorithms.Papers.Independent.Intakethird100.P03.measurementMatrix

Let I,JI,JI,J be finite index types with decidable equality, let rrr be any natural number, and let (Pv)v<r(P_v)_{v<r}(Pv​)v<r​ be complex matrices on III satisfying Pv†=PvP_v^\dagger=P_vPv†​=Pv​, Pv2=PvP_v^2=P_vPv2​=Pv​, and PvPu=0P_vP_u=0Pv​Pu​=0 whenever v≠uv\ne uv=u. For any family (Vv)v<r(V_v)_{v<r}(Vv​)v<r​ of complex matrices on JJJ, this defines the matrix on I×JI\times JI×J

M=∑v<rPv⊗Vv+(II−∑v<rPv)⊗IJ.M=\sum_{v<r}P_v\otimes V_v+ \left(I_I-\sum_{v<r}P_v\right)\otimes I_J.M=v<r∑​Pv​⊗Vv​+(II​−v<r∑​Pv​)⊗IJ​.

No condition that ∑vPv=II\sum_vP_v=I_I∑v​Pv​=II​ is imposed, and the VvV_vVv​ are not required to be unitary. The index types may be empty; if r=0r=0r=0, the sums are empty and M=II×JM=I_{I\times J}M=II×J​.

QAlgorithms.Papers.Independent.Intakethird100.P03.notTau

This definition gives a gate of arity two whose complex matrix, indexed by two-bit output strings yyy and input strings xxx, has entry 111 exactly when y=(x0,x1⊕¬x0)y=(x_0,x_1\mathbin{\oplus}\neg x_0)y=(x0​,x1​⊕¬x0​), and entry 000 otherwise. Thus the first bit is retained, and the second bit is flipped exactly when the first bit is false.

QAlgorithms.Papers.Independent.Intakethird100.P03.orderAction

For every natural number qqq, every unit ggg of Z/qZ\mathbb Z/q\mathbb ZZ/qZ, every integer mmm, and every x∈Z/qZx\in\mathbb Z/q\mathbb Zx∈Z/qZ, this definition assigns gmxg^m xgmx, with the integer power taken in the group of units and then regarded as a ring element before multiplication. Negative exponents use the inverse of ggg. The definition also includes q=0q=0q=0, where the ring is Z\mathbb ZZ, and q=1q=1q=1, where the ring has one element.

QAlgorithms.Papers.Independent.Intakethird100.P03.outerMap

For every type III and every pair of complex Euclidean vectors v,uv,uv,u indexed by III, the outer map is the matrix indexed by I×II\times II×I whose entries are

outerMap⁡(v,u)ij=viuj‾.\operatorname{outerMap}(v,u)_{ij}=v_i\overline{u_j}.outerMap(v,u)ij​=vi​uj​​.

No finiteness, decidable-equality, or normalization assumption on I,v,uI,v,uI,v,u is required.

QAlgorithms.Papers.Independent.Intakethird100.P03.partialOracleCount

For every pair of natural numbers n,Tn,Tn,T and every finite list ccc of steps on TTT wires, this definition returns the number of entries constructed as oracle calls, counting each occurrence once and counting no known-gate entries. A call consists of an injection of nnn oracle wires into the TTT wires; a known-gate entry consists of an injectively placed gate that is either an arbitrary one-wire unitary, controlled NOT, or the three-wire permutation (a,b,c)↦(a,b,cxor(a∧b))(a,b,c)\mapsto(a,b,c\mathbin{\mathrm{xor}}(a\land b))(a,b,c)↦(a,b,cxor(a∧b)). Thus the result depends only on the constructors in the list, not on an oracle, a state, or the actual matrices. The empty list has count 000, and zero-wire calls, when present, still count as calls.

QAlgorithms.Papers.Independent.Intakethird100.P03.partialOracleMatrix

For natural numbers n,Tn,Tn,T, a finite list c=[s0,…,sℓ−1]c=[s_0,\ldots,s_{\ell-1}]c=[s0​,…,sℓ−1​] of steps on TTT wires, and a partial unitary UUU on the space indexed by nnn-bit strings, this definition gives the matrix Bℓ−1⋯B0B_{\ell-1}\cdots B_0Bℓ−1​⋯B0​, so that the steps act in list order on column vectors; the empty list gives the identity matrix. To define BjB_jBj​, write UUU as an isometry u:D→Ru:D\to Ru:D→R between complex subspaces and form Mab=(u(PDeb))aM_{ab}=(u(P_D e_b))_aMab​=(u(PD​eb​))a​, using orthogonal projection PDP_DPD​ and coordinate basis vectors ebe_beb​. A call step supplies MMM and an injection of its nnn wires into the TTT wires. A known step supplies a gate matrix and an injective wire assignment, with the gate either an arbitrary one-wire unitary, controlled NOT, or the three-wire permutation (a,b,c)↦(a,b,cxor(a∧b))(a,b,c)\mapsto(a,b,c\mathbin{\mathrm{xor}}(a\land b))(a,b,c)↦(a,b,cxor(a∧b)). For either kind of step, the embedded matrix has entry By∘w,z∘wB_{y\circ w,z\circ w}By∘w,z∘w​ when the full-register strings y,zy,zy,z agree outside the assigned wires, and entry 000 otherwise. No condition that the execution stays in the oracle domain is part of this definition, and n,T,ℓn,T,\elln,T,ℓ may be zero.

QAlgorithms.Papers.Independent.Intakethird100.P03.partialRun

For any finite index type III, any finite list [U0,…,Uℓ−1][U_0,\ldots,U_{\ell-1}][U0​,…,Uℓ−1​] of partial unitaries on CI\mathbb C^ICI, and any x∈CIx\in\mathbb C^Ix∈CI, write uj:Dj→Rju_j:D_j\to R_juj​:Dj​→Rj​ for the complex-linear isometric isomorphism of UjU_jUj​, and PDjP_{D_j}PDj​​ for orthogonal projection onto its domain. This definition starts with x0=xx_0=xx0​=x, successively sets xj+1=uj(PDjxj)x_{j+1}=u_j(P_{D_j}x_j)xj+1​=uj​(PDj​​xj​) in list order, and returns xℓx_\ellxℓ​. No compatibility between successive domains and ranges is required. An empty list returns xxx, and empty III is allowed.

QAlgorithms.Papers.Independent.Intakethird100.P03.phaseAncilla

For every real number ϕ\phiϕ, this defines a complex matrix indexed by {false,true}\{\mathrm{false},\mathrm{true}\}{false,true} as

Aϕ=H(100e2πiϕ)H,H=12(111−1),A_\phi=H \begin{pmatrix}1&0\\0&e^{2\pi i\phi}\end{pmatrix} H,\qquad H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},Aϕ​=H(10​0e2πiϕ​)H,H=2​1​(11​1−1​),

where the displayed ordering is false,true\mathrm{false},\mathrm{true}false,true. Equivalently,

Aϕ=12(1+e2πiϕ1−e2πiϕ1−e2πiϕ1+e2πiϕ).A_\phi=\frac12 \begin{pmatrix} 1+e^{2\pi i\phi}&1-e^{2\pi i\phi}\\ 1-e^{2\pi i\phi}&1+e^{2\pi i\phi} \end{pmatrix}.Aϕ​=21​(1+e2πiϕ1−e2πiϕ​1−e2πiϕ1+e2πiϕ​).

QAlgorithms.Papers.Independent.Intakethird100.P03.phaseDistance

For every pair of real numbers x,yx,yx,y, this defines min⁡(r,1−r)\min(r,1-r)min(r,1−r), where r=(x−y)−⌊x−y⌋r=(x-y)-\lfloor x-y\rfloorr=(x−y)−⌊x−y⌋ is the fractional part of x−yx-yx−y. Thus the value is zero when x−yx-yx−y is an integer, and is 1/21/21/2 when its fractional part is 1/21/21/2.

QAlgorithms.Papers.Independent.Intakethird100.P03.rBasis

This definition gives the set consisting of three gates: the one-bit gate mapping uuu to ¬u\neg u¬u; the two-bit gate mapping (u,v)(u,v)(u,v) to (u,v⊕u)(u,v\mathbin{\oplus}u)(u,v⊕u); and the three-bit gate mapping (u,v,w)(u,v,w)(u,v,w) to (u,v,w⊕(u∧v))(u,v,w\mathbin{\oplus}(u\land v))(u,v,w⊕(u∧v)). Each gate’s complex matrix has entry 111 when its row string is the stated image of its column string and entry 000 otherwise; ⊕\oplus⊕, ¬\neg¬, and ∧\land∧ denote Boolean exclusive-or, negation, and conjunction.

QAlgorithms.Papers.Independent.Intakethird100.P03.randomBitBell

This definition gives a vector in C{false,true}2\mathbb C^{\{\mathrm{false},\mathrm{true}\}^2}C{false,true}2 by starting with the tensor product of H∣false⟩H|\mathrm{false}\rangleH∣false⟩ and ∣false⟩|\mathrm{false}\rangle∣false⟩, and then applying the permutation matrix that sends ∣a,b⟩|a,b\rangle∣a,b⟩ to ∣a,b⊕a⟩|a,b\mathbin{\oplus}a\rangle∣a,b⊕a⟩, where the kets are standard coordinate basis vectors and, in the order false, true,

H=12(111−1).H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.H=2​1​(11​1−1​).

The tensor product has amplitude equal to the product of the two component amplitudes.

QAlgorithms.Papers.Independent.Intakethird100.P03.rationalRecoveryInput

For every pair of natural numbers nnn and numerator\mathrm{numerator}numerator, this defines a Boolean list consisting of nnn true bits, one false bit, and a block of exactly 2n+12n+12n+1 bits encoding numerator mod 22n+1\mathrm{numerator}\bmod 2^{2n+1}numeratormod22n+1 in most-significant-first order, including leading zeros. Equivalently, if the final block is (b0,…,b2n)(b_0,\ldots,b_{2n})(b0​,…,b2n​), then ∑i=02n1{bi=true}22n−i=numerator mod 22n+1\sum_{i=0}^{2n}\mathbf1_{\{b_i=\mathrm{true}\}}2^{2n-i}=\mathrm{numerator}\bmod 2^{2n+1}∑i=02n​1{bi​=true}​22n−i=numeratormod22n+1. There is no bound on the supplied numerator, so values differing by a multiple of 22n+12^{2n+1}22n+1 produce the same list. When n=0n=0n=0, the list is a false separator followed by the numerator’s parity bit.

QAlgorithms.Papers.Independent.Intakethird100.P03.repeatedMajorityLaw

Let n,m,w,rn,m,w,rn,m,w,r be arbitrary natural numbers, let UUU be any complex matrix indexed by pairs of (n+w)(n+w)(n+w)-bit strings, let 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} be an injection, let xxx be an nnn-bit string, and let yyy be an (m+1)(m+1)(m+1)-bit string. Write ∣x,0w⟩|x,0^w\rangle∣x,0w⟩ for the coordinate basis vector with input xxx followed by www false bits, and define Px(s)=∑z: z∘o=s∣(U∣x,0w⟩)z∣2P_x(s)=\sum_{z:\,z\circ o=s}|(U|x,0^w\rangle)_z|^2Px​(s)=∑z:z∘o=s​∣(U∣x,0w⟩)z​∣2 for each mmm-bit string sss. For a list (si)i<r(s_i)_{i<r}(si​)i<r​, define its majority code to be sss followed by true if some string sss occurs strictly more than r/2r/2r/2 times; if no such string exists, define the code to be 0m0^m0m followed by false. The repeated majority law is

∑(si)i<r1{majority code of (si)=y}∏i<rPx(si).\sum_{(s_i)_{i<r}} \mathbf 1_{\{\text{majority code of }(s_i)=y\}} \prod_{i<r}P_x(s_i).(si​)i<r​∑​1{majority code of (si​)=y}​i<r∏​Px​(si​).

No unitarity or normalization hypothesis is imposed on UUU. Zero values of the natural parameters are included whenever the injection exists; in particular, for r=0r=0r=0, the value is 111 at y=(0m,false)y=(0^m,\mathrm{false})y=(0m,false) and 000 elsewhere.

QAlgorithms.Papers.Independent.Intakethird100.P03.rotatedZero

For every natural number bbb and every Boolean string xxx of length bbb, let

αx=2π∑i=0b−11{xi=true}2i+1.\alpha_x=2\pi\sum_{i=0}^{b-1}\frac{\mathbf 1_{\{x_i=\mathrm{true}\}}}{2^{i+1}}.αx​=2πi=0∑b−1​2i+11{xi​=true}​​.

This definition gives the vector in the complex Euclidean space indexed by Boolean strings of length b+1b+1b+1 whose amplitude at a string zzz is zero unless its first bbb bits equal xxx; when they do, the amplitude is cos⁡αx\cos\alpha_xcosαx​ if its last bit is false and sin⁡αx\sin\alpha_xsinαx​ if its last bit is true. Equivalently, it is cos⁡αx ∣x,false⟩+sin⁡αx ∣x,true⟩\cos\alpha_x\,|x,\mathrm{false}\rangle+\sin\alpha_x\,|x,\mathrm{true}\ranglecosαx​∣x,false⟩+sinαx​∣x,true⟩, where the kets are standard coordinate basis vectors. For b=0b=0b=0, this is the one-qubit basis vector ∣false⟩|\mathrm{false}\rangle∣false⟩.

QAlgorithms.Papers.Independent.Intakethird100.P03.secondMeasurement

Let I,J,KI,J,KI,J,K be finite index types with decidable equality, let r∈Nr\in\mathbb Nr∈N, and let (Pv)v<r(P_v)_{v<r}(Pv​)v<r​ be complex matrices on III satisfying Pv†=PvP_v^\dagger=P_vPv†​=Pv​, Pv2=PvP_v^2=P_vPv2​=Pv​, and PvPu=0P_vP_u=0Pv​Pu​=0 for v≠uv\ne uv=u. Given arbitrary complex matrices (Vv)v<r(V_v)_{v<r}(Vv​)v<r​ on KKK, this defines a matrix on I×(J×K)I\times(J\times K)I×(J×K) by

M2=∑v<rPv⊗(IJ⊗Vv)+(II−∑v<rPv)⊗IJ×K.M_2=\sum_{v<r}P_v\otimes(I_J\otimes V_v) +\left(I_I-\sum_{v<r}P_v\right)\otimes I_{J\times K}.M2​=v<r∑​Pv​⊗(IJ​⊗Vv​)+(II​−v<r∑​Pv​)⊗IJ×K​.

Thus the auxiliary matrix associated with vvv acts on the KKK coordinate and leaves the JJJ coordinate unchanged. The family of projectors need not sum to the identity, and no unitarity assumption is made on VvV_vVv​. Empty index types and r=0r=0r=0 are allowed; for r=0r=0r=0, the defined matrix is the identity.

QAlgorithms.Papers.Independent.Intakethird100.P03.stabilizer

For any natural numbers k,nk,nk,n, any M⊆{0,1}nM\subseteq\{0,1\}^nM⊆{0,1}n, any total map run⁡:Zk×{0,1}n→{0,1}n\operatorname{run}:\mathbb Z^k\times\{0,1\}^n\to\{0,1\}^nrun:Zk×{0,1}n→{0,1}n that preserves MMM and satisfies run⁡(0,x)=x\operatorname{run}(0,x)=xrun(0,x)=x and run⁡(g+h,x)=run⁡(g,run⁡(h,x))\operatorname{run}(g+h,x)=\operatorname{run}(g,\operatorname{run}(h,x))run(g+h,x)=run(g,run(h,x)) for all g,hg,hg,h and x∈Mx\in Mx∈M, and any a∈{0,1}na\in\{0,1\}^na∈{0,1}n together with the hypothesis a∈Ma\in Ma∈M, this definition gives the additive subgroup {g∈Zk:run⁡(g,a)=a}\{g\in\mathbb Z^k:\operatorname{run}(g,a)=a\}{g∈Zk:run(g,a)=a}. Thus membership means exactly that ggg fixes aaa; this set contains zero and is closed under addition and additive inverses. The supplied point a∈Ma\in Ma∈M excludes the case M=∅M=\varnothingM=∅.

QAlgorithms.Papers.Independent.Intakethird100.P03.subspaceProbability

For every finite type III and arbitrary complex matrices ρ,P∈CI×I\rho,P\in\mathbb C^{I\times I}ρ,P∈CI×I, the defined real number is

subspaceProbability⁡(ρ,P)=Re⁡tr⁡(ρP).\operatorname{subspaceProbability}(\rho,P) = \operatorname{Re}\operatorname{tr}(\rho P).subspaceProbability(ρ,P)=Retr(ρP).

Neither a density-matrix condition on ρ\rhoρ nor a projector condition on PPP is imposed by this definition. If III is empty, the trace is an empty sum and the value is 000.

QAlgorithms.Papers.Independent.Intakethird100.P03.xorIntoFirst

For every natural number nnn, this defines the complex matrix on pairs of nnn-bit strings whose entry in row yyy and column x=(x1,x2)x=(x_1,x_2)x=(x1​,x2​) is 111 if

y=(x1⊕x2,x2)y=(x_1\mathbin{\oplus}x_2,x_2)y=(x1​⊕x2​,x2​)

and is 000 otherwise, where ⊕\oplus⊕ denotes coordinatewise exclusive-or. For n=0n=0n=0, both registers have only the empty string, so the matrix is the one-dimensional identity.

QAlgorithms.Papers.Independent.Intakethird100.P03.xorIntoSecond

For every natural number nnn, this defines the complex matrix on pairs of nnn-bit strings whose entry in row yyy and column x=(x1,x2)x=(x_1,x_2)x=(x1​,x2​) is 111 if

y=(x1,x2⊕x1)y=(x_1,x_2\mathbin{\oplus}x_1)y=(x1​,x2​⊕x1​)

and is 000 otherwise, where ⊕\oplus⊕ denotes coordinatewise exclusive-or. For n=0n=0n=0, both registers have only the empty string, so the matrix is the one-dimensional identity.

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