Definitions for Quantum measurements and the Abelian Stabilizer Problem
DefinitionQAlgorithms_Papers_Independent_Intakethird100_P03The 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.
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Intakethird100.P03.ASPAction
For natural numbers , including zero, and a set , an consists of a total function satisfying the following conditions: for every and , one has , , and , where addition in is coordinatewise. These conditions impose no requirements on inputs ; when is empty, all three conditions are vacuous.
QAlgorithms.Papers.Independent.Intakethird100.P03.Computes
For natural numbers , a complex matrix indexed by the bit strings of length , an injection , a subset , a function , and a real number , the defined property means that
Here is the coordinate vector at followed by false bits, and acts by ordinary matrix-vector multiplication. This definition imposes no unitarity condition on and no restriction on . It is vacuously satisfied when is empty. All lengths may be ; when , every satisfies the output condition.
QAlgorithms.Papers.Independent.Intakethird100.P03.ControlledDomain
For every natural number , every partial unitary consisting of an isometry between complex subspaces , and every vector , this predicate says that both vectors
belong to , where is the bit string whose first bit is and whose remaining bits are . Neither slice nor the full vector is required to be normalized or nonzero. For , each slice has one coordinate, indexed by the unique empty bit string, and both resulting vectors must still belong to .
QAlgorithms.Papers.Independent.Intakethird100.P03.IsCanonicalBasis
For every natural number and integer matrices and , this predicate requires that multiplication by be injective on ; that ; that whenever ; that for every ; and that whenever . In particular, the upper off-diagonal entry is bounded by the diagonal entry in its own row. When , all these conditions hold for the empty matrices.
QAlgorithms.Papers.Independent.Intakethird100.P03.IsLatticeBasis
For every natural number and every integer matrix , this predicate means that multiplication by is injective on integer vectors: for every , if for every , then . For , this condition holds for the unique empty matrix.
QAlgorithms.Papers.Independent.Intakethird100.P03.OrthogonalProjectorFamily
For a finite type with decidable equality and a natural number , an object of this structure consists of complex matrices , indexed by , together with the requirements that and for every , and whenever . There is no requirement that these matrices sum to the identity, have positive rank, or be distinct. Zero projectors are allowed. When , the family is empty and all requirements are vacuous; may also be empty.
QAlgorithms.Papers.Independent.Intakethird100.P03.OrthogonalProjectorFamily.support
For every finite type with decidable equality, every natural number , and every family of complex matrices satisfying , , and for distinct indices, its support is defined to be the matrix
The family is not required to sum to the identity. For , this definition gives the zero matrix, and the index type is allowed to be empty.
QAlgorithms.Papers.Independent.Intakethird100.P03.PartialApprox
For any finite index type , let and be partial unitaries on : each consists of domain and range complex subspaces and , together with complex-linear isometric isomorphisms and . For any real number , the relation defined here holds precisely when , , and
The norms are the Euclidean norms in the ambient space . No nonnegativity condition on is included; if , the inequality can hold only when . Empty is allowed.
QAlgorithms.Papers.Independent.Intakethird100.P03.PartialOracleStep.matrix
For natural numbers and a partial unitary on the complex space indexed by -bit strings, this definition assigns a complex matrix on -bit strings to each step. Write as an isometry between subspaces and let , where is orthogonal projection onto and 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 call step uses and its stored injection. In either case, embedding a matrix on wires along an injection means assigning the entry
for -bit strings . 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 , this inductive definition specifies a type of steps with two constructors. A known step contains a gate , a proof that it belongs to the prescribed gate set, and an injective assignment of its input wires to the available wires. A gate consists of a natural-number arity and a complex matrix indexed by -bit strings. The prescribed set contains every unitary gate of arity , the two-wire gate sending to , and the three-wire gate sending to ; the latter two have matrix entries at the indicated output for each input and elsewhere. A call step contains only an injection from the oracle wires into the available wires. No oracle or state is stored in a call step. Zero values of and are included: a call has no possible wire injection when , whereas for its wire assignment is the empty injection.
QAlgorithms.Papers.Independent.Intakethird100.P03.PartialSequenceApprox
For any finite index type , possibly empty, let with its Euclidean norm. A partial unitary consists of two complex linear subspaces and a complex linear isometric isomorphism ; its application to an arbitrary vector means , where is orthogonal projection onto . For any finite lists of such partial unitaries, any subspaces , and any real , the defined condition is the conjunction
where and 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 need not equal . No sign restriction is imposed on ; if , the displayed norm bound can hold only when .
QAlgorithms.Papers.Independent.Intakethird100.P03.PartialUnitary.apply
For any finite index type , any partial unitary consisting of complex subspaces and a complex-linear isometric isomorphism , and any vector , this definition returns
viewed as a vector in , where is the orthogonal projection onto . 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 may be empty.
QAlgorithms.Papers.Independent.Intakethird100.P03.PartialUnitary.inverse
For every finite type and every partial unitary consisting of complex linear subspaces and a bijective complex linear isometry , its inverse is defined to be the partial unitary with domain , range , and isometry . This definition also applies to zero subspaces and to an empty index type .
QAlgorithms.Papers.Independent.Intakethird100.P03.PartialUnitary.matrix
For every finite type equipped with decidable equality and every partial unitary on , consisting of complex linear subspaces and a surjective complex linear isometry , this definition assigns the complex matrix
where is orthogonal projection onto , has coordinate at and elsewhere, and vectors in are viewed as vectors in . 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 may be empty, in which case this is the empty matrix.
QAlgorithms.Papers.Independent.Intakethird100.P03.PartialUnitary
For a finite type , an object of this structure consists of two complex linear subspaces , called its domain and range, together with a bijective complex linear isometry , where both subspaces inherit the Euclidean norm. Neither subspace is required to be the whole ambient space or to be nonzero. The index type may be empty, in which case both subspaces are necessarily the zero space. The structure specifies the isometry on , without specifying an action on vectors outside .
QAlgorithms.Papers.Independent.Intakethird100.P03.ValidPartialExecution
For natural numbers , a finite list of steps on wires, a partial unitary on the space indexed by -bit strings, and any vector , this predicate requires norm preservation at every call step and places no requirement at known steps. More precisely, write as an isometry between subspaces and let represent , with the orthogonal projection onto . For a call at position with wire injection , let be the result of applying the first step matrices to in list order; the requirement is
Here if agree outside the range of , and is otherwise. Call-step matrices are ; known-step matrices are embeddings of their stored gates, which are arbitrary one-wire unitaries, controlled NOT, or . The incoming vector at the first position is , because the empty prefix has identity matrix. There is no normalization requirement on ; 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 , the amplification rate is defined by
There is no restriction on . The real square root is taken to be zero for negative arguments, so when or , and also at .
QAlgorithms.Papers.Independent.Intakethird100.P03.andTau
This definition gives a gate of arity three whose complex matrix, indexed by three-bit output strings and input strings , has entry exactly when , and entry otherwise. Here is Boolean exclusive-or and 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 and every Boolean string of length , this definition assigns the real angle
Thus the first bit receives weight , the second weight , and so on. When , 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 to ; the three-bit gate mapping to ; and the two-bit gate mapping to . Each gate’s complex matrix has entry when its row string is the stated image of its column string and entry otherwise; , , and denote Boolean exclusive-or, negation, and conjunction.
QAlgorithms.Papers.Independent.Intakethird100.P03.canonicalBasis
For every natural number and integer matrix , this defines a matrix by choosing some integer matrix satisfying the following conditions, if one exists: multiplication by is injective on , its integer column span equals that of , for , every is positive, and for . If no such exists, the result is the zero matrix. This definition itself imposes no hypothesis on and specifies no selection rule among multiple qualifying matrices.
QAlgorithms.Papers.Independent.Intakethird100.P03.coherentImage
For every finite index type , every type equipped with decidable equality, every function , and every vector , this definition returns
in the complex Euclidean space indexed by , where has coordinate at and elsewhere. The type need not be finite, and neither normalization of nor injectivity of is assumed. Its amplitude at is ; if is empty, the result is zero.
QAlgorithms.Papers.Independent.Intakethird100.P03.columnLattice
For every natural number and every integer matrix , this defines the set , where . Thus all integer coefficient vectors are allowed, without any independence assumption on the columns. For , this set contains the unique empty vector.
QAlgorithms.Papers.Independent.Intakethird100.P03.copyInputMatrix
For every pair of natural numbers , this defines a complex matrix indexed by pairs consisting of a Boolean string of length and a Boolean string of length . For row and column , its entry is
where is followed by false bits and is coordinatewise exclusive-or. Thus the first register is unchanged, the first bits of the second register are exclusive-ored with it, and the last bits are unchanged. No zero-initialization of either register is part of this definition. Zero values of and are included; when , this is the identity.
QAlgorithms.Papers.Independent.Intakethird100.P03.cyclicFourierMatrix
For arbitrary natural numbers , let denote the length-, most-significant-bit-first binary representation of , and let denote the coordinate basis vector at an -bit string . The cyclic Fourier matrix is
Here means the matrix with entries . There is no restriction : for the matrix is zero because the sum is empty, and for binary encodings repeat. The case is included.
QAlgorithms.Papers.Independent.Intakethird100.P03.cyclicFourierVector
For natural numbers and an integer with , define a complex vector indexed by -bit strings by
where is the coordinate basis vector at the bit string , and is the length- binary representation of , with the most significant bit first. No assumption is made, so different summands may use the same basis vector. If , there is no permissible index ; is allowed and has a single, empty bit string.
QAlgorithms.Papers.Independent.Intakethird100.P03.discreteLogInput
For every natural number , units of , and integer matrix , this defines the concatenation of the natural-number encodings of , the natural-number value of the underlying residue , and the natural-number value of the underlying residue , followed by the matrix encoding of . For , these residue values are the representatives in ; when , the residue type is and its value function returns absolute value. The natural-number encoding of consists of a unary length prefix of true bits, a false separator, and the binary digits of from least significant to most significant. The matrix encoding consists of the natural-number encoding of followed by signed encodings of , where a signed encoding of is the bit indicating followed by the natural-number encoding of . No primality or column-independence assumption is imposed by this definition.
QAlgorithms.Papers.Independent.Intakethird100.P03.eigenphaseTest
For every finite index type equipped with decidable equality and every complex matrix indexed by , this defines a matrix on by
with Boolean ordering , where is if , is if , and is if . No unitarity assumption on is imposed, and may be empty.
QAlgorithms.Papers.Independent.Intakethird100.P03.eigenspaceOutcomeProbability
For natural numbers , write , and let be any family of complex matrices on . Given an injection , an index , and , this defines the real number
where is the coordinate vector of the all-false string and . Neither unitarity of nor normalization of is assumed. The injection requires ; when , the restriction condition is automatic and the value is . When , no argument exists.
QAlgorithms.Papers.Independent.Intakethird100.P03.encodeBasis
For every natural number and every integer matrix , this defines a Boolean list beginning with an encoding of , followed by encodings of all entries in column order: , then the entries of column , and so on. The natural-number encoding of consists of true bits, one false bit, and , where lists the binary digits of from least significant to most significant. Each integer entry is encoded by a sign bit, true exactly when , followed by the natural-number encoding of . When , there are no entry encodings, and the result is just the encoding of zero.
QAlgorithms.Papers.Independent.Intakethird100.P03.encodeInteger
For every integer , this defines a Boolean list whose first bit is true exactly when , followed by the natural-number encoding of . Explicitly, let be the binary digits of , listed from least significant to most significant; the remaining list consists of true bits, one false bit, and then . Zero therefore has a false sign bit.
QAlgorithms.Papers.Independent.Intakethird100.P03.encodeNatural
For every natural number , let be the binary digit list of , ordered from least significant to most significant bit, with false representing and true representing . The encoding of is the list consisting of true bits, followed by one false bit, followed by itself. This includes , whose encoding is .
QAlgorithms.Papers.Independent.Intakethird100.P03.encodeRational
For every rational number , 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 consists of the bit indicating followed by the natural-number encoding of . The natural-number encoding of consists of true bits, one false bit, and , where lists the binary digits of from least significant to most significant. This includes zero, whose reduced numerator is and denominator is .
QAlgorithms.Papers.Independent.Intakethird100.P03.firstMeasurement
Let be finite index types with decidable equality, let , and let be complex matrices on satisfying , , and for . Given arbitrary complex matrices on , this defines a matrix on by
Thus the auxiliary matrix associated with acts on the coordinate and leaves the coordinate unchanged. The family of projectors need not sum to the identity, and no unitarity assumption is made on . Empty index types and are allowed; for , the defined matrix is the identity.
QAlgorithms.Papers.Independent.Intakethird100.P03.garbageState
For every finite index type , every pair of types equipped with decidable equality, every pair of functions , , and every vector , this definition returns
in the complex Euclidean space indexed by , where is the vector with coordinate at and elsewhere. Neither nor is required to be finite. No normalization or injectivity is assumed: the amplitude at is the sum of over all with and . If is empty, the result is zero.
QAlgorithms.Papers.Independent.Intakethird100.P03.idealQ
For arbitrary natural numbers , write for the length- binary representation of , for the coordinate basis vector at , and, for , set
The matrix called idealQ, indexed by pairs of -bit strings, is
The tensor product has coordinates , 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 is imposed; gives the zero matrix, permits repeated encodings, and is included.
QAlgorithms.Papers.Independent.Intakethird100.P03.idealTswapped
For arbitrary natural numbers , write for the length- binary representation of , for the coordinate basis vector at , and define
The matrix called idealTswapped, indexed by pairs of -bit strings, is
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 ; an empty sum at gives zero, encodings repeat when , and is allowed.
QAlgorithms.Papers.Independent.Intakethird100.P03.inputXorMatrix
For every natural number , every natural number , and every Boolean string of length , this defines a complex matrix whose rows and columns are indexed by Boolean strings of length . Let denote followed by false bits. Its entries are
where is coordinatewise Boolean exclusive-or. Thus the condition toggles the first coordinates according to and leaves the final coordinates unchanged. Both and are allowed; for the matrix is the identity, including the one-dimensional matrix indexed by the unique empty string when also .
QAlgorithms.Papers.Independent.Intakethird100.P03.integerBits
For every integer , this definition assigns the natural number , where 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 is , and and 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 to and the arity-three gate mapping to . For each of the two specified gates, the matrix entry is exactly when the output string is the stated image of the input string and is otherwise; and denote Boolean exclusive-or and conjunction.
QAlgorithms.Papers.Independent.Intakethird100.P03.latticeBasisBits
For any natural number , any additive subgroup , and any additive group isomorphism , this definition assigns the natural number , where has coordinate at and elsewhere, and is viewed as an integer vector through the inclusion . When , both sums are empty and the value is zero.
QAlgorithms.Papers.Independent.Intakethird100.P03.majorityCode
For natural numbers and any indexed collection of -bit Boolean strings, this defines an -bit string as follows: if some entire string occurs at strictly more than half the indices, meaning , choose such a and output its bits followed by ; if no such string exists, output false bits followed by . A tie does not meet the strict inequality. For , the output is the all-false -bit string. For , there is one empty input string, so the output is the one-bit string when and when .
QAlgorithms.Papers.Independent.Intakethird100.P03.majorityTail
For every natural number and every real number , this defines
The sum includes when is even. There is no assumption that lies in . The subtraction is natural-number subtraction, and all included indices satisfy . Zero exponents have value , including ; in particular, for every real .
QAlgorithms.Papers.Independent.Intakethird100.P03.measurementMatrix
Let be finite index types with decidable equality, let be any natural number, and let be complex matrices on satisfying , , and whenever . For any family of complex matrices on , this defines the matrix on
No condition that is imposed, and the are not required to be unitary. The index types may be empty; if , the sums are empty and .
QAlgorithms.Papers.Independent.Intakethird100.P03.notTau
This definition gives a gate of arity two whose complex matrix, indexed by two-bit output strings and input strings , has entry exactly when , and entry 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 , every unit of , every integer , and every , this definition assigns , 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 . The definition also includes , where the ring is , and , where the ring has one element.
QAlgorithms.Papers.Independent.Intakethird100.P03.outerMap
For every type and every pair of complex Euclidean vectors indexed by , the outer map is the matrix indexed by whose entries are
No finiteness, decidable-equality, or normalization assumption on is required.
QAlgorithms.Papers.Independent.Intakethird100.P03.partialOracleCount
For every pair of natural numbers and every finite list of steps on 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 oracle wires into the 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 . 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 , and zero-wire calls, when present, still count as calls.
QAlgorithms.Papers.Independent.Intakethird100.P03.partialOracleMatrix
For natural numbers , a finite list of steps on wires, and a partial unitary on the space indexed by -bit strings, this definition gives the matrix , so that the steps act in list order on column vectors; the empty list gives the identity matrix. To define , write as an isometry between complex subspaces and form , using orthogonal projection and coordinate basis vectors . A call step supplies and an injection of its wires into the 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 . For either kind of step, the embedded matrix has entry when the full-register strings agree outside the assigned wires, and entry otherwise. No condition that the execution stays in the oracle domain is part of this definition, and may be zero.
QAlgorithms.Papers.Independent.Intakethird100.P03.partialRun
For any finite index type , any finite list of partial unitaries on , and any , write for the complex-linear isometric isomorphism of , and for orthogonal projection onto its domain. This definition starts with , successively sets in list order, and returns . No compatibility between successive domains and ranges is required. An empty list returns , and empty is allowed.
QAlgorithms.Papers.Independent.Intakethird100.P03.phaseAncilla
For every real number , this defines a complex matrix indexed by as
where the displayed ordering is . Equivalently,
QAlgorithms.Papers.Independent.Intakethird100.P03.phaseDistance
For every pair of real numbers , this defines , where is the fractional part of . Thus the value is zero when is an integer, and is when its fractional part is .
QAlgorithms.Papers.Independent.Intakethird100.P03.rBasis
This definition gives the set consisting of three gates: the one-bit gate mapping to ; the two-bit gate mapping to ; and the three-bit gate mapping to . Each gate’s complex matrix has entry when its row string is the stated image of its column string and entry otherwise; , , and denote Boolean exclusive-or, negation, and conjunction.
QAlgorithms.Papers.Independent.Intakethird100.P03.randomBitBell
This definition gives a vector in by starting with the tensor product of and , and then applying the permutation matrix that sends to , where the kets are standard coordinate basis vectors and, in the order false, true,
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 and , this defines a Boolean list consisting of true bits, one false bit, and a block of exactly bits encoding in most-significant-first order, including leading zeros. Equivalently, if the final block is , then . There is no bound on the supplied numerator, so values differing by a multiple of produce the same list. When , the list is a false separator followed by the numerator’s parity bit.
QAlgorithms.Papers.Independent.Intakethird100.P03.repeatedMajorityLaw
Let be arbitrary natural numbers, let be any complex matrix indexed by pairs of -bit strings, let be an injection, let be an -bit string, and let be an -bit string. Write for the coordinate basis vector with input followed by false bits, and define for each -bit string . For a list , define its majority code to be followed by true if some string occurs strictly more than times; if no such string exists, define the code to be followed by false. The repeated majority law is
No unitarity or normalization hypothesis is imposed on . Zero values of the natural parameters are included whenever the injection exists; in particular, for , the value is at and elsewhere.
QAlgorithms.Papers.Independent.Intakethird100.P03.rotatedZero
For every natural number and every Boolean string of length , let
This definition gives the vector in the complex Euclidean space indexed by Boolean strings of length whose amplitude at a string is zero unless its first bits equal ; when they do, the amplitude is if its last bit is false and if its last bit is true. Equivalently, it is , where the kets are standard coordinate basis vectors. For , this is the one-qubit basis vector .
QAlgorithms.Papers.Independent.Intakethird100.P03.secondMeasurement
Let be finite index types with decidable equality, let , and let be complex matrices on satisfying , , and for . Given arbitrary complex matrices on , this defines a matrix on by
Thus the auxiliary matrix associated with acts on the coordinate and leaves the coordinate unchanged. The family of projectors need not sum to the identity, and no unitarity assumption is made on . Empty index types and are allowed; for , the defined matrix is the identity.
QAlgorithms.Papers.Independent.Intakethird100.P03.stabilizer
For any natural numbers , any , any total map that preserves and satisfies and for all and , and any together with the hypothesis , this definition gives the additive subgroup . Thus membership means exactly that fixes ; this set contains zero and is closed under addition and additive inverses. The supplied point excludes the case .
QAlgorithms.Papers.Independent.Intakethird100.P03.subspaceProbability
For every finite type and arbitrary complex matrices , the defined real number is
Neither a density-matrix condition on nor a projector condition on is imposed by this definition. If is empty, the trace is an empty sum and the value is .
QAlgorithms.Papers.Independent.Intakethird100.P03.xorIntoFirst
For every natural number , this defines the complex matrix on pairs of -bit strings whose entry in row and column is if
and is otherwise, where denotes coordinatewise exclusive-or. For , 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 , this defines the complex matrix on pairs of -bit strings whose entry in row and column is if
and is otherwise, where denotes coordinatewise exclusive-or. For , both registers have only the empty string, so the matrix is the one-dimensional identity.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.