Quantum and Circuits

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

Read this chapter with formatted equations

1 \section{Gate matrices and symbolic conventions}\label{g:app:gate-matrices}
2 \index{gate matrix}
3 \index{symplectic convention}
4 
5 
6 \subsection{Row-transvection convention}
7 Matrices act on column coordinate vectors, while row operations left multiply the current matrix.  A row transvection
8 \[
9 \tau_{t,s}(a)=I+aE_{t,s}
10 \]
11 performs
12 \[
13 R_t\leftarrow R_t+aR_s.
14 \]
15 In the binary CNOT interpretation, $s$ is the control and $t$ is the target.
16 
17 The canonical six-row target is
18 \[
19 C=
20 \begin{pmatrix}
21 1&0&0&0&0&0\\
22 1&1&0&0&0&0\\
23 0&0&1&0&0&0\\
24 0&1&1&1&0&0\\
25 1&1&1&0&1&0\\
26 1&1&1&0&0&1
27 \end{pmatrix}.
28 \]
29 One ambient word is
30 \[
31 \tau_{1,2}(1),
32 \tau_{3,1}(1),
33 \tau_{1,0}(1),
34 \tau_{4,1}(1),
35 \tau_{5,1}(1),
36 \tau_{1,2}(-1).
37 \]
38 A restricted word of length seven is
39 \[
40 \tau_{1,0}(1),
41 \tau_{2,1}(1),
42 \tau_{3,0}(-1),
43 \tau_{3,2}(1),
44 \tau_{4,2}(1),
45 \tau_{5,2}(1),
46 \tau_{2,1}(-1).
47 \]
48 
49 \subsection{Qudit SUM gate}
50 On computational basis labels in $\Z_d$,
51 \[
52 \SUM^{(a)}_{s\to t}
53 \ket{x_s,x_t}
54 =
55 \ket{x_s,x_t+a x_s\bmod d}.
56 \]
57 Its classical linear action is the transvection $I+aE_{t,s}$ over $\Z_d$.
58 
59 \subsection{Binary symplectic form}
60 Pauli exponents are ordered as
61 \[
62 (x_0,\ldots,x_{n-1},z_0,\ldots,z_{n-1}).
63 \]
64 The symplectic form is
65 \[
66 J=
67 \begin{pmatrix}
68 0&I_n\\
69 I_n&0
70 \end{pmatrix}
71 \]
72 over $\F_2$.  A matrix $M$ is symplectic when
73 \[
74 M^TJM=J.
75 \]
76 
77 \subsection{Clifford generator matrices}
78 For qubit $i$, the Hadamard swaps $x_i$ and $z_i$:
79 \[
80 H_i:e_i\leftrightarrow e_{n+i}.
81 \]
82 The phase gate has
83 \[
84 z_i\leftarrow z_i+x_i.
85 \]
86 For CNOT with control $c$ and target $t$,
87 \[
88 x_t\leftarrow x_t+x_c,
89 \qquad
90 z_c\leftarrow z_c+z_t.
91 \]
92 For CZ on $i,j$,
93 \[
94 z_i\leftarrow z_i+x_j,
95 \qquad
96 z_j\leftarrow z_j+x_i.
97 \]
98 SWAP exchanges both $x$ and $z$ coordinates of the two qubits.
99 
100 The parabolic subgroup used in the census is generated by $S_i$, $\CZ_{ij}$, and $\CX_{i\to j}$.  It stabilizes the $Z$ Lagrangian
101 \[
102 L_Z=\Span(e_n,\ldots,e_{2n-1}).
103 \]
104 
105 \subsection{Two-qubit Clifford witness}
106 The target symplectic matrix is
107 \[
108 M_2=
109 \begin{pmatrix}
110 0&1&0&0\\
111 1&0&0&0\\
112 1&1&0&1\\
113 1&1&1&0
114 \end{pmatrix}.
115 \]
116 A restricted path is
117 \[
118 \CX_{0\to1},\ S_1,\ \CX_{1\to0},\ \CX_{0\to1},
119 \]
120 with three charged entangling gates.  An ambient path is
121 \[
122 H_1,\ \CX_{1\to0},\ \CX_{0\to1},\ H_0,\ S_1,\ S_0,
123 \]
124 with two charged entangling gates when $H,S$ are free.
125 
126 \subsection{Three-qubit Clifford witness}
127 The target symplectic matrix is
128 \[
129 M_3=
130 \begin{pmatrix}
131 0&1&0&0&0&0\\
132 0&0&1&0&0&0\\
133 1&0&0&0&0&0\\
134 1&0&1&0&1&0\\
135 0&1&0&0&0&1\\
136 0&1&0&1&0&0
137 \end{pmatrix}.
138 \]
139 A restricted total-count path is
140 \[
141 \CX_{0\to2},\ \CZ_{1,2},\ \CX_{2\to0},\ \CX_{0\to2},
142 \ \CX_{0\to1},\ \CX_{1\to0},\ \CX_{0\to1},
143 \]
144 while an ambient path is
145 \[
146 H_1,\ \CX_{1\to2},\ \CX_{2\to1},\ \CX_{2\to0},\ \CX_{0\to2},\ H_0.
147 \]
148 
149 \subsection{Classical reversible gates}
150 For a bit string $x\in\F_2^n$:
151 \[
152 X_i:x_i\leftarrow x_i+1,
153 \]
154 \[
155 \CX_{c\to t}:x_t\leftarrow x_t+x_c,
156 \]
157 \[
158 \TOF_{a,b\to t}:x_t\leftarrow x_t+x_ax_b.
159 \]
160 All other coordinates are unchanged.  The first two generate $\operatorname{AGL}(n,2)$.  On three bits, all three generate the full permutation group $S_8$.  For $n\ge4$ without ancillas they are all even permutations, so the generated group is contained in $A_{2^n}$ and is not the full symmetric group.
161 
162 \subsection{Bosonic symplectic embedding}
163 For $A\in\GL(n,\R)$,
164 \[
165 \iota(A)=\diag(A,A^{-T})\in\Sp(2n,\R).
166 \]
167 This convention orders quadratures as $(q_1,\ldots,q_n,p_1,\ldots,p_n)$.
168 
169 \subsection{Pauli rotations}
170 For a Hermitian Pauli $P$,
171 \[
172 R_P(\theta)=e^{-i\theta P/2}.
173 \]
174 Clifford conjugation gives
175 \[
176 C R_P(\theta) C^\dagger=R_{CPC^\dagger}(\theta).
177 \]
178 The sign of $CPC^\dagger$ can be absorbed by changing $\theta$ to $-\theta$.
179 
180 \subsection{Tensor and direct-sum conventions}
181 For linear maps, $A\oplus B$ denotes a block-diagonal direct sum.  The Kronecker product $A\otimes B$ uses lexicographic ordering.  In quantum chapters, $U\otimes V$ denotes the physical tensor product on disjoint systems.  These operations have different dimension and cost normalizations and are not interchanged silently.
182 
183 \section{Finite census tables and witnesses}\label{g:app:census}
184 \index{census}
185 
186 
187 \subsection{Status key}
188 Every table in this appendix is generated from exact finite output in the accompanying JSON files.  ``Restricted size'' and ``ambient size'' refer to the enumerated quotient groups, not necessarily the full unitary groups including phases and translations.
189 
190 \subsection{Clifford census summary}
191 \begin{longtable}{@{}ccccrrrr@{}}
192 \toprule
193 Qubits & Metric & SWAP & Restricted size & Ambient size & $\operatorname{diam}_R$ & $\operatorname{diam}_A$ & Defects\\
194 \midrule
195 1 & total & no & 2 & 6 & 1 & 3 & 0\\
196 1 & entangling & no & 2 & 6 & 0 & 0 & 0\\
197 2 & total & no & 48 & 720 & 5 & 8 & 0\\
198 2 & entangling & no & 48 & 720 & 3 & 3 & 4\\
199 3 & total & no & 10,752 & 1,451,520 & 8 & 12 & 24\\
200 3 & total & yes & 10,752 & 1,451,520 & 7 & 11 & 0\\
201 3 & entangling & no & 10,752 & 1,451,520 & 6 & 6 & 1,624\\
202 \bottomrule
203 \end{longtable}
204 
205 \subsection{Clifford defect distributions}
206 \begin{longtable}{@{}p{.31\textwidth}p{.55\textwidth}r@{}}
207 \toprule
208 Model & Distance pair & Count\\
209 \midrule
210 Two qubits, entangling & $3\to2$ & 4\\
211 Three qubits, total & $7\to6$ & 6\\
212 Three qubits, total & $8\to7$ & 18\\
213 Three qubits, entangling & $3\to2$ & 24\\
214 Three qubits, entangling & $4\to3$ & 432\\
215 Three qubits, entangling & $5\to4$ & 1,056\\
216 Three qubits, entangling & $6\to4$ & 48\\
217 Three qubits, entangling & $6\to5$ & 64\\
218 \bottomrule
219 \end{longtable}
220 
221 \subsection{Affine-versus-Toffoli census}
222 \begin{longtable}{@{}cccccc@{}}
223 \toprule
224 Bits & Metric & Restricted size & Ambient size & Restricted diameter & Defects\\
225 \midrule
226 3 & total & 1,344 & 40,320 & 7 & 0\\
227 3 & entangling & 1,344 & 40,320 & 6 & 0\\
228 \bottomrule
229 \end{longtable}
230 
231 \subsection{Linear atom modular checks}
232 \begin{longtable}{@{}cccc@{}}
233 \toprule
234 Modulus & Restricted word length & Ambient word length & Both match target\\
235 \midrule
236 2 & 7 & 6 & yes\\
237 3 & 7 & 6 & yes\\
238 5 & 7 & 6 & yes\\
239 8 & 7 & 6 & yes\\
240 \bottomrule
241 \end{longtable}
242 These checks confirm the symbolic words.  Exact optimality over general rings is proved separately in the core chapter.
243 
244 \subsection{Core binary six-dimensional census}
245 For $U_6(\F_2)$ there are $2^{15}=32{,}768$ targets.  The complete comparison is:
246 \begin{longtable}{@{}rrr@{}}
247 \toprule
248 Restricted distance & Ambient distance & Number of targets\\
249 \midrule
250 0 & 0 & 1\\
251 1 & 1 & 15\\
252 2 & 2 & 125\\
253 3 & 3 & 720\\
254 4 & 4 & 2,914\\
255 5 & 5 & 7,851\\
256 6 & 6 & 12,656\\
257 7 & 6 & 20\\
258 7 & 7 & 7,926\\
259 8 & 8 & 540\\
260 \bottomrule
261 \end{longtable}
262 The twenty strict defects are exactly the analytic three-cross, one-phase motifs.
263 
264 \subsection{Endpoint Green coefficients for the canonical atom}
265 Restricted word counts for degrees zero through ten are
266 \[
267 0,0,0,0,0,0,0,543,25080,510703,10824940.
268 \]
269 Ambient word counts for degrees zero through eight are
270 \[
271 0,0,0,0,0,0,2,776,39454.
272 \]
273 Thus first arrival occurs at seven and six, respectively.
274 
275 \subsection{Machine-readable locations}
276 The release contains:
277 \begin{itemize}
278 \item \texttt{results/atlas\_results.json},
279 \item \texttt{results/clifford\_n3\_total.json},
280 \item \texttt{results/clifford\_n3\_total\_swap.json},
281 \item \texttt{results/clifford\_n3\_entangling.json},
282 \item the complete unitriangular supplement under \texttt{core\_extract/supplement/}.
283 \end{itemize}
284 The JSON schema records model, metric, group sizes, diameters, defect distributions, and selected witnesses.
285 
286 \section{Python and C++ interface}\label{g:app:api}
287 \index{Python API}
288 
289 
290 \subsection{Package overview}
291 The Python package \texttt{catalytic\_gate\_atlas} exports exact primitives for the linear, Clifford, and classical reversible experiments.  It requires Python 3.10 or later and has no runtime dependencies.
292 
293 \subsection{Installation}
294 \begin{lstlisting}[style=pythonstyle]
295 cd code
296 python -m venv .venv
297 . .venv/bin/activate
298 python -m pip install -e . --no-build-isolation
299 python -m pytest tests
300 \end{lstlisting}
301 On Windows PowerShell, activation is
302 \begin{verbatim}
303 .\.venv\Scripts\Activate.ps1
304 \end{verbatim}
305 
306 \subsection{Top-level API}
307 \begin{lstlisting}[style=pythonstyle]
308 from catalytic_gate_atlas import (
309     RowGate,
310     canonical_ambient_word,
311     canonical_restricted_word,
312     canonical_six_target,
313     snapshot_target,
314     verify_canonical_atom,
315     exact_clifford_census,
316     exact_affine_toffoli_census,
317     gate_word_to_openqasm,
318 )
319 \end{lstlisting}
320 
321 \subsection{Linear atom}
322 \begin{lstlisting}[style=pythonstyle]
323 from catalytic_gate_atlas import verify_canonical_atom
324 
325 for modulus in (2, 3, 5, 8):
326     print(verify_canonical_atom(modulus))
327 \end{lstlisting}
328 The function evaluates the displayed restricted and ambient words over $\Z/m\Z$ and compares both endpoints with the canonical target.
329 
330 \subsection{Snapshot targets}
331 \begin{lstlisting}[style=pythonstyle]
332 from catalytic_gate_atlas import snapshot_target
333 
334 # u=4 source updates; snapshots at phases 0, 2, and 4.
335 A = snapshot_target(4, phases=(0, 2, 4), modulus=2)
336 for row in A:
337     print(row)
338 \end{lstlisting}
339 The generator checks phase order and produces the exact lower-unitriangular target matrix used in the symbolic family.
340 
341 \subsection{Clifford census}
342 \begin{lstlisting}[style=pythonstyle]
343 from catalytic_gate_atlas import exact_clifford_census
344 
345 print(exact_clifford_census(2, entangling_cost=True))
346 print(exact_clifford_census(2, entangling_cost=False))
347 \end{lstlisting}
348 The optional three-qubit Python census is slower.  The release includes an optimized C++ program for the full $1{,}451{,}520$-state group.
349 
350 \subsection{Affine-versus-Toffoli census}
351 \begin{lstlisting}[style=pythonstyle]
352 from catalytic_gate_atlas import exact_affine_toffoli_census
353 
354 print(exact_affine_toffoli_census(3, entangling_cost=False))
355 print(exact_affine_toffoli_census(3, entangling_cost=True))
356 \end{lstlisting}
357 The complete ambient enumeration is intentionally limited to three bits.
358 
359 \subsection{OpenQASM witness export}
360 \begin{lstlisting}[style=pythonstyle]
361 from catalytic_gate_atlas import gate_word_to_openqasm
362 
363 word = ["H1", "CX12", "CX21", "CX20", "CX02", "H0"]
364 print(gate_word_to_openqasm(word, 3, title="ambient witness"))
365 \end{lstlisting}
366 The exporter supports the named $H$, $S$, $X$, CX, CZ, and SWAP gates used by the finite atlas and writes OpenQASM~3.  The supplied files in \texttt{examples/} encode the two- and three-qubit restricted and ambient witness words.  The Clifford census is performed modulo global phase and Pauli translations, so equality of an exported pair refers to its binary symplectic action unless the ignored Pauli and phase data are separately reconstructed.
367 
368 \begin{verbatim}
369 PYTHONPATH=. python scripts/export_qasm_examples.py
370 \end{verbatim}
371 
372 \subsection{Search primitives}
373 \begin{lstlisting}[style=pythonstyle]
374 from catalytic_gate_atlas.search import (
375     NamedGenerator,
376     breadth_first_distances,
377     breadth_first_with_parents,
378     zero_one_distances,
379     zero_one_with_parents,
380     dijkstra_distances,
381     reconstruct_path,
382     defect_distribution,
383 )
384 \end{lstlisting}
385 Every state must be immutable and hashable.  The caller supplies a multiplication function with the convention
386 \[
387 \texttt{multiply(generator, state)}.
388 \]
389 
390 \subsection{Binary matrix primitives}
391 The module \texttt{algebra.py} provides:
392 \begin{itemize}
393 \item \texttt{gf2\_identity},
394 \item \texttt{gf2\_mul},
395 \item \texttt{gf2\_transpose},
396 \item \texttt{gf2\_rank},
397 \item dense modular matrix multiplication,
398 \item exact permutation composition and inversion.
399 \end{itemize}
400 
401 \subsection{C++ verifier}
402 \begin{verbatim}
403 g++ -O3 -std=c++20 scripts/clifford_census.cpp -o scripts/clifford_census
404 ./scripts/clifford_census --n 3 --metric total
405 ./scripts/clifford_census --n 3 --metric total --swap
406 ./scripts/clifford_census --n 3 --metric entangling
407 \end{verbatim}
408 The executable can write JSON using the \texttt{--output} option.
409 
410 \subsection{Figure generation}
411 \begin{verbatim}
412 python scripts/make_monograph_figures.py
413 \end{verbatim}
414 All new monograph figures are generated by Matplotlib without external data.  The established unitriangular figures are preserved from the Paper I source archive.
415 
416 \subsection{Adding a new finite gate model}
417 A new module should implement:
418 \begin{enumerate}
419 \item a canonical immutable state representation;
420 \item exact multiplication;
421 \item named restricted and ambient generators with nonnegative costs;
422 \item an exact target-membership test;
423 \item a census function returning the standard JSON fields;
424 \item smoke tests for group size and witness evaluation.
425 \end{enumerate}
426 
427 \subsection{Standard result schema}
428 A census result should include:
429 \begin{lstlisting}[style=pythonstyle]
430 {
431     "model": "descriptive-name",
432     "size": n,
433     "metric": "total-or-weighted",
434     "restricted_group_size": ...,
435     "ambient_group_size": ...,
436     "restricted_diameter": ...,
437     "ambient_diameter": ...,
438     "defect_count": ...,
439     "defect_distribution": {...},
440     "maximum_defect": ...,
441     "witness": {...},
442     "status": "complete finite enumeration"
443 }
444 \end{lstlisting}
445 A partial search must not use the status string ``complete finite enumeration.''
446 
447 \subsection{Error handling}
448 Several entry points validate dimensions, distinct controls, matrix shape, and cost restrictions.  The complete affine census rejects widths above three, and the C++ Clifford executable accepts only one through three qubits.  Low-level helpers assume well-formed indices and states, so callers should not treat every helper as a fully validated public parser.  The search code does not silently truncate its reachable state space.
449 
450 \section{Conjecture and obligation ledger}\label{g:app:ledger}
451 \index{conjecture ledger}
452 
453 
454 \subsection{How to read the ledger}
455 The ledger separates established statements, complete computations, partial checks, and open conjectures.  ``Open'' means no proof is claimed in this monograph.  ``Computed'' refers only to the stated finite model.
456 
457 \begin{longtable}{@{}>{\raggedright\arraybackslash}p{.05\textwidth}>{\raggedright\arraybackslash}p{.38\textwidth}>{\raggedright\arraybackslash}p{.16\textwidth}>{\raggedright\arraybackslash}p{.31\textwidth}@{}}
458 \toprule
459 ID & Statement & Status & Decisive next step\\
460 \midrule
461 L1 & Canonical six-row transvection target has lengths $7$ and $6$ over nonzero commutative rings. & Proved & Independent external proof audit.\\
462 L2 & Dimensions below six are rigid over every coefficient field or ring. & Open & Symbolic bounded-skeleton elimination for $n\le5$.\\
463 L3 & Maximum unitriangular defect is $\Theta(n\log n)$. & Open & Matching upper bound or larger interacting-catalyst family.\\
464 L4 & Multiplicative unitriangular distortion is bounded by $3/2$. & Open & Normal form beyond one clean carrier.\\
465 L5 & Canonical atom has lower border length seven. & Open & Eliminate six-gate word-map components algebraically.\\
466 L6 & A one-copy rigid target exhibits tensor activation. & Open & Exact tensor-power search or asymptotic construction.\\
467 C1 & Two-qubit parabolic Clifford entangling model has four $3\to2$ defects in one free-phase orbit. & Analytic costs and orbit; finite classification & Complete: Theorem~\ref{g:thm:clifford-two-analytic} plus the exhaustive census.\\
468 C2 & Three-qubit swap-free total Clifford model has twenty-four defects. & Computed & Analytic motif classification.\\
469 C3 & Unit-cost SWAP eliminates all three-qubit total defects. & Computed & Determine whether rigidity persists for larger $n$.\\
470 C4 & Parabolic-versus-full Clifford defect is unbounded. & Open & Construct and certify an amplifiable atom.\\
471 N1 & Three-bit affine targets receive no Toffoli-assisted saving in the two tested metrics. & Computed & Independent implementation and formal certificate.\\
472 N2 & Some finite affine target is shortened by temporary nonlinearity. & Open & Complete four-bit normal-form search.\\
473 P1 & A diagonal target has a Pareto improvement from non-diagonal Clifford escape. & Open & Exact small-width multiobjective atlas.\\
474 P2 & Phase-polynomial $T$-count displays tensor activation. & Open & Joint synthesis of repeated phase targets.\\
475 G1 & A number-conserving Gaussian target is shortened by Bogoliubov escape. & Open & Exact low-mode orthogonal/symplectic search.\\
476 G2 & A nearest-neighbor matchgate target is shortened by restored mode permutation. & Open & Architecture-weighted routing theorem.\\
477 S1 & A constant-size symmetry-breaking excursion can save unbounded cost. & Open & Explicit sector-coupled family and lower bound.\\
478 A1 & A fixed number of dirty ancillas can yield unbounded saving in a non-linear quantum gate model. & Open & Family with all-input restoration proof.\\
479 R1 & A nonsimply laced root system has catalytic ratio exceeding $3/2$. & Open & Low-rank Chevalley word search and restricted lower bound.\\
480 H1 & Typed Green kernels yield non-enumerative distance lower bounds. & Open & Representation-theoretic coefficient inequalities.\\
481 H2 & Finite-degree transition moments suffice to distinguish all Latin squares of fixed order. & Open & Moment hierarchy and counterexample search.\\
482 Q1 & The order-six quantum-Latin product realization is empty while the entangled realization is nonempty. & Established externally & See Ball--Simoens and cited entangled constructions.\\
483 \bottomrule
484 \end{longtable}
485 
486 \subsection{Negative results worth preserving}
487 The following failed or negative conclusions are part of the research record.
488 \begin{itemize}
489 \item Comparisons involving the separate hard Latin line-spread computation remain pending until its input representatives and verifier are supplied.
490 \item Abstract row-column-symbol eigenvalues do not distinguish order-six Latin main classes.
491 \item No classification of the two hard classes by a projective spread operator is certified by the present archive.
492 \item Three-bit Toffoli assistance does not shorten affine targets in the tested costs.
493 \item Adding unit-cost SWAP removes the three-qubit total-count Clifford defects in the declared quotient model.
494 \end{itemize}
495 These results prevent overgeneralization and sharpen the next search spaces.
496 
497 \subsection{Publication obligations}
498 Before any skeleton chapter is separated into a theorem paper, complete:
499 \begin{enumerate}
500 \item targeted literature review,
501 \item independent verification of all exact computations,
502 \item a formal statement of equivalence conventions,
503 \item proof or certificate for every lower bound,
504 \item archive of source, expected outputs, and manifests,
505 \item explicit discussion of what the model omits.
506 \end{enumerate}
507 

Back to source controls

Back to Quantum and Circuits