Readout–subtract–uncompute:
ProvedOPI.tau_specWork with classical configurations of qubits; register values are read in binary, most significant bit first. The circuit uses:
- a control register of qubits with value ;
- an accumulator , with , one qubit , and ;
- a data register of qubits holding a residue mod , where ;
- a scratch register ( qubits), ancillas and a flag .
does three things. It sets the accumulator to (flip , then add into the accumulator times). It subtracts the value of modulo from . Then it runs the first part in reverse.
Statement. Assume the size conditions and , and that all listed wires are pairwise distinct. If the accumulator, , and are in , then
where adds modulo to values and fixes larger values. So a valid becomes , where is rounded to the nearest integer (ties rounded up) and reduced mod . Everything else, including and the accumulator, is unchanged.
In the gadget, is the phase-estimation outcome. Subtracting the estimate moves from to whenever the estimate is correct.
import Definitions.Def_TwoFoldOPI_CL_Part01
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
open QAlgorithms Matrix
variable {n : ℕ}
theorem OPI.tau_spec (p w : ℕ) (hp : 0 < p) (hpw : p ≤ 2 ^ w) (ctrlL top : List (Fin n)) (lh : Fin n)
(lrest Al Z as : List (Fin n)) (f : Fin n)
(htop : top.length = w + 1) (hct : ctrlL.length = lrest.length + 1)
(hAl : Al.length = w) (hZ : Z.length = w)
(hlen1 : 1 + (top.length + lrest.length + 1) ≤ as.length + 2)
(hlen2 : top.length + Al.length ≤ as.length + 2)
(hnd : (ctrlL ++ (top ++ lh :: lrest) ++ Al ++ Z ++ as ++ [f]).Nodup)
(z : Qubits n) (hac : ∀ a ∈ top ++ lh :: lrest, z a = false)
(hcl : ∀ a ∈ Z ++ as ++ [f], z a = false) :
revAct (tauList p w ctrlL top lh lrest Al Z as f) z =
writeReg Al (shiftL p w (p - rdv p (lrest.length + 1) (regVal ctrlL z)) (Al.map z)) z := by sorry