§7, unnumbered: constructed one-ancilla circuit size
OpenQAlgorithms.Papers.Independent.Intakethird100.P85.circuitGate_boundThere are absolute positive constants such that the following holds. Let and let be a unitary -qubit operator over with least complex-matrix denominator exponent . The column-elimination trace and its elementary compilation return a circuit using one trailing clean helper, with
Each compiled one-/two-level operation contributes an actual segment of at most elementary gates, and the trace concatenates those segments. The count is over . This is an output-size bound for the constructed exact circuit, not an arithmetic runtime or optimality assertion.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P85
noncomputable section
namespace QAlgorithms.Papers.Independent.Intakethird100.P85
open scoped Classical BigOperators
open QAlgorithms
open QAlgorithms.Papers.Independent.Gap48.P10
(InZomega InDomega Residue bits residue residueMultiply Reducible)
open QAlgorithms.Papers.Independent.Support21.P13
(synthesisRing integralRing coordinateValue HTLetter htWordMatrix EntriesInRing cliffordTLibrary)
local notation "omega" => QAlgorithms.gateT true true
local notation "sqrtTwo" => ((Real.sqrt 2 : ℝ) : ℂ)
/-- Section 7, PDF p.7: actual one-helper elementary output has O(3^(2^n) n k) gates.
The matrix-reduction and per-operation compilation traces tie the count to the output. -/
theorem circuitGate_bound :
∃ B C : ℕ, 0 < B ∧ 0 < C ∧
∀ (n : ℕ) (U : Matrix (Qubits n) (Qubits n) ℂ) (k : ℕ),
0 < n → 0 < k → U ∈ Matrix.unitaryGroup (Qubits n) ℂ → EntriesInRing U →
LeastMatrixExponent U k →
∃ w : List (LevelOp (2 ^ n)), ∃ c : Circuit gateSet (n + 1),
MatrixTrace (indexedMatrix U) k w ∧
CompilationTrace B n (inverseWord w) c ∧
ImplementsWithCleanAncillas c.unitary U ∧
c.size ≤ C * 3 ^ (2 ^ n) * n * k := by sorry
end QAlgorithms.Papers.Independent.Intakethird100.P85
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exist positive natural numbers such that, for every pair of positive natural numbers and every unitary complex matrix indexed by the -bit strings , the following holds. Set , let , and let be the smallest subring of containing and . Assume every entry of belongs to , and assume is the least natural number for which every entry of belongs to . Then there exist a finite list of the elementary operations described below on basis indices and a circuit on qubits satisfying the specified matrix and compilation traces, such that, for every vector ,
Here is the product of the circuit's embedded gate matrices in reverse list order, so the first listed gate acts first. The allowed circuit gates are , , , CNOT sending to , and the zero-qubit scalar gate ; each gate is placed on an injectively chosen ordered list of wires and acts identically on the other wires. An elementary operation on basis indices is , or on an ordered pair of distinct indices , acting identically on all other indices, or a phase operation multiplying just index by , where ; write for the reverse-order matrix product of a list of these operations, with empty product the identity. The required matrix trace starts with reindexed by the big-endian binary value , and is the following recursively generated relation between a matrix , a natural exponent , and a list of elementary operations: in dimension zero the empty list is permitted for every ; in dimension , the list must be followed by a list whose indices have all been increased by one, where has a column trace for the first column , target index , and exponent , and has a matrix trace for the submatrix of on indices , with exponent . A column trace with target index has the following constructors: at exponent zero its vector is exactly at one index and zero elsewhere, for some , and its list swaps using if they differ and then applies the phase operation at exactly times; at exponent , its list is followed by , where has a pass trace at exponent for the original vector , and has a column trace at exponent for . To specify a pass trace, define the residue of by choosing an integer expansion and reducing its four coefficients modulo ; outside , the residue is the zero vector. For residue vectors , define
and call reducible when for some residue vector . Put . A pass trace for at exponent may be empty if every is reducible; otherwise its next constructor chooses distinct indices with not reducible and , applies the two-level lift of the row word described next to , and continues with a pass trace at the same exponent for the resulting whole vector. The row word is the first word, in the ordered candidate list consisting of the empty word, then the words written chronologically as copies of followed by for , then all ordered concatenations of two such words, whose reverse-order product sends the pair to a vector all of whose entries become elements of after multiplication by ; if no candidate qualifies, it is the empty word, and here is natural subtraction, equal to zero when . Finally, the required compilation trace is for the inverse list of , obtained by reversing , leaving each unchanged, and replacing each or phase operation by seven copies of itself: it recursively partitions into one segment per operation, each segment having at most gates and implementing that operation, after binary reindexing, on every -qubit vector with the extra qubit initialized and returned to zero; the empty operation list compiles to the empty circuit. The constants are uniform over all the quantified data; and are excluded by the hypotheses.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.