The Toffoli-ladder gate list is computable by a polynomial realizer
ProvedOPI.W6.IsPR.mcxN_prGates of reversible circuits are written first-order as pairs (tag, wires) of natural numbers: tag for X, for CNOT, for Toffoli. The function is the natural-number twin of the multi-controlled NOT ladder. On wire lists , and a target it returns , or for zero, one or two controls. For at least three controls and an ancilla it returns
and if there are at least three controls and no ancilla. The companion lemma mcx_N shows it equals the gate list of mcx with wires replaced by their indices.
Statement. The map
is polynomially realizable (): it is computed by a realizer in the stack-machine model whose running time and output size are bounded by a monotone polynomial in the size of the input.
This is one of the building blocks for showing that the generator of the quantum program (gate lists of all circuits, then serialisation) runs in polynomial time.
import Definitions.Def_TwoFoldOPI_CL_Part03
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.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI
variable {α β γ : Type} [Coding α] [Coding β] [Coding γ]
theorem OPI.W6.IsPR.mcxN_pr : IsPR (fun x : List ℕ × List ℕ × ℕ => mcxN x.1 x.2.1 x.2.2) := by sorry