The shift circuit maps the pivot word of to the codeword
ProvedOPI.SymEnc.lin_basisLet be given by a field presentation, each element encoded in qubits. A register consists of blocks of qubits (jointly injective); a word is stored as , block holding the encoding of . Let and let be injective with (identity on the pivot columns, as for a basis in reduced row-echelon form). For , is the word with in position and elsewhere.
The circuit performs, for every row and every non-pivot column , the shift by table lookups, using a scratch register of qubits, ancillas and a flag qubit . The layout hypotheses say that for each such pair the wires of , , , , are pairwise distinct, , , and no wire of lies in , or equals .
Statement. For every and every vector on the remaining qubits that vanishes unless , , are all , the unitary of the compiled circuit satisfies
Here denotes the vector .
In the state preparation, a repeat-until-success step puts a uniform into the pivot blocks of ; this circuit then turns into when the rows of form a basis of , without a separate coefficient register.
import Definitions.Def_TwoFoldOPI_CL_Part02
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI OPI.SymEnc
open QAlgorithms
variable {N : ℕ}
open TwoFoldOPI
variable {F : AvgCaseTI.FieldPres} {n m kd : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
variable (Rr : Fin m → (Fin L ↪ Fin n)) (hRd : ∀ i i' j j', Rr i j = Rr i' j' → i = i' ∧ j = j')
(piv : Fin kd → Fin m) (hpivi : Function.Injective piv)
variable (G : Fin kd → Fin m → F.F) (hpiv : ∀ j j', G j (piv j') = if j = j' then 1 else 0)
(Z as : List (Fin n)) (f : Fin n)
(hnd : ∀ p : Fin kd × Fin m, (∀ j', piv j' ≠ p.2) → (List.ofFn (Rr (piv p.1)) ++ List.ofFn (Rr p.2) ++ Z ++ as ++ [f]).Nodup)
(hZ : L = Z.length) (hlen : L + L ≤ as.length + 2)
(hsc : ∀ i j, Rr i j ≠ f ∧ (∀ q ∈ Z, Rr i j ≠ q) ∧ ∀ q ∈ as, Rr i j ≠ q)
include hRd hpivi hpiv hnd hZ hlen hsc
theorem OPI.SymEnc.lin_basis (a : Fin kd → F.F) (G0 : Qubits n → ℂ) (hG0 : ∀ z, G0 z ≠ 0 → scrClean Z as f z) :
(Circuit.unitary (revCirc (linCirc Rr piv G Z as f))).mulVec
(bfac (wRof (F := F) Rr hRd) (fun y => if y = encW F m (vPiv piv a) then 1 else 0) G0) =
bfac (wRof (F := F) Rr hRd) (fun y => if y = encW F m (Matrix.vecMul a G) then 1 else 0) G0 := by sorry