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 \chapter{Foundations of packet simulation}
2 \section{The symmetry-collapse question}
3 \label{s:ch:question}
4 \index{symmetry collapse}
5 
6 \subsection{The computational mismatch}
7 An $n$-qubit pure state has $2^n$ complex amplitudes in the computational basis. That description is universal but frequently redundant. A number-preserving circuit started with two excitations never visits basis strings of weight zero, one, three, or more. A permutation-symmetric circuit started in a symmetric state never distinguishes two strings that differ only by a relabeling of qubits. A quantum walk on a highly symmetric graph may evolve entirely in the span of a polynomial number of orbit states. In each case the full Hilbert space is a valid container but not the intrinsic state space of the computation.
8 
9 The question is therefore not whether a quantum circuit acts on an exponential ambient space. It is whether the reachable part of that space, together with the gate action and measurement, has a polynomial classical representation.
10 
11 \begin{definition}[Exact symmetry collapse]
12 A uniform quantum circuit family exhibits an exact symmetry collapse when its acceptance probability can be computed by an exact classical simulation on an invariant representation whose description and update costs are polynomial in the input length.
13 \end{definition}
14 
15 \begin{definition}[Approximate symmetry collapse]
16 A uniform circuit family exhibits an approximate symmetry collapse to error $\varepsilon(n)$ when a polynomial-size classical representation reproduces its acceptance probability to additive error $\varepsilon(n)$, with the error below the promise gap required by the decision problem.
17 \end{definition}
18 
19 \subsection{Four conclusions that must not be conflated}
20 The phrase ``symmetry reduction'' is used for several logically different achievements.
21 
22 \begin{enumerate}
23 \item \textbf{Structural reduction.} A projector, quotient, or representation-theoretic coordinate change removes redundant coordinates.
24 \item \textbf{Practical acceleration.} A concrete implementation uses less time or memory on tested instances.
25 \item \textbf{Polynomial classical simulation.} A uniform family admits a deterministic polynomial-time classical algorithm.
26 \item \textbf{Universal complexity collapse.} Every polynomial-size quantum circuit admits such a representation.
27 \end{enumerate}
28 
29 The first three occur in this monograph for declared subclasses. The fourth would imply $BQP\subseteq P$ and is not established. A benchmark can support the second conclusion without proving the third. A small invariant label set can support the first conclusion while leaving exponentially large internal blocks and therefore failing to prove the third.
30 
31 \subsection{The four audit quantities}
32 For a proposed reduction, define the schematic complexity record
33 \[
34 \mathfrak C_n=
35 \bigl(
36 N_{\mathrm{packets}},
37 D_{\mathrm{internal}},
38 S_{\mathrm{transfer}},
39 L_{\mathrm{leakage}}
40 \bigr).
41 \]
42 Here:
43 
44 \begin{itemize}
45 \item $N_{\mathrm{packets}}$ is the number of reachable symmetry labels.
46 \item $D_{\mathrm{internal}}$ is the packet dimension or the size of a compressed internal representation.
47 \item $S_{\mathrm{transfer}}$ records the sparsity and cost of gate-induced transitions.
48 \item $L_{\mathrm{leakage}}$ measures departure from the proposed representation.
49 \end{itemize}
50 
51 A complete claim must also state the cost of discovering this structure from the input. A decomposition that is small but exponentially hard to find does not yield a polynomial algorithm.
52 
53 \begin{figure}[H]
54 \centering
55 \includegraphics[width=.91\textwidth]{assets/s_collapse_decision_tree.pdf}
56 \caption{A disciplined decision tree for proposed symmetry-collapse claims.}
57 \end{figure}
58 
59 \subsection{Why symmetry is only the beginning}
60 Suppose a group $G$ acts on the Hilbert space and the circuit commutes with this action. Representation theory decomposes the space into isotypic pieces. This gives a canonical block structure, but three questions remain.
61 
62 First, how many pieces are reachable from the input? Second, how large is each piece or how compactly can its states be encoded? Third, can each gate and measurement be applied in those coordinates without reconstructing the full state? The monograph repeatedly returns to this three-stage distinction:
63 \[
64 \text{symmetry label}
65 \longrightarrow
66 \text{reachable representation}
67 \longrightarrow
68 \text{efficient classical algorithm}.
69 \]
70 
71 \begin{principle}[No free collapse]
72 Block diagonality is a structural statement. Polynomial-time classical simulation requires an efficient basis or encoding, efficient updates, and efficient output evaluation in addition to the block decomposition.
73 \end{principle}
74 
75 \section{Projectors and quantum packets}
76 \label{s:ch:projectors}
77 \index{projector}
78 \index{packet decomposition}
79 
80 \subsection{Orthogonal packet decompositions}
81 Let $\Hh$ be a finite-dimensional Hilbert space and let $\{P_\alpha\}_{\alpha\in A}$ be orthogonal projectors satisfying
82 \[
83 P_\alpha P_\beta=\delta_{\alpha\beta}P_\alpha,
84 \qquad
85 \sum_{\alpha\in A}P_\alpha=I.
86 \]
87 Every state and operator decompose as
88 \[
89 \ket\psi=\sum_\alpha P_\alpha\ket\psi,
90 \qquad
91 X=\sum_{\alpha,\beta}P_\alpha X P_\beta.
92 \]
93 The diagonal blocks act within packets. The off-diagonal blocks transfer amplitude or coherence between packets.
94 
95 Define the packet-transfer graph of an operator $X$ by placing an edge $\beta\to\alpha$ whenever
96 \[
97 P_\alpha X P_\beta\neq0.
98 \]
99 An exactly symmetry-preserving operator has only diagonal edges. A sparse transfer graph may still permit efficient simulation if the active packets and internal states remain compact.
100 
101 \subsection{Conserved observables}
102 Let
103 \[
104 Q=\sum_k q_kP_k
105 \]
106 be a self-adjoint observable with spectral projectors $P_k$.
107 
108 \begin{theorem}[Invariant quantum packets]
109 \label{s:thm:invariant-packets}
110 If a unitary $U$ satisfies $[U,Q]=0$, then
111 \[
112 P_iUP_j=0\qquad(i\neq j),
113 \]
114 and
115 \[
116 U=\bigoplus_i U_i,
117 \qquad
118 U_i=P_iUP_i\big|_{P_i\Hh}.
119 \]
120 If $P_k\ket\psi=\ket\psi$, then $P_kU\ket\psi=U\ket\psi$.
121 \end{theorem}
122 
123 \begin{proof}
124 Since $U$ commutes with $Q$, it commutes with every spectral projector obtained from the functional calculus of $Q$. Thus
125 \[
126 P_iUP_j=UP_iP_j=0
127 \]
128 for $i\neq j$. Summing the diagonal blocks gives the direct-sum form. The final statement follows from
129 \[
130 P_kU\ket\psi=UP_k\ket\psi=U\ket\psi.
131 \]
132 \end{proof}
133 
134 \subsection{Residue and character packets}
135 Suppose $Q$ has integer spectrum. For a modulus $M$, define
136 \[
137 B_r^{(M)}=
138 \sum_{k\equiv r\pmod M}P_k.
139 \]
140 Let
141 \[
142 V_M=\exp\left(\frac{2\pi i}{M}Q\right),
143 \qquad
144 \omega_M=e^{2\pi i/M}.
145 \]
146 Then
147 \begin{equation}
148 B_r^{(M)}
149 =
150 \frac1M\sum_{\ell=0}^{M-1}
151 \omega_M^{-r\ell}V_M^\ell.
152 \label{s:eq:residue-projector}
153 \end{equation}
154 On a $Q$-eigenvector, the right side is the roots-of-unity filter. The same finite-character formula selects residue classes in signal polyphase analysis and charge sectors in quantum theory.
155 
156 \subsection{Finite-group projectors}
157 Let a finite group $G$ act unitarily by $U_g$. For an irreducible character $\chi$ of degree $d_\chi$, the central isotypic projector is
158 \begin{equation}
159 P_\chi
160 =
161 \frac{d_\chi}{|G|}
162 \sum_{g\in G}
163 \overline{\chi(g)}U_g.
164 \label{s:eq:character-projector}
165 \end{equation}
166 Character orthogonality gives
167 \[
168 P_\chi P_\psi=\delta_{\chi\psi}P_\chi,
169 \qquad
170 \sum_\chi P_\chi=I
171 \]
172 on the represented space. If an operator $A$ commutes with every $U_g$, then
173 \[
174 P_\chi A P_\psi=0
175 \qquad(\chi\neq\psi).
176 \]
177 
178 This framework includes momentum, parity, total spin, point-group symmetry, permutation symmetry, and stabilizer syndrome labels. The isotypic projector identifies a symmetry type. It does not necessarily resolve the multiplicity space within that type.
179 
180 \subsection{Nested refinements}
181 If one conserved label is too coarse, intersect commuting projector families. For mutually commuting observables $Q_1,\ldots,Q_s$, a joint packet has the form
182 \[
183 P_{\bm\alpha}
184 =
185 P^{(1)}_{\alpha_1}\cdots P^{(s)}_{\alpha_s}.
186 \]
187 The dimension can decrease dramatically, but each extra label must be efficiently computable and preserved. A refinement that requires exponential preprocessing merely relocates the complexity.
188 
189 \begin{remark}
190 A packet decomposition is basis independent as an orthogonal direct sum, although a practical simulator must choose a concrete basis or compressed coordinate system within each active packet.
191 \end{remark}
192 
193 \section{Uniform circuits and the classical cost model}
194 \label{s:ch:complexity-model}
195 \index{uniform circuit}
196 \index{classical simulation}
197 
198 \subsection{Circuit families}
199 A quantum decision procedure is a polynomial-time uniform family of circuits $\{C_x\}$, where the input string $x$ determines a circuit on $n=n(|x|)$ qubits with at most $\poly(|x|)$ gates. Let
200 \[
201 C_x=G_m\cdots G_1.
202 \]
203 A classical simulation theorem must describe an algorithm receiving the same succinct description of $x$ and the circuit. It is not enough to assume that an exponentially large matrix or a complete orbit list has already been supplied.
204 
205 \subsection{The packet access model}
206 For each input length, suppose there is a packet projector $P_n$ and a basis
207 \[
208 \B_n=
209 \{\ket{b_1},\ldots,\ket{b_{D_n}}\}
210 \]
211 of $P_n\Hh_n$. The simulation interface has four routines.
212 
213 \begin{enumerate}
214 \item \textbf{Discovery and indexing.} Produce or index $\B_n$ in polynomial time.
215 \item \textbf{Initialization.} Express the initial state in this basis.
216 \item \textbf{Gate update.} Apply each restricted gate $P_nG_jP_n$ to the packet coordinates in polynomial time.
217 \item \textbf{Measurement.} Compute the final acceptance probability to the needed precision.
218 \end{enumerate}
219 
220 The basis need not be listed explicitly if there is a compact data structure supporting these operations. Stabilizer tableaux and covariance matrices are examples of representations that encode exponentially many computational-basis amplitudes without storing them individually.
221 
222 \subsection{Precision and promise gaps}
223 A BQP decision problem has an inverse-constant promise gap after standard amplification. A deterministic classical simulator need only estimate the acceptance probability to an additive error smaller than this gap. If the gate entries are algebraic or otherwise polynomial-time computable, ordinary numerical analysis gives polynomial bit complexity for polynomially many updates, provided condition numbers and error amplification are controlled.
224 
225 \subsection{State-vector cost inside a packet}
226 If the simulator stores $D$ amplitudes and a local gate can be applied in $O(nD)$ arithmetic operations, a depth-$d$ packet simulation has schematic cost
227 \[
228 C_{\mathrm{packet}}=O(dnD)+C_{\mathrm{compile}}.
229 \]
230 The corresponding full state-vector path is
231 \[
232 C_{\mathrm{full}}=O(dn2^n).
233 \]
234 These formulas are intentionally schematic. Cache behavior, indexing, vectorization, and basis compilation determine actual runtime. The asymptotic distinction is exact when $D$ is polynomial and $2^n$ is exponential.
235 
236 \subsection{Reuse and amortization}
237 Packet compilation can be expensive. Repeated parameter sweeps, time stepping, variational optimization, and repeated likelihood evaluation benefit from cached basis maps and gate plans. A one-shot simulation can be slower even when each subsequent packet update is much cheaper. The benchmark chapter preserves both one-shot and repeated-application measurements for this reason.
238 
239 \begin{scopebox}
240 A polynomial-dimensional invariant sector does not guarantee a practical speedup at small $n$. It guarantees that the state-vector representation within that sector has polynomial asymptotic size under the stated access assumptions.
241 \end{scopebox}
242 
243 \section{Exact packet simulation and polynomial collapse}
244 \label{s:ch:exact-simulation}
245 
246 \subsection{Gatewise invariance}
247 Let $P$ be an orthogonal projector and suppose the initial state obeys $P\ket{\psi_0}=\ket{\psi_0}$. If every gate satisfies
248 \begin{equation}
249 G_jP=PG_jP,
250 \label{s:eq:gatewise-invariance}
251 \end{equation}
252 then $G_j$ maps $P\Hh$ into itself. For a general linear map, this equation asserts only invariance of the selected subspace. For the finite-dimensional unitary gates considered here, invariance also implies invariance of the orthogonal complement, so it is equivalent to commutation with $P$.
253 
254 \begin{theorem}[Invariant-basis simulation]
255 \label{s:thm:invariant-basis}
256 Let $U=G_m\cdots G_1$ and assume \cref{s:eq:gatewise-invariance} for every gate. If $P\ket{\psi_0}=\ket{\psi_0}$, then
257 \[
258 U\ket{\psi_0}
259 =
260 (PG_mP)\cdots(PG_1P)\ket{\psi_0}.
261 \]
262 In any basis of $P\Hh$, the restricted circuit gives exactly the same amplitudes after embedding.
263 \end{theorem}
264 
265 \begin{proof}
266 Inductively, if $P\ket{\psi_{j-1}}=\ket{\psi_{j-1}}$, then
267 \[
268 G_j\ket{\psi_{j-1}}
269 =
270 G_jP\ket{\psi_{j-1}}
271 =
272 PG_jP\ket{\psi_{j-1}},
273 \]
274 so the next state remains in $P\Hh$. Iterating proves the identity.
275 \end{proof}
276 
277 \subsection{Polynomial packet-simulation theorem}
278 \begin{theorem}[Polynomial packet-simulation theorem]
279 \label{s:thm:poly-packet}
280 Let $\{C_x\}$ be a polynomial-time uniform family of quantum circuits. Suppose there is an efficiently computable packet representation such that:
281 
282 \begin{enumerate}
283 \item the initial state lies in the represented packet and its coordinates are computable in polynomial time;
284 \item every gate preserves the representation;
285 \item the representation size is at most $\poly(|x|)$;
286 \item each gate update is computable to polynomial precision in polynomial time;
287 \item the final acceptance probability is computable from the representation in polynomial time.
288 \end{enumerate}
289 
290 Then the language decided by the circuit family belongs to $P$.
291 \end{theorem}
292 
293 \begin{proof}
294 The simulator stores a polynomial-size classical description of the evolving state. It performs polynomially many polynomial-time gate updates and evaluates the final measurement to inverse-polynomial precision. Choosing an error smaller than the amplified promise gap yields a deterministic polynomial-time decision algorithm.
295 \end{proof}
296 
297 \begin{provedbox}
298 The theorem is a genuine quantum-to-classical complexity collapse for the declared subclass. It does not assume that a full $2^n$ state vector is ever constructed.
299 \end{provedbox}
300 
301 \subsection{Dimension-only corollary}
302 A convenient special case uses an explicit basis of a packet of dimension $D_n$.
303 
304 \begin{corollary}[Polynomial-dimensional invariant packet]
305 If $D_n\le\poly(n)$, the packet basis is efficiently indexed, every gate has a polynomial-time sparse or structured action in that basis, and the measurement is efficiently evaluable, then the circuit family is classically polynomial-time simulable.
306 \end{corollary}
307 
308 \subsection{A broader compressed representation}
309 The state description need not be a vector of packet amplitudes. Let $\mathcal R_n$ be a polynomial-size classical representation class with an embedding into the packet Hilbert space. If initialization, gate updates, and measurement stay within $\mathcal R_n$ and are efficient, the same proof applies. This observation will later combine packet labels with stabilizer, Gaussian, or tensor-network coordinates.
310 
311 \begin{figure}[H]
312 \centering
313 \includegraphics[width=.92\textwidth]{assets/s_compiler_pipeline.pdf}
314 \caption{A complete collapse certificate includes discovery, update, leakage, measurement, and complexity information.}
315 \end{figure}
316 
317 \section{Approximate symmetry and leakage certificates}
318 \label{s:ch:approximate-symmetry}
319 \index{leakage}
320 
321 \subsection{Hamiltonian leakage}
322 Exact conservation is not the only useful regime. Let $P$ be an orthogonal projector and let
323 \[
324 U(t)=e^{-itH}
325 \]
326 for a bounded self-adjoint Hamiltonian $H$. The leakage operator from the packet is
327 \[
328 L_P(t)=(I-P)e^{-itH}P.
329 \]
330 
331 \begin{theorem}[Commutator leakage bound]
332 \label{s:thm:commutator-leakage}
333 For every real $t$,
334 \[
335 \|(I-P)e^{-itH}P\|
336 \le
337 |t|\,\|[H,P]\|.
338 \]
339 \end{theorem}
340 
341 \begin{proof}
342 Define
343 \[
344 F(s)=e^{-i(t-s)H}Pe^{-isH}P.
345 \]
346 Then $F(0)=e^{-itH}P$ and $F(t)=Pe^{-itH}P$. Differentiation gives
347 \[
348 F'(s)=ie^{-i(t-s)H}[H,P]e^{-isH}P.
349 \]
350 Therefore
351 \[
352 (I-P)e^{-itH}P
353 =-(I-P)\int_0^tF'(s)\,ds.
354 \]
355 The unitary factors and projectors have norm at most one, so the integral is bounded by $|t|\|[H,P]\|$.
356 \end{proof}
357 
358 \subsection{Circuit leakage}
359 For a gate $G_j$, define
360 \[
361 \delta_j=\|(I-P)G_jP\|.
362 \]
363 Let $V_j=PG_jP$. A telescoping expansion gives
364 \[
365 G_m\cdots G_1P-V_m\cdots V_1P
366 =
367 \sum_{k=1}^m
368 G_m\cdots G_{k+1}(G_k-V_k)V_{k-1}\cdots V_1P.
369 \]
370 Taking norms yields the following.
371 
372 \begin{proposition}[Sum-of-leakages bound]
373 \label{s:prop:sum-leakage}
374 For an initial state in $P\Hh$,
375 \[
376 \|G_m\cdots G_1\ket{\psi_0}
377 -
378 V_m\cdots V_1\ket{\psi_0}\|
379 \le
380 \sum_{j=1}^m\delta_j.
381 \]
382 \end{proposition}
383 
384 This is conservative because leakage contributions may interfere destructively. Its value is that it is composable and can be checked gate by gate.
385 
386 \subsection{Decision-problem consequence}
387 If the packet representation is polynomial, the restricted updates are efficient, and
388 \[
389 \sum_j\delta_j\le\frac1{\poly(n)},
390 \]
391 then the approximate packet simulator reproduces the final acceptance probability to inverse-polynomial accuracy. After ordinary promise-gap amplification, this suffices for a deterministic polynomial-time decision algorithm.
392 
393 \subsection{Adaptive packet enlargement}
394 A practical simulator need not fix one packet forever. It can maintain an active set $A_t$ of packets, estimate transfers $P_\alpha G_tP_\beta$, and add a packet when its predicted mass exceeds a tolerance. The proof obligation becomes a global accounting identity:
395 \[
396 \text{total error}
397 \le
398 \text{discarded transfer}
399 +
400 \text{numerical error}
401 +
402 \text{measurement approximation}.
403 \]
404 The key research problem is to retain polynomial active size while certifying the tail.
405 
406 \begin{figure}[H]
407 \centering
408 \includegraphics[width=.76\textwidth]{assets/s_leakage_bound.pdf}
409 \caption{Recorded leakage examples and the analytic commutator certificate.}
410 \end{figure}
411 
412 \section{Moving packets, dynamic frames, and sparse transfer graphs}
413 \label{s:ch:dynamic-frames}
414 \index{moving packet}
415 \index{time-dependent projector}
416 \index{packet transfer graph}
417 
418 \subsection{Why one fixed projector is not the end of the theory}
419 The exact packet theorem in \cref{s:ch:exact-simulation} follows a state inside one fixed subspace. That is sufficient for a conserved charge, but it is not necessary for classical collapse. A circuit may move through a sequence of small subspaces, or it may preserve a small packet only after a time-dependent change of coordinates. The correct object is therefore a \emph{packet schedule}, not necessarily one static projector.
420 
421 \begin{definition}[Packet schedule]
422 For a circuit
423 \[
424 U=G_m\cdots G_1
425 \]
426 on a Hilbert space $\Hh$, a packet schedule is a sequence of orthogonal projectors
427 \[
428 P_0,P_1,\ldots,P_m.
429 \]
430 It is exact when
431 \begin{equation}
432 G_tP_{t-1}=P_tG_tP_{t-1}
433 \qquad(1\le t\le m).
434 \label{s:eq:dynamic-packet-condition}
435 \end{equation}
436 \end{definition}
437 
438 The condition says that gate $G_t$ maps the currently active packet into the next active packet. The dimensions may vary with time.
439 
440 \subsection{Exact dynamic-packet simulation}
441 Choose isometries
442 \[
443 B_t:\C^{D_t}\longrightarrow\Hh,
444 \qquad
445 B_tB_t^*=P_t,
446 \qquad
447 B_t^*B_t=I_{D_t},
448 \]
449 where $D_t=\rank P_t$. Define the rectangular coordinate update
450 \begin{equation}
451 M_t=B_t^*G_tB_{t-1}.
452 \label{s:eq:dynamic-coordinate-update}
453 \end{equation}
454 
455 \begin{theorem}[Exact dynamic-packet theorem]
456 \label{s:thm:dynamic-packet}
457 Suppose $P_0\ket{\psi_0}=\ket{\psi_0}$ and \cref{s:eq:dynamic-packet-condition} holds for every gate. Put
458 \[
459 z_0=B_0^*\ket{\psi_0},
460 \qquad
461 z_t=M_tz_{t-1}.
462 \]
463 Then
464 \[
465 G_t\cdots G_1\ket{\psi_0}=B_tz_t
466 \]
467 for every $t$.
468 \end{theorem}
469 
470 \begin{proof}
471 The claim is true at $t=0$. If the state after $t-1$ gates is $B_{t-1}z_{t-1}$, then
472 \[
473 G_tB_{t-1}z_{t-1}
474 =P_tG_tP_{t-1}B_{t-1}z_{t-1}
475 =B_tB_t^*G_tB_{t-1}z_{t-1}
476 =B_tM_tz_{t-1}.
477 \]
478 This is $B_tz_t$.
479 \end{proof}
480 
481 \begin{theorem}[Polynomial moving-packet collapse]
482 \label{s:thm:moving-packet-collapse}
483 Let $\{C_x\}$ be a polynomial-time uniform circuit family. Suppose an exact packet schedule can be produced from $x$ in polynomial time such that:
484 \begin{enumerate}
485 \item $\max_tD_t\le\poly(|x|)$;
486 \item the coordinate description of the initial state is computable in polynomial time;
487 \item each rectangular update $M_t$ can be applied to polynomial precision in polynomial time;
488 \item the final acceptance probability is computable from $z_m$ in polynomial time.
489 \end{enumerate}
490 Then the language decided by the circuit family belongs to $P$.
491 \end{theorem}
492 
493 \begin{proof}
494 The simulator stores at most polynomially many coordinates at every step and applies polynomially many polynomial-time updates. \Cref{s:thm:dynamic-packet} proves exactness before numerical rounding. Polynomial precision below the amplified promise gap gives a deterministic polynomial-time decision procedure.
495 \end{proof}
496 
497 \begin{derivedbox}
498 A circuit does not need one globally conserved sector. It is enough that the state follow an efficiently discoverable path through polynomial-dimensional sectors.
499 \end{derivedbox}
500 
501 \subsection{Moving frames and hidden symmetry}
502 The packet schedule has a useful coordinate form. Let $P$ be one fixed projector and let $W_t$ be unitaries with
503 \[
504 P_t=W_tPW_t^*.
505 \]
506 In the moving frame, the transformed gate is
507 \begin{equation}
508 \widetilde G_t
509 =W_t^*G_tW_{t-1}.
510 \label{s:eq:moving-frame-gate}
511 \end{equation}
512 The schedule condition is equivalent to
513 \[
514 \widetilde G_tP=P\widetilde G_tP.
515 \]
516 
517 \begin{corollary}[Moving-frame collapse]
518 \label{s:cor:moving-frame-collapse}
519 Suppose a polynomial-time uniform circuit admits efficiently described frames $W_t$ for which the transformed gates in \cref{s:eq:moving-frame-gate} preserve one fixed polynomial-dimensional packet, the initial state has efficiently computable coordinates in $W_0P\Hh$, and their restricted matrices and the transformed final measurement are efficiently computable. Then the circuit family is classically simulable in polynomial time.
520 \end{corollary}
521 
522 This is the appropriate theorem for a symmetry that changes orientation with time. Examples to test include Clifford frames, Gaussian mode frames, rotating spin axes, and gauge-fixed local coordinates.
523 
524 \begin{scopebox}
525 The frame must be independently discoverable and efficiently usable. Choosing $W_t=G_t\cdots G_1$ makes the transformed state trivial but is circular: computing that frame is the original simulation problem. The theorem is useful only when the frames have a compact classical description and their restricted actions can be computed without constructing the full state.
526 \end{scopebox}
527 
528 \begin{figure}[H]
529 \centering
530 \includegraphics[width=.94\textwidth]{assets/s_moving_frame_packets.pdf}
531 \caption{A circuit may fail to preserve one laboratory-frame packet while remaining inside a small packet in a computable moving frame.}
532 \end{figure}
533 
534 \subsection{Sparse packet-transfer graphs}
535 Let
536 \[
537 I=\sum_{\alpha\in\Lambda}P_\alpha
538 \]
539 be an orthogonal packet decomposition. Write the gate blocks as
540 \[
541 G_{t;\beta\alpha}=P_\beta G_tP_\alpha.
542 \]
543 Starting from an active packet set $S_0$, define recursively
544 \begin{equation}
545 S_t
546 =
547 \left\{
548 \beta:\exists\alpha\in S_{t-1}
549 \text{ with }G_{t;\beta\alpha}\ne0
550 \right\}.
551 \label{s:eq:reachable-packet-set}
552 \end{equation}
553 
554 \begin{corollary}[Reachable packet-graph collapse]
555 \label{s:cor:packet-graph-collapse}
556 Suppose the packet sets $S_t$ and nonzero transfer blocks are computable in polynomial time, and
557 \[
558 D_t
559 =
560 \sum_{\alpha\in S_t}\rank P_\alpha
561 \le\poly(n)
562 \]
563 for every $t$. If all active block updates and the final measurement are efficiently computable, then the circuit family is classically polynomial-time simulable.
564 \end{corollary}
565 
566 \begin{proof}
567 Take
568 \[
569 P_t=\sum_{\alpha\in S_t}P_\alpha.
570 \]
571 The definition of $S_t$ gives $G_tP_{t-1}=P_tG_tP_{t-1}$. Apply \cref{s:thm:moving-packet-collapse}.
572 \end{proof}
573 
574 This theorem permits exact sector changes. What matters is not that one charge be fixed, but that the union of reachable sectors remain polynomial.
575 
576 \begin{corollary}[Bounded-excitation collapse]
577 \label{s:cor:bounded-excitation-collapse}
578 Consider $n$ qubits and suppose the initial state and every circuit prefix are certified to lie in
579 \[
580 \Hh_{\le K}
581 =
582 \bigoplus_{k=0}^{K}\Hh_{n,k}
583 \]
584 for a fixed constant $K$. If initialization, the gate actions, and the measurement are computable in polynomial time in the occupation basis, then the circuit family lies in $P$, even when individual gates change excitation number.
585 \end{corollary}
586 
587 \begin{proof}
588 The active dimension is
589 \[
590 \sum_{k=0}^{K}\binom nk
591 =O(n^K).
592 \]
593 Let $P$ project onto $\Hh_{\le K}$. By the hypothesis on the actual circuit prefixes, $P\psi_t=\psi_t$ at every step. Consequently $PG_tP\psi_{t-1}=G_t\psi_{t-1}$ on the evolving state, even if the gate does not preserve all of $P\Hh$. The restricted update therefore reproduces that trajectory exactly. The hypothesis supplies efficient initialization, updates, and measurement in these polynomially many coordinates.
594 \end{proof}
595 
596 For example, a fixed-weight input followed by only a constant number of pair-creation or pair-annihilation events remains in a constant collection of low-weight sectors. Exact number conservation is therefore stronger than necessary.
597 
598 \begin{figure}[H]
599 \centering
600 \includegraphics[width=.90\textwidth]{assets/s_reachable_packet_graph.pdf}
601 \caption{Sector-changing gates remain classically tractable when the reachable packet graph and total active dimension stay polynomial.}
602 \end{figure}
603 
604 \subsection{Approximate dynamic packets}
605 Define the one-step leakage from the scheduled packet by
606 \[
607 \delta_t
608 =
609 \|(I-P_t)G_tP_{t-1}\|.
610 \]
611 Let
612 \[
613 \widehat G_t=P_tG_tP_{t-1}.
614 \]
615 
616 \begin{theorem}[Dynamic sum-of-leakages bound]
617 \label{s:thm:dynamic-leakage}
618 For an initial unit vector in $P_0\Hh$,
619 \[
620 \left\|
621 G_m\cdots G_1\ket{\psi_0}
622 -
623 \widehat G_m\cdots\widehat G_1\ket{\psi_0}
624 \right\|
625 \le
626 \sum_{t=1}^{m}\delta_t.
627 \]
628 For any acceptance operator $0\le M\le I$, the corresponding acceptance probabilities differ by at most
629 \[
630 2\sum_{t=1}^{m}\delta_t.
631 \]
632 \end{theorem}
633 
634 \begin{proof}
635 A telescoping expansion inserts $G_t-\widehat G_t$ at one time. On $P_{t-1}\Hh$ this difference equals $(I-P_t)G_tP_{t-1}$, while all other unitary or projected factors have norm at most one. Summing the operator norms proves the state bound. If $\psi$ and $\phi$ have norm at most one, then
636 \[
637 |\langle\psi,M\psi\rangle-\langle\phi,M\phi\rangle|
638 \le
639 (\|\psi\|+\|\phi\|)\|\psi-\phi\|
640 \le2\|\psi-\phi\|.
641 \]
642 \end{proof}
643 
644 \begin{corollary}[Approximate moving-packet collapse]
645 If the scheduled dimensions and updates are polynomial and
646 \[
647 \sum_t\delta_t\le\frac1{\poly(n)},
648 \]
649 then, after ordinary promise-gap amplification, the circuit family remains deterministically classically simulable in polynomial time.
650 \end{corollary}
651 
652 The result is conservative but fully composable. It extends the fixed-projector estimate of \cref{s:ch:approximate-symmetry} to moving frames and changing packet sets.
653 
654 
655 \subsection{An adaptive certificate from discarded state vectors}
656 The operator-norm leakage certificate is uniform over every input in a packet. An adaptive simulator can use a less expensive certificate that follows its actual approximate state. The discarded vector must be accounted for before any normalization.
657 
658 \begin{theorem}[Adaptive discarded-state certificate]
659 \label{s:thm:adaptive-discarded-state}
660 Let $G_1,\ldots,G_m$ be unitary operators on a finite-dimensional Hilbert space, and let $\psi_0=\phi_0$ be a unit vector. At each step choose an orthogonal projector $P_t$, possibly as a function of the previously computed approximate states. Define
661 \[
662 \psi_t=G_t\psi_{t-1},\qquad
663 \phi_t=P_tG_t\phi_{t-1},\qquad
664 \eta_t=\|(I-P_t)G_t\phi_{t-1}\|.
665 \]
666 Then
667 \[
668 \|\psi_m-\phi_m\|\le\sum_{t=1}^m\eta_t.
669 \]
670 For an effect $0\le M\le I$,
671 \[
672 \left|\langle\psi_m,M\psi_m\rangle-\langle\phi_m,M\phi_m\rangle\right|
673 \le2\sum_{t=1}^m\eta_t.
674 \]
675 No renormalization of $\phi_t$ is performed. The second quadratic form is an unnormalized acceptance estimate.
676 \end{theorem}
677 
678 \begin{proof}
679 Fix the projectors chosen during the particular run. Put $d_t=(I-P_t)G_t\phi_{t-1}$. Subtraction gives the exact recurrence
680 \[
681 \psi_t-\phi_t=G_t(\psi_{t-1}-\phi_{t-1})+d_t.
682 \]
683 Since $\psi_0-\phi_0=0$, iteration yields
684 \[
685 \psi_m-\phi_m=\sum_{t=1}^mG_m\cdots G_{t+1}d_t.
686 \]
687 Every unitary product preserves norm, so the triangle inequality proves the state estimate. Also $\|\psi_m\|=1$ and $\|\phi_m\|\le1$ because each projector is contractive. Expanding the difference of the two quadratic forms and using $\|M\|\le1$ gives the factor two. This proof applies to the chosen run even when the projectors were selected adaptively.
688 \end{proof}
689 
690 \begin{example}[A rational two-step certificate]
691 Take
692 \[
693 G=\begin{pmatrix}3/5&-4/5\\4/5&3/5\end{pmatrix},
694 \qquad
695 P=\begin{pmatrix}1&0\\0&0\end{pmatrix},
696 \qquad
697 \psi_0=\phi_0=\begin{pmatrix}1\\0\end{pmatrix}.
698 \]
699 Using $G_1=G_2=G$ and $P_1=P_2=P$ gives
700 \[
701 \phi_2=\begin{pmatrix}9/25\\0\end{pmatrix},\qquad
702 \psi_2=\begin{pmatrix}-7/25\\24/25\end{pmatrix},\qquad
703 \eta_1=4/5,\quad\eta_2=12/25.
704 \]
705 The squared state error is $832/625$, below $(\eta_1+\eta_2)^2=1024/625$. The rational validation script checks these values exactly. The deliberately large tail illustrates a valid but loose certificate, not an efficient approximation.
706 \end{example}
707 
708 The theorem closes global error accounting for any adaptive projection run whose discarded vectors or certified norm bounds can be computed. It does not prove that the retained representation stays polynomial, that the discarded norm is cheap to evaluate, or that a small tail can always be found. Those are separate algorithmic obligations. This is a written theorem with exact finite controls, not an additional Lean formalization.
709 
710 \chapter{Exact symmetry families}
711 \section{Fixed charge and exact-number circuits}
712 \label{s:ch:fixed-charge}
713 \index{Hamming weight}
714 \index{particle number}
715 
716 \subsection{Excitation-number packets}
717 For $n$ qubits, define
718 \[
719 \widehat N
720 =
721 \sum_{q=1}^n\frac{I-Z_q}{2}.
722 \]
723 Its eigenvalues are $k=0,1,\ldots,n$. The projector onto Hamming weight $k$ is
724 \[
725 P_{n,k}
726 =
727 \sum_{|x|=k}\ket x\bra x,
728 \]
729 and
730 \[
731 \dim P_{n,k}\Hh
732 =
733 \binom nk.
734 \]
735 The decomposition
736 \[
737 (\C^2)^{\otimes n}
738 =
739 \bigoplus_{k=0}^n\Hh_{n,k}
740 \]
741 recovers the full dimension through
742 \[
743 \sum_{k=0}^n\binom nk=2^n.
744 \]
745 
746 \subsection{Number-preserving gates}
747 Single-qubit $R_Z$ gates commute with $\widehat N$. A two-qubit exchange rotation acts in the ordered basis $\ket{00},\ket{01},\ket{10},\ket{11}$ as
748 \[
749 U_{XY}(\theta,\phi)
750 =
751 \begin{pmatrix}
752 1&0&0&0\\
753 0&\cos\theta&-ie^{-i\phi}\sin\theta&0\\
754 0&-ie^{i\phi}\sin\theta&\cos\theta&0\\
755 0&0&0&1
756 \end{pmatrix}.
757 \]
758 It rotates $\ket{01}$ and $\ket{10}$ while fixing $\ket{00}$ and $\ket{11}$, so it preserves exact Hamming weight.
759 
760 \begin{corollary}[Fixed-charge polynomial simulation]
761 \label{s:cor:fixed-charge-poly}
762 For every fixed $k$, a polynomial-time uniform family of number-preserving circuits initialized in $\Hh_{n,k}$ and measured by an efficiently computable observable is classically simulable in polynomial time, provided the initial weight-$k$ coordinates can be computed efficiently and each restricted local gate is efficiently applied in that basis.
763 \end{corollary}
764 
765 \begin{proof}
766 For fixed $k$,
767 \[
768 \dim\Hh_{n,k}=\binom nk=O(n^k).
769 \]
770 The weight-$k$ basis is efficiently indexed by $k$-element subsets. A local number-preserving gate changes only basis states containing the affected occupation pattern. Apply \cref{s:thm:poly-packet}.
771 \end{proof}
772 
773 \subsection{Sparse update structure}
774 A one-qubit diagonal phase changes one amplitude at a time. An exchange gate on modes $p,q$ couples a basis state only to the state obtained by moving one excitation between those modes. Thus every column of the restricted gate has at most two nonzero entries. For fixed $k$, the total update cost is polynomial in $n$.
775 
776 \subsection{Uniformity and input encoding}
777 The fixed-charge corollary assumes $k$ is a fixed constant independent of $n$. It also applies when $k=O(1)$ is supplied by the circuit family. If $k$ is written in binary and allowed to scale as $n/2$, the sector can become exponential. The theorem is about the dimension and update cost of the actual active sector, not the name of the symmetry.
778 
779 \begin{figure}[H]
780 \centering
781 \includegraphics[width=.83\textwidth]{assets/s_dimension_scaling.pdf}
782 \caption{Fixed weight and permutation symmetry can be polynomial, while half filling remains exponential.}
783 \end{figure}
784 
785 \subsection{Observables}
786 A diagonal observable depending on occupations is immediate. Few-body number-preserving observables are sparse in the subset basis. More global observables may require additional structure. The measurement hypothesis in \cref{s:thm:poly-packet} cannot be omitted: a compactly evolved state does not help if the requested output itself hides exponential work.
787 
788 \section{The exact weight-two benchmark}
789 \label{s:ch:benchmarks}
790 \index{benchmark}
791 
792 \subsection{Purpose and status}
793 The benchmark record compares a full state-vector simulator with a simulator restricted to the exact weight-two packet. Both use the same local gate arithmetic. The benchmark is not a hardware claim and not a universal performance model. It shows that the exact dimension reduction can translate into large memory and repeated-application gains in an ordinary implementation.
794 
795 \begin{recordbox}
796 At $n=20$, the full state has $1{,}048{,}576$ amplitudes and the exact weight-two packet has $190$. The archived repeated-application gain is $958.8$, the one-shot gain is $54.8$, and the amplitude-memory ratio is $5518.8$. The recorded relative reconstruction error is zero at the displayed precision.
797 \end{recordbox}
798 
799 \subsection{Recorded table}
800 \begin{longtable}{@{}rrrrrrr@{}}
801 \caption{Recorded exact-weight-two benchmark.}\label{s:tab:weight-two}\\
802 \toprule
803 $n$ & full dim. & packet dim. & apply gain & one-shot gain & memory gain & rel. error\\
804 \midrule
805 \endfirsthead
806 \toprule
807 $n$ & full dim. & packet dim. & apply gain & one-shot gain & memory gain & rel. error\\
808 \midrule
809 \endhead
810 8 & 256 & 28 & 1.11 & 1.64 & 9.14 & 0\\
811 10 & 1,024 & 45 & 1.51 & 2.02 & 22.8 & 0\\
812 12 & 4,096 & 66 & 2.95 & 3.98 & 62.1 & 0\\
813 14 & 16,384 & 91 & 8.55 & 11.0 & 180.0 & 0\\
814 16 & 65,536 & 120 & 33.0 & 36.9 & 546.1 & 0\\
815 18 & 262,144 & 153 & 131.3 & 39.1 & 1,713.4 & 0\\
816 20 & 1,048,576 & 190 & 958.8 & 54.8 & 5,518.8 & 0\\
817 \bottomrule
818 \end{longtable}
819 
820 \subsection{What is machine independent}
821 The dimension identity
822 \[
823 \frac{2^n}{\binom n2}
824 \]
825 is independent of implementation. It predicts an exponential memory advantage for fixed $k=2$. The measured runtime ratio need not equal the dimension ratio. Packet indexing, compilation, sparse update kernels, allocation, and cache behavior determine the constant factors.
826 
827 \subsection{Repeated application versus one shot}
828 Let $C_{\rm compile}$ be the cost of constructing the packet basis and restricted gate plans, and let $C_{\rm apply}$ be one packet application. Reusing the compiled plan $R$ times costs
829 \[
830 C_{\rm packet}(R)
831 =
832 C_{\rm compile}+RC_{\rm apply}.
833 \]
834 If the full path costs $RC_{\rm full}$, the packet method breaks even when
835 \[
836 R>
837 \frac{C_{\rm compile}}
838 {C_{\rm full}-C_{\rm apply}}.
839 \]
840 This is why time evolution, parameter sweeps, variational loops, and repeated likelihood evaluations are natural applications.
841 
842 \begin{figure}[H]
843 \centering
844 \includegraphics[width=.86\textwidth]{assets/s_weight_two_benchmark.pdf}
845 \caption{Recorded runtime and memory gains for the exact-weight-two packet.}
846 \end{figure}
847 
848 \subsection{Independent reconstruction check}
849 The release code generates a random packet state, embeds it in the full Hilbert space, applies the same $R_Z$ and exchange gates through both arithmetic paths, and compares the final states. The representative checks at $(n,k)=(6,1),(8,2),(10,2)$ produce errors near machine precision.
850 
851 \paragraph{Scope.}
852 The recorded benchmark supports exactness and implementation value for a symmetry-preserving subclass. It does not show that generic quantum circuits admit comparable reductions.
853 
854 \section{Coarse packets and the honest limitation}
855 \label{s:ch:coarse-packets}
856 
857 \subsection{Parity}
858 The even- and odd-parity packets each have dimension
859 \[
860 2^{n-1}.
861 \]
862 Parity removes half the state vector. This can produce a useful constant factor, but it does not change exponential scaling.
863 
864 A pair-creation rotation mixes $\ket{00}$ and $\ket{11}$ and therefore changes excitation number by two while preserving parity. The packet is exact for a parity-preserving circuit, but its internal dimension remains exponential.
865 
866 \subsection{Weight modulo four}
867 A four-qubit rotation between $\ket{0000}$ and $\ket{1111}$ changes excitation number by four. It can mix exact-weight sectors while preserving weight modulo four. A single residue packet contains asymptotically one quarter of all basis states. Again, the reduction is a constant factor.
868 
869 \subsection{Half filling}
870 At half filling,
871 \[
872 \binom n{\lfloor n/2\rfloor}
873 \sim
874 \frac{2^n}{\sqrt{\pi n/2}}.
875 \]
876 The packet is smaller by a polynomial factor, but it remains exponential. At $n=20$, the half-filled packet contains $184{,}756$ amplitudes. The archived repeated-application gain is approximately $7.396$, while the one-shot gain is $0.6529$, meaning the packet path was slower in that single-run test after compilation overhead.
877 
878 \begin{recordbox}
879 The half-filled benchmark demonstrates a necessary distinction: dimension reduction can be exact and useful without yielding polynomial complexity or a one-shot speedup.
880 \end{recordbox}
881 
882 \begin{figure}[H]
883 \centering
884 \includegraphics[width=.82\textwidth]{assets/s_coarse_vs_fine.pdf}
885 \caption{Parity and mod-four packets retain an exponential number of basis states.}
886 \end{figure}
887 
888 \subsection{Entanglement inside a packet}
889 A small number of symmetry labels does not imply low entanglement. The half-filled packet can support volume-law entanglement. Tensor-network bond dimension and packet dimension are independent resources. A robust simulator should therefore track both
890 \[
891 (D_{\rm packet},\chi_{\rm internal}),
892 \]
893 where $\chi_{\rm internal}$ measures the cost of representing the state inside the packet.
894 
895 \subsection{The no-label shortcut}
896 A stabilizer syndrome is only a label. A momentum quantum number is only a label. A total charge residue is only a label. The internal multiplicity space may still contain exponentially many degrees of freedom. The packet-simulation theorem becomes polynomial only when the complete active representation, not merely the label set, has polynomial classical cost.
897 
898 \section{Permutation-symmetric circuits and Dicke coordinates}
899 \label{s:ch:permutation-symmetry}
900 \index{Dicke state}
901 \index{permutation symmetry}
902 
903 \subsection{The symmetric subspace}
904 Let the symmetric group $S_n$ act by permuting the $n$ tensor factors. The fully symmetric qubit subspace is spanned by the Dicke states
905 \[
906 \ket{D_n^k}
907 =
908 \binom nk^{-1/2}
909 \sum_{|x|=k}\ket x,
910 \qquad
911 0\le k\le n.
912 \]
913 Its dimension is $n+1$.
914 
915 \begin{derivedbox}
916 If the initial state is permutation symmetric with efficiently computable Dicke coordinates, every gate preserves the fully symmetric subspace, the gate matrices in the Dicke basis are computable in polynomial time, and the final measurement is permutation invariant and efficient, then the circuit family lies in $P$.
917 \end{derivedbox}
918 
919 \begin{theorem}[Permutation-symmetric collapse]
920 \label{s:thm:permutation-collapse}
921 Under the hypotheses above, an $n$-qubit circuit can be simulated using an $(n+1)$-component classical state vector and polynomial-time updates.
922 \end{theorem}
923 
924 \begin{proof}
925 The projector onto the trivial $S_n$ representation has rank $n+1$. The Dicke basis is explicitly indexed by $k=0,\ldots,n$. Apply \cref{s:thm:poly-packet}.
926 \end{proof}
927 
928 \begin{figure}[H]
929 \centering
930 \includegraphics[width=.94\textwidth]{assets/s_dicke_basis.pdf}
931 \caption{Computational-basis orbits become Dicke coordinates.}
932 \end{figure}
933 
934 \subsection{Collective spin operators}
935 Define
936 \[
937 J_a=\frac12\sum_{q=1}^n\sigma_a^{(q)},
938 \qquad a\in\{x,y,z\}.
939 \]
940 The operators $J_a$ preserve the symmetric subspace. We use the computational convention $\sigma_z\ket0=\ket0$ and $\sigma_z\ket1=-\ket1$. Thus $J_z\ket{D_n^k}=(n/2-k)\ket{D_n^k}$. For the following occupation formulas define $J_+=J_x-iJ_y$ and $J_-=J_x+iJ_y$, so that the subscript records increasing or decreasing excitation number rather than magnetic quantum number. Then
941 \[
942 J_+\ket{D_n^k}
943 =
944 \sqrt{(n-k)(k+1)}\ket{D_n^{k+1}},
945 \]
946 \[
947 J_-\ket{D_n^k}
948 =
949 \sqrt{k(n-k+1)}\ket{D_n^{k-1}}.
950 \]
951 Thus collective rotations and polynomial functions of collective spin admit banded or structured updates on $n+1$ amplitudes.
952 
953 \subsection{Symmetric qudits}
954 For local dimension $d$, the symmetric subspace has occupation-number basis
955 \[
956 (n_1,\ldots,n_d),
957 \qquad
958 n_1+\cdots+n_d=n,
959 \]
960 and dimension
961 \begin{equation}
962 \dim\Sym^n(\C^d)
963 =
964 \binom{n+d-1}{d-1}.
965 \label{s:eq:symmetric-qudit-dim}
966 \end{equation}
967 For fixed $d$, this is polynomial in $n$.
968 
969 \begin{corollary}[Fixed-local-dimension symmetric qudits]
970 A uniform family of fully symmetric $d$-level circuits is classically polynomial-time simulable for fixed $d$, provided its occupation-basis updates and measurement are polynomial-time computable.
971 \end{corollary}
972 
973 \begin{figure}[H]
974 \centering
975 \includegraphics[width=.80\textwidth]{assets/s_symmetric_qudit_scaling.pdf}
976 \caption{Symmetric qudit sectors remain polynomial for every fixed local dimension.}
977 \end{figure}
978 
979 \subsection{What full symmetry excludes}
980 A generic two-qubit gate acting on one selected pair does not preserve the fully symmetric subspace. Symmetry is preserved by collective gates or by circuits arranged so that the total operation commutes with all permutations. A gatewise packet simulator requires gatewise invariance, or else it must combine several elementary gates into a symmetry-preserving layer and audit intermediate leakage.
981 
982 \section{Schur--Weyl coordinates and total-spin packets}
983 \label{s:ch:schur}
984 \index{Schur-Weyl duality}
985 
986 \subsection{Decomposition}
987 For $n$ qudits of local dimension $d$, Schur--Weyl duality decomposes
988 \[
989 (\C^d)^{\otimes n}
990 \cong
991 \bigoplus_{\lambda\vdash n,\,\ell(\lambda)\le d}
992 \mathcal U_\lambda\otimes\mathcal V_\lambda,
993 \]
994 where $\mathcal U_\lambda$ carries an irreducible unitary-group representation and $\mathcal V_\lambda$ carries a symmetric-group representation. A permutation-invariant operator acts as
995 \[
996 A
997 =
998 \bigoplus_\lambda
999 A_\lambda\otimes I_{\mathcal V_\lambda}.
1000 \]
1001 
1002 The label $\lambda$ can be polynomially short even when the multiplicity space $\mathcal V_\lambda$ is exponentially large. This is a canonical example of the difference between a small packet label and a small active representation.
1003 
1004 \subsection{Qubit total spin}
1005 For qubits, the decomposition may be labeled by total spin $j$ and a multiplicity index. A collective $SU(2)$ operation acts nontrivially only on the $(2j+1)$-dimensional spin factor and as the identity on multiplicity. If the initial state and observable are insensitive to multiplicity, the effective dimension can be small. If arbitrary information is stored in multiplicity, total-spin labeling alone does not compress it.
1006 
1007 \begin{principle}[Multiplicity audit]
1008 A representation-theoretic packet must be recorded as
1009 \[
1010 \text{irrep label}
1011 \quad+
1012 \text{irrep carrier}
1013 \quad+
1014 \text{multiplicity space}.
1015 \]
1016 Dropping the multiplicity space is valid only when the dynamics, input, and measurement make it redundant.
1017 \end{principle}
1018 
1019 \subsection{Efficient Schur simulation regime}
1020 A Schur-coordinate simulation is polynomial when the number of active partitions is polynomial, the retained carrier and multiplicity dimensions are polynomial or compactly represented, and each gate has an efficient action in these coordinates. Fully symmetric dynamics is the one-row partition and therefore the simplest case.
1021 
1022 \subsection{Possible compiler use}
1023 A symmetry compiler can detect collective layers, transform them into Schur coordinates, apply small representation matrices, and transform only when required. The transformation itself must be costed. In a purely classical simulator, one may never materialize the full Schur transform if the initial state is already specified by occupation or spin coordinates.
1024 
1025 \begin{frontierbox}
1026 A broad Schur-based collapse theorem requires explicit uniform algorithms for active-partition discovery, multiplicity handling, and local-gate updates. The decomposition alone is not the algorithm.
1027 \end{frontierbox}
1028 
1029 \section{Permutation-invariant mixed states and commutant compression}
1030 \label{s:ch:commutant-collapse}
1031 \index{commutant compression}
1032 \index{permutation twirl}
1033 \index{permutation-invariant density operator}
1034 
1035 \subsection{Why multiplicity can disappear without being discarded}
1036 The fully symmetric subspace is only one Schur--Weyl packet. A general permutation-invariant mixed state can occupy every Schur label while still admitting a polynomial classical description for fixed local dimension. The reason is that the exponentially large symmetric-group multiplicities occur as identity factors rather than independent dynamical coordinates.
1037 
1038 Let $S_n$ act on
1039 \[
1040 \Hh_{n,d}=(\C^d)^{\otimes n}
1041 \]
1042 by permuting tensor factors. Schur--Weyl duality gives
1043 \begin{equation}
1044 \Hh_{n,d}
1045 \cong
1046 \bigoplus_{\lambda\vdash n,\,\ell(\lambda)\le d}
1047 \mathcal U_\lambda\otimes\mathcal V_\lambda,
1048 \label{s:eq:schur-decomp-commutant}
1049 \end{equation}
1050 where $S_n$ acts trivially on the first tensor factor and irreducibly on $\mathcal V_\lambda$.
1051 
1052 \subsection{The permutation twirl}
1053 Define the twirling channel
1054 \begin{equation}
1055 \mathcal T_n(X)
1056 =
1057 \frac1{n!}
1058 \sum_{\pi\in S_n}
1059 U_\pi XU_\pi^*.
1060 \label{s:eq:permutation-twirl}
1061 \end{equation}
1062 Its image is the commutant of the permutation action.
1063 
1064 \begin{lemma}[Invariant observables see only the twirl]
1065 \label{s:lem:twirl-observable}
1066 If $A$ commutes with every $U_\pi$, then
1067 \[
1068 \Tr(A\rho)
1069 =
1070 \Tr\bigl(A\mathcal T_n(\rho)\bigr)
1071 \]
1072 for every density operator $\rho$.
1073 \end{lemma}
1074 
1075 \begin{proof}
1076 Using cyclicity of the trace and $U_\pi^*AU_\pi=A$,
1077 \[
1078 \Tr\bigl(A\mathcal T_n(\rho)\bigr)
1079 =
1080 \frac1{n!}\sum_\pi
1081 \Tr(AU_\pi\rho U_\pi^*)
1082 =
1083 \frac1{n!}\sum_\pi
1084 \Tr(U_\pi^*AU_\pi\rho)
1085 =
1086 \Tr(A\rho).
1087 \]
1088 \end{proof}
1089 
1090 If a unitary $U$ and acceptance operator $M$ are permutation invariant, then $U^*MU$ is invariant. Therefore the final probability depends on the input only through its twirl. This permits an observable-specific collapse even when the original pure input is not itself symmetric.
1091 
1092 \subsection{Exact commutant record}
1093 Let
1094 \[
1095 u_\lambda=\dim\mathcal U_\lambda,
1096 \qquad
1097 f_\lambda=\dim\mathcal V_\lambda.
1098 \]
1099 Schur's lemma gives the following normal form.
1100 
1101 \begin{lemma}[Permutation-invariant state normal form]
1102 \label{s:lem:invariant-state-normal-form}
1103 A density operator $\rho$ commutes with every permutation if and only if it can be written as
1104 \begin{equation}
1105 \rho
1106 =
1107 \bigoplus_\lambda
1108 p_\lambda\,\rho_\lambda\otimes
1109 \frac{I_{\mathcal V_\lambda}}{f_\lambda},
1110 \label{s:eq:commutant-state-record}
1111 \end{equation}
1112 where $p_\lambda\ge0$, $\sum_\lambda p_\lambda=1$, and each $\rho_\lambda$ is a density operator on $\mathcal U_\lambda$ whenever $p_\lambda>0$. The weights $p_\lambda$ and the unnormalized blocks $p_\lambda\rho_\lambda$ are unique. The normalized block $\rho_\lambda$ is unique only when $p_\lambda>0$ and is omitted when $p_\lambda=0$.
1113 \end{lemma}
1114 
1115 The complete state record is therefore
1116 \[
1117 \left\{
1118 (p_\lambda,\rho_\lambda)
1119 \right\}_\lambda.
1120 \]
1121 The multiplicity dimension $f_\lambda$ affects normalization and degeneracy, but no $f_\lambda\times f_\lambda$ matrix needs to be stored.
1122 
1123 A permutation-invariant unitary has the form
1124 \begin{equation}
1125 U
1126 =
1127 \bigoplus_\lambda
1128 U_\lambda\otimes I_{\mathcal V_\lambda},
1129 \label{s:eq:commutant-unitary-form}
1130 \end{equation}
1131 and a permutation-invariant measurement operator has the analogous form
1132 \[
1133 M
1134 =
1135 \bigoplus_\lambda
1136 M_\lambda\otimes I_{\mathcal V_\lambda}.
1137 \]
1138 The output probability is
1139 \begin{equation}
1140 \Tr(MU\rho U^*)
1141 =
1142 \sum_\lambda
1143 p_\lambda
1144 \Tr\bigl(M_\lambda U_\lambda\rho_\lambda U_\lambda^*\bigr).
1145 \label{s:eq:commutant-output}
1146 \end{equation}
1147 
1148 \subsection{Polynomial parameter bound}
1149 The number of partitions of $n$ with at most $d$ parts is bounded by the number of weak compositions:
1150 \[
1151 \#\{\lambda:\ell(\lambda)\le d\}
1152 \le
1153 \binom{n+d-1}{d-1}
1154 =O_d(n^{d-1}).
1155 \]
1156 The Weyl dimension formula gives
1157 \begin{equation}
1158 u_\lambda
1159 =
1160 \prod_{1\le i<j\le d}
1161 \frac{\lambda_i-\lambda_j+j-i}{j-i}
1162 =O_d\left(n^{d(d-1)/2}\right).
1163 \label{s:eq:weyl-dimension-bound}
1164 \end{equation}
1165 Therefore
1166 \begin{equation}
1167 \sum_\lambda u_\lambda^2
1168 =O_d\left(n^{d^2-1}\right).
1169 \label{s:eq:commutant-parameter-bound}
1170 \end{equation}
1171 
1172 \begin{theorem}[Schur-commutant collapse]
1173 \label{s:thm:schur-commutant-collapse}
1174 Fix the local dimension $d$. Consider a polynomial-time uniform family of permutation-invariant quantum circuits or channels on $n$ qudits. Suppose:
1175 \begin{enumerate}
1176 \item the Schur-block record of the twirled input can be constructed in polynomial time;
1177 \item the induced update on the invariant operator record in \cref{s:eq:commutant-state-record} is computable to polynomial precision in polynomial time;
1178 \item the final measurement is permutation invariant and its Schur blocks are efficiently computable.
1179 \end{enumerate}
1180 Then the associated decision problem belongs to $P$.
1181 \end{theorem}
1182 
1183 \begin{proof}
1184 Permutation covariance keeps the density operator inside the commutant algebra. By \cref{s:eq:commutant-parameter-bound}, that algebra has polynomial dimension for fixed $d$. The hypotheses supply polynomial-time initialization, updates, and measurement on this record. Apply \cref{s:thm:compressed-packet}.
1185 \end{proof}
1186 
1187 \begin{derivedbox}
1188 For fixed local dimension, permutation-invariant mixed-state dynamics can be classically polynomial even when the state has support across exponentially large symmetric-group multiplicity spaces. Those multiplicities are exact identity factors in the invariant operator record.
1189 \end{derivedbox}
1190 
1191 \subsection{Qubit corollary}
1192 For qubits, Schur labels are total spins $j$. The carrier dimension is
1193 \[
1194 u_j=2j+1\le n+1,
1195 \]
1196 and there are at most $\lfloor n/2\rfloor+1$ labels. Hence
1197 \begin{equation}
1198 \sum_j(2j+1)^2=O(n^3).
1199 \label{s:eq:qubit-commutant-size}
1200 \end{equation}
1201 
1202 \begin{corollary}[Permutation-invariant qubit channels]
1203 \label{s:cor:perm-invariant-qubit-channels}
1204 A uniform permutation-covariant qubit channel family with efficiently computable total-spin block updates, efficiently available twirled input blocks, and a permutation-invariant measurement is classically simulable using $O(n^3)$ density-matrix parameters, up to constant factors and numerical precision.
1205 \end{corollary}
1206 
1207 Collective Hamiltonians that are polynomial expressions in $J_x,J_y,J_z$ are a basic test class because their total-spin matrices can be generated directly without constructing the full $2^n\times2^n$ operator.
1208 
1209 \begin{figure}[H]
1210 \centering
1211 \includegraphics[width=.94\textwidth]{assets/s_schur_commutant_compression.pdf}
1212 \caption{Permutation-invariant density operators retain the polynomial carrier blocks and replace each possibly exponential multiplicity space by an exact identity factor.}
1213 \end{figure}
1214 
1215 \subsection{What this theorem does not cover}
1216 The theorem does not make an arbitrary local circuit easy. A gate acting on one selected pair generally fails to commute with all permutations. An arbitrary input may have Schur blocks that are difficult to compute from its succinct description. A non-invariant measurement can read information stored in multiplicity coordinates. Finally, allowing local dimension $d$ to grow with $n$ can make the commutant record superpolynomial.
1217 
1218 The result is therefore a complete collapse theorem for a declared symmetry and access model, not a claim that Schur--Weyl decomposition alone solves generic many-body simulation.
1219 
1220 \section{Orbit-quotient quantum walks}
1221 \label{s:ch:orbit-quotients}
1222 \index{quantum walk}
1223 \index{orbit quotient}
1224 
1225 \subsection{Orbit states}
1226 Let a group $G$ act by automorphisms on a finite graph with vertex set $V$. The orbits are $\mathcal O_1,\ldots,\mathcal O_r$. Define normalized orbit states
1227 \[
1228 \ket{\mathcal O_a}
1229 =
1230 \frac1{\sqrt{|\mathcal O_a|}}
1231 \sum_{x\in\mathcal O_a}\ket x.
1232 \]
1233 If the adjacency or Hamiltonian $H$ commutes with the group action, the span of these states is invariant whenever the partition is equitable.
1234 
1235 The quotient matrix is
1236 \[
1237 \widetilde H_{ab}
1238 =
1239 \bra{\mathcal O_a}H\ket{\mathcal O_b}.
1240 \]
1241 
1242 \begin{theorem}[Orbit-quotient collapse]
1243 \label{s:thm:orbit-collapse}
1244 Suppose a uniformly described quantum walk has a polynomial number $r(n)$ of relevant orbits, an orbit-uniform initial state, an orbit-invariant final measurement, and polynomial-time algorithms for orbit sizes, quotient entries, initial orbit coordinates, and the restricted final measurement. For continuous-time evolution, also assume a polynomial bound on $|t|\|\widetilde H\|$ and efficient entry access to the precision required by the simulation. Then the walk can be simulated classically in polynomial time by the $r(n)\times r(n)$ quotient dynamics.
1245 \end{theorem}
1246 
1247 \begin{proof}
1248 The orbit-state span is invariant. The state is represented by $r(n)$ amplitudes. Polynomial-time computation of quotient entries and ordinary polynomial-precision linear algebra satisfy \cref{s:thm:poly-packet}.
1249 \end{proof}
1250 
1251 \subsection{Hypercube example}
1252 The $n$-dimensional hypercube is invariant under coordinate permutations. Its vertex orbits are Hamming-weight layers $0,1,\ldots,n$. In the normalized orbit basis, the quotient adjacency has couplings
1253 \begin{equation}
1254 \bra{k+1}A\ket{k}
1255 =
1256 \sqrt{(k+1)(n-k)}.
1257 \label{s:eq:hypercube-coupling}
1258 \end{equation}
1259 Thus a walk on $2^n$ vertices initialized at $0^n$ evolves in an $(n+1)$-dimensional subspace.
1260 
1261 \begin{figure}[H]
1262 \centering
1263 \includegraphics[width=.94\textwidth]{assets/s_hypercube_quotient.pdf}
1264 \caption{The hypercube walk collapses to a weighted path of Hamming-weight orbits.}
1265 \end{figure}
1266 
1267 \subsection{The succinct-input caveat}
1268 If the full graph is supplied explicitly, a polynomial-in-$|V|$ algorithm may still be exponential in the succinct parameter $n$. The theorem requires quotient data computable directly from the succinct graph description. Discovering graph automorphisms or orbit partitions can itself be difficult. For regular families such as hypercubes, Johnson graphs, association schemes, and Cayley graphs with known character theory, the quotient is explicit.
1269 
1270 \subsection{Fourier packets}
1271 On a cycle, translation characters diagonalize the adjacency operator. The continuous-time walk
1272 \[
1273 \ket{\psi(t)}=e^{-itA}\ket0
1274 \]
1275 is a sum of Fourier-character packets. This is the same discrete Fourier transform that appears as a signal-processing coordinate change, a group-character decomposition, and a quantum basis transformation.
1276 
1277 \section{Few bosons and few fermions}
1278 \label{s:ch:few-particles}
1279 \index{boson}
1280 \index{fermion}
1281 
1282 \subsection{Bosonic occupation space}
1283 For $N$ indistinguishable bosons in $m$ modes, a Fock basis state is an occupation vector
1284 \[
1285 (n_1,\ldots,n_m),
1286 \qquad
1287 n_1+\cdots+n_m=N.
1288 \]
1289 The dimension is
1290 \begin{equation}
1291 D_{\rm boson}(m,N)
1292 =
1293 \binom{N+m-1}{N}.
1294 \label{s:eq:boson-dim}
1295 \end{equation}
1296 For fixed $N$, this is $O(m^N)$.
1297 
1298 \subsection{Fermionic occupation space}
1299 For $N$ fermions in $m$ modes, each mode is occupied at most once and
1300 \begin{equation}
1301 D_{\rm fermion}(m,N)
1302 =
1303 \binom mN.
1304 \label{s:eq:fermion-dim}
1305 \end{equation}
1306 For fixed $N$, this is also polynomial in $m$.
1307 
1308 \begin{corollary}[Few-particle collapse]
1309 A polynomial-size number-preserving bosonic or fermionic circuit with a fixed number of particles is classically polynomial-time simulable if its initial occupation coordinates, mode-gate updates, and final observable are computable in polynomial time in the occupation basis.
1310 \end{corollary}
1311 
1312 \begin{proof}
1313 Use \cref{s:eq:boson-dim,s:eq:fermion-dim} and \cref{s:thm:poly-packet}.
1314 \end{proof}
1315 
1316 \begin{figure}[H]
1317 \centering
1318 \includegraphics[width=.82\textwidth]{assets/s_few_particle_dimensions.pdf}
1319 \caption{Fixed-particle bosonic and fermionic sectors grow polynomially with the number of modes.}
1320 \end{figure}
1321 
1322 \subsection{Gate updates}
1323 A number-preserving one-body unitary acts on mode creation operators by
1324 \[
1325 a_i^\dagger
1326 \longmapsto
1327 \sum_j U_{ji}a_j^\dagger.
1328 \]
1329 A generic dense mode transformation can induce many occupation-basis transitions, but for fixed $N$ the basis dimension remains polynomial. Local hopping and phase gates are sparse. Few-body interactions remain polynomial to apply for fixed $N$, although the exponent can grow with $N$.
1330 
1331 \subsection{Where the theorem stops}
1332 If $N$ scales linearly with $m$, both dimensions become exponential. The fixed-number symmetry still reduces the full Fock space, but it does not prove polynomial simulation. Boson-sampling-type interference also shows that a fixed total particle number is not enough when the particle count itself scales with input size and the output asks for detailed many-body amplitudes.
1333 
1334 \begin{scopebox}
1335 The corollary is a fixed-particle theorem. It is not a claim that general many-boson or many-fermion quantum dynamics are classically easy.
1336 \end{scopebox}
1337 
1338 \section{Scaling phase diagrams for charge, particles, and local dimension}
1339 \label{s:ch:scaling-phases}
1340 \index{particle-number scaling}
1341 \index{quasipolynomial simulation}
1342 \index{subexponential simulation}
1343 
1344 \subsection{Exact sector size is a complexity phase variable}
1345 The statement ``fixed particle number is polynomial'' has a sharp extension. Let the particle number depend on the system size:
1346 \[
1347 k=k(n).
1348 \]
1349 The explicit-amplitude simulation cost of one fermionic or qubit weight packet is governed by
1350 \[
1351 D_{n,k}=\binom nk.
1352 \]
1353 For $1\le k\le n$, the standard bounds
1354 \begin{equation}
1355 \left(\frac nk\right)^k
1356 \le
1357 \binom nk
1358 \le
1359 \left(\frac{en}{k}\right)^k
1360 \label{s:eq:binomial-basic-bounds}
1361 \end{equation}
1362 show that the growth changes continuously between polynomial and exponential regimes.
1363 
1364 Because
1365 \[
1366 \binom nk=\binom n{n-k},
1367 \]
1368 write
1369 \[
1370 r(n)=\min\{k(n),n-k(n)\}.
1371 \]
1372 
1373 \begin{theorem}[Explicit fixed-charge phase diagram]
1374 \label{s:thm:charge-phase-diagram}
1375 For explicit amplitude storage in a weight-$k(n)$ packet:
1376 \begin{enumerate}
1377 \item the packet dimension is polynomial in $n$ if $r(n)=O(1)$;
1378 \item the packet dimension is superpolynomial whenever $r(n)\to\infty$;
1379 \item if $r(n)=O(\log n)$, then
1380 \[
1381 D_{n,k}=2^{O((\log n)^2)},
1382 \]
1383 so the explicit packet simulation is quasipolynomial;
1384 \item if $r(n)=O(n^\alpha)$ for a fixed $0<\alpha<1$, then
1385 \[
1386 D_{n,k}=2^{O(n^\alpha\log n)},
1387 \]
1388 which is subexponential;
1389 \item if $k(n)/n\to p\in(0,1)$, then
1390 \[
1391 \log_2 D_{n,k}
1392 =
1393 nH_2(k(n)/n)+O(\log n)
1394 =
1395 nH_2(p)+o(n),
1396 \]
1397 where $H_2$ is binary entropy, and the packet remains exponential.
1398 \end{enumerate}
1399 \end{theorem}
1400 
1401 \begin{proof}
1402 The upper bounds follow from \cref{s:eq:binomial-basic-bounds}. If $r=O(1)$, then $\binom nr=O(n^r)$. Conversely, suppose $r\to\infty$ and $r\le n/2$. If $r\le\sqrt n$, then
1403 \[
1404 \log\binom nr
1405 \ge
1406 r\log(n/r)
1407 \ge
1408 \frac r2\log n,
1409 \]
1410 whose ratio to $\log n$ diverges. If $r>\sqrt n$, then
1411 \[
1412 \log\binom nr
1413 \ge
1414 r\log2
1415 \ge
1416 \sqrt n\log2,
1417 \]
1418 which also dominates every constant multiple of $\log n$. For the final assertion, $p_n=k(n)/n$ stays in a compact subinterval of $(0,1)$. Stirling's formula gives
1419 \[
1420 \log_2\binom n{k(n)}
1421 =nH_2(p_n)-\frac12\log_2\!\bigl(2\pi n p_n(1-p_n)\bigr)+O(1/n).
1422 \]
1423 The logarithmic term is $O(\log n)$, uniformly on that subinterval. Continuity of $H_2$ gives $nH_2(p_n)=nH_2(p)+o(n)$. Replacing $p_n$ by its limit inside an $O(\log n)$ estimate would require a convergence rate, which is not assumed here.
1424 \end{proof}
1425 
1426 \begin{derivedbox}
1427 For the explicit occupation-amplitude representation, ``few particles'' means a bounded number of particles or holes. A slowly growing charge can still improve on full state-vector scaling, but it no longer guarantees membership in $P$.
1428 \end{derivedbox}
1429 
1430 \subsection{A bounded-excitation hierarchy}
1431 The union of the first $K$ weight sectors has dimension
1432 \[
1433 D_{\le K}(n)
1434 =
1435 \sum_{k=0}^{K}\binom nk.
1436 \]
1437 For fixed $K$,
1438 \[
1439 D_{\le K}(n)=O(n^K).
1440 \]
1441 If $K=O(\log n)$, the same union is quasipolynomial. This refines \cref{s:cor:bounded-excitation-collapse}: bounded symmetry breaking preserves polynomial simulation, while logarithmically growing excitation gives a controlled quasipolynomial regime.
1442 
1443 \subsection{Bosonic and fermionic analogues}
1444 For $N$ fermions in $m$ modes,
1445 \[
1446 D_{\mathrm F}(m,N)=\binom mN.
1447 \]
1448 For $N$ bosons in $m$ modes,
1449 \[
1450 D_{\mathrm B}(m,N)=\binom{m+N-1}{N}.
1451 \]
1452 The same binomial analysis gives:
1453 
1454 \begin{corollary}[Few-particle scaling]
1455 \label{s:cor:few-particle-scaling}
1456 With the number of modes as the input-size parameter:
1457 \begin{enumerate}
1458 \item fixed $N$ gives polynomial explicit-amplitude simulation;
1459 \item $N=O(\log m)$ gives quasipolynomial sector size;
1460 \item $N=O(m^\alpha)$, $0<\alpha<1$, gives subexponential sector size;
1461 \item finite-density fermionic sectors remain exponential.
1462 \end{enumerate}
1463 For bosons, the statements hold in the dilute regime with the same occupation-basis access assumptions.
1464 \end{corollary}
1465 
1466 The adjective ``polynomial'' here refers to the sector dimension and efficient gate action. It does not assert that every interacting Hamiltonian has efficiently computable matrix elements or that every compact description remains closed.
1467 
1468 \subsection{Symmetric qudits with growing local dimension}
1469 The symmetric $d$-level subspace has dimension
1470 \[
1471 S(n,d)
1472 =
1473 \binom{n+d-1}{d-1}.
1474 \]
1475 For fixed $d$, this is polynomial in $n$. If $d=d(n)$ grows, the same phase transition appears.
1476 
1477 \begin{proposition}[Growing-local-dimension boundary]
1478 \label{s:prop:growing-d-boundary}
1479 In the explicit occupation basis:
1480 \begin{enumerate}
1481 \item fixed $d$ gives $S(n,d)=O(n^{d-1})$;
1482 \item $d=O(\log n)$ gives $S(n,d)=2^{O((\log n)^2)}$;
1483 \item unbounded $d$ is not covered by the fixed-$d$ polynomial-collapse theorem without an additional internal compression.
1484 \end{enumerate}
1485 \end{proposition}
1486 
1487 Thus permutation symmetry removes the exponential tensor-product multiplicity only when the number of local levels is controlled, or when the occupation record itself admits a second compression.
1488 
1489 \begin{figure}[H]
1490 \centering
1491 \includegraphics[width=.94\textwidth]{assets/s_particle_scaling_phases.pdf}
1492 \caption{The active dimension passes through polynomial, quasipolynomial, subexponential, and exponential regimes as particle number grows.}
1493 \end{figure}
1494 
1495 \subsection{Complexity class versus practical runtime}
1496 A polynomial sector can still have a large exponent. Fixed $k=20$ gives $O(n^{20})$ explicit amplitudes, which is in $P$ but may be impractical. Conversely, a subexponential sector may be useful at moderate size without changing the formal complexity class.
1497 
1498 A complete performance claim should therefore report both:
1499 \[
1500 \text{asymptotic class}
1501 \qquad\text{and}\qquad
1502 \text{actual representation size and update cost}.
1503 \]
1504 This is why the benchmark chapters keep wall-clock evidence separate from the dimension theorems.
1505 
1506 \section{Stabilizer syndromes and Clifford packets}
1507 \label{s:ch:stabilizer}
1508 \index{stabilizer}
1509 \index{Clifford circuit}
1510 
1511 \subsection{Syndrome projectors}
1512 Let $S_1,\ldots,S_m$ be commuting Pauli stabilizers with eigenvalues $\pm1$. A syndrome $s\in\{0,1\}^m$ defines
1513 \[
1514 P_s
1515 =
1516 \prod_{j=1}^m
1517 \frac{I+(-1)^{s_j}S_j}{2}.
1518 \]
1519 These projectors are orthogonal and sum to the identity. Syndrome measurement selects one packet, while recovery applies a syndrome-dependent transfer toward the code packet.
1520 
1521 \subsection{The syndrome label is not the logical state}
1522 If the code encodes $k$ logical qubits, a fixed syndrome packet can have dimension $2^k$. The syndrome has only $m$ bits, but arbitrary logical information remains inside the packet. Syndrome packetization therefore does not by itself prove efficient simulation.
1523 
1524 \subsection{Tableau compression}
1525 Clifford circuits provide a different route. A stabilizer state may occupy exponentially many computational-basis strings, yet it is represented by a polynomial-size stabilizer tableau. Clifford gates update the tableau in polynomial time, and Pauli measurements are efficiently computable. This is an example of the compressed-packet theorem rather than a small-dimensional packet theorem.
1526 
1527 \begin{derivedbox}
1528 Packet labels and internal encoding are complementary. A Clifford circuit restricted to selected syndromes may be simulated by a tableau augmented with the active syndrome graph, even when the packet dimensions are exponential.
1529 \end{derivedbox}
1530 
1531 \subsection{Non-Clifford residues}
1532 A few non-Clifford gates can be handled by stabilizer decompositions, quasiprobability expansions, or magic-state rank methods. The cost grows with a non-Clifford resource such as stabilizer rank or robustness. Symmetry packets may reduce the number of relevant branches, but they do not eliminate the intrinsic cost of the non-Clifford residue.
1533 
1534 \subsection{Error-correction interpretation}
1535 The packet view separates three objects:
1536 \[
1537 \text{syndrome label},
1538 \qquad
1539 \text{logical state},
1540 \qquad
1541 \text{recovery transfer}.
1542 \]
1543 This separation is useful for compressed simulation of fault-tolerant protocols, but a full complexity statement must include repeated measurements, classical control, and the size of the logical state.
1544 
1545 \section{Gaussian, fermionic, and matchgate compression}
1546 \label{s:ch:gaussian}
1547 \index{Gaussian circuit}
1548 \index{matchgate}
1549 
1550 \subsection{Polynomial covariance representations}
1551 Gaussian bosonic and fermionic states are specified by first and second moments rather than by all Fock-basis amplitudes. A bosonic covariance matrix has size polynomial in the number of modes, and a fermionic Gaussian state is represented by an antisymmetric Majorana covariance matrix. Gaussian unitaries act by symplectic or orthogonal transformations:
1552 \[
1553 \Gamma\longmapsto S\Gamma S^T
1554 \quad\text{or}\quad
1555 \Gamma\longmapsto O\Gamma O^T.
1556 \]
1557 This is a compact internal encoding even when the corresponding Hilbert-space packet is exponentially large.
1558 
1559 \subsection{Hybrid symmetry and Gaussianity}
1560 Number conservation, parity, translation symmetry, and point-group symmetry can further block the covariance matrices. A simulator can therefore combine two reductions:
1561 \[
1562 \text{symmetry packetization}
1563 +
1564 \text{Gaussian internal encoding}.
1565 \]
1566 The first removes unreachable sectors. The second compresses states within the remaining sectors.
1567 
1568 \subsection{Matchgate circuits}
1569 Nearest-neighbor matchgate circuits have polynomial classical representations through fermionic Gaussian dynamics. Geometry matters: adding SWAP, fermionic SWAP, long-range gates, or a non-matchgate resource changes the simulation problem. A symmetry-collapse atlas should therefore record the gate library and connectivity as part of the model, not as implementation details.
1570 
1571 \subsection{Low-rank non-Gaussian corrections}
1572 One research direction is to represent a weakly non-Gaussian state as
1573 \[
1574 \rho
1575 =
1576 \sum_{a=1}^R c_a\rho_a^{\rm Gauss}
1577 \]
1578 with small Gaussian rank $R$, or as a Gaussian reference plus sparse packet corrections. A polynomial collapse requires $R$ and the update cost to remain polynomial.
1579 
1580 \begin{frontierbox}
1581 Gaussianity is an internal representation class, not a symmetry projector. A complete hybrid theorem must prove closure of the chosen compressed class under every allowed gate and bound the growth of any non-Gaussian residue.
1582 \end{frontierbox}
1583 
1584 \subsection{Few-particle versus Gaussian routes}
1585 Fixed-particle simulation and Gaussian simulation are independent. A fixed two-fermion state may be non-Gaussian but live in a polynomial-dimensional sector. A half-filled Gaussian state may live in an exponential number sector but have a polynomial covariance description. The two-axis model in \cref{s:ch:compressed-packets} is designed to capture this distinction.
1586 
1587 \chapter{States, measurements, and open dynamics}
1588 \section{Density operators: populations and coherences}
1589 \label{s:ch:density}
1590 \index{density operator}
1591 \index{coherence}
1592 
1593 \subsection{Two packet indices}
1594 A pure state uses one packet label. A density operator uses two:
1595 \[
1596 \rho
1597 =
1598 \sum_{\alpha,\beta}
1599 P_\alpha\rho P_\beta.
1600 \]
1601 The diagonal block $P_\alpha\rho P_\alpha$ is population inside packet $\alpha$. The off-diagonal block $P_\alpha\rho P_\beta$ is coherence between packets $\alpha$ and $\beta$.
1602 
1603 Discarding off-diagonal blocks is not merely a change of coordinates. It is a physical operation such as dephasing. An exact simulator must preserve all coherence blocks relevant to the final observable.
1604 
1605 \subsection{Hilbert--Schmidt decomposition}
1606 Orthogonality of the left-right operator packets gives
1607 \[
1608 \|\rho\|_2^2
1609 =
1610 \sum_{\alpha,\beta}
1611 \|P_\alpha\rho P_\beta\|_2^2.
1612 \]
1613 This identity supplies an exact coherence-energy ledger. It can be used to decide which blocks are large, to audit dephasing, or to bound truncation errors in approximate packet simulations.
1614 
1615 \subsection{Symmetry-preserving unitary dynamics}
1616 If $U$ commutes with every packet projector, then
1617 \[
1618 P_\alpha U\rho U^\dagger P_\beta
1619 =
1620 U(P_\alpha\rho P_\beta)U^\dagger.
1621 \]
1622 The left and right packet labels are preserved. Populations and coherences evolve independently by their declared labels.
1623 
1624 \subsection{Observable sparsity}
1625 For an observable $M$,
1626 \[
1627 \Tr(M\rho)
1628 =
1629 \sum_{\alpha,\beta}
1630 \Tr(P_\beta M P_\alpha\,P_\alpha\rho P_\beta).
1631 \]
1632 Only operator packets coupled by $M$ contribute. A measurement that is diagonal in the symmetry labels depends only on populations. A phase-sensitive measurement can require off-diagonal coherences.
1633 
1634 \begin{figure}[H]
1635 \centering
1636 \includegraphics[width=.78\textwidth]{assets/s_channel_blocks.pdf}
1637 \caption{State operators carry two packet indices, while channels act between pairs of packet labels.}
1638 \end{figure}
1639 
1640 \subsection{Polynomial operator-space collapse}
1641 If only polynomially many density blocks are reachable and every block has a polynomial representation, then mixed-state evolution can also be simulated in polynomial time. The representation size is not the square of the full Hilbert dimension. It is the total cost of the active left-right blocks.
1642 
1643 \begin{derivedbox}
1644 For a polynomial active set $A_n$ of packet labels, a density-matrix simulator has at most $|A_n|^2$ label pairs. Polynomial-time simulation follows when each active coherence block has a polynomial classical representation and channel updates remain sparse and efficient.
1645 \end{derivedbox}
1646 
1647 \section{Channels, Kraus maps, and Lindblad generators}
1648 \label{s:ch:channels}
1649 \index{quantum channel}
1650 \index{Lindblad equation}
1651 
1652 \subsection{Four-index transfer}
1653 A quantum channel with Kraus operators $K_\mu$ acts by
1654 \[
1655 \Phi(\rho)
1656 =
1657 \sum_\mu K_\mu\rho K_\mu^\dagger.
1658 \]
1659 Relative to operator packets
1660 \[
1661 \mathcal P_{\alpha\beta}(X)
1662 =
1663 P_\alpha X P_\beta,
1664 \]
1665 the channel has blocks
1666 \[
1667 \Phi_{\gamma\delta,\alpha\beta}
1668 =
1669 \mathcal P_{\gamma\delta}
1670 \,\Phi\,
1671 \mathcal P_{\alpha\beta}.
1672 \]
1673 Thus a channel carries four packet labels: an input coherence pair and an output coherence pair.
1674 
1675 \subsection{Symmetry-preserving channels}
1676 If every Kraus operator commutes with the symmetry action, the channel is diagonal in the isotypic labels. More generally, Kraus operators may carry definite charges, producing a sparse selection rule. Amplitude damping transfers population between number sectors. Dephasing damps selected off-diagonal blocks. Particle loss moves weight-$k$ population to weight $k-1$.
1677 
1678 \subsection{Lindblad dynamics}
1679 A Markovian open system obeys
1680 \[
1681 \frac{d\rho}{dt}
1682 =
1683 \mathcal L(\rho)
1684 =
1685 -i[H,\rho]
1686 +
1687 \sum_a
1688 \left(
1689 L_a\rho L_a^\dagger
1690 -
1691 \frac12\{L_a^\dagger L_a,\rho\}
1692 \right).
1693 \]
1694 Packet selection rules of $H$ and $L_a$ determine a sparse directed graph on coherence pairs. If the reachable graph and each block representation remain polynomial, a classical integrator can evolve the reduced system.
1695 
1696 \subsection{Error accounting for truncated channels}
1697 Let $\Pi_A$ project operator space onto an active set of coherence blocks. A reduced evolution uses
1698 \[
1699 \mathcal L_A
1700 =
1701 \Pi_A\mathcal L\Pi_A.
1702 \]
1703 The discarded transfer is
1704 \[
1705 (I-\Pi_A)\mathcal L\Pi_A.
1706 \]
1707 Duhamel's formula yields an error bound analogous to the Hamiltonian leakage theorem. The resulting estimate depends on the induced norm of the discarded superoperator transfer and the integration time.
1708 
1709 \subsection{Syndrome-conditioned recovery}
1710 Error correction naturally fits the four-index model. Syndrome measurement selects a population packet, classical processing chooses a recovery, and the recovery transfers the state toward the code packet. A full simulation must still retain the logical state inside each syndrome sector.
1711 
1712 \begin{frontierbox}
1713 A useful open-system collapse theorem should state the norm, time horizon, packet-discovery algorithm, integration precision, and growth of reachable coherence pairs. Sparsity of a displayed block matrix is not enough by itself.
1714 \end{frontierbox}
1715 
1716 \section{Measurement, conditioning, and classical feedback}
1717 \label{s:ch:measurement}
1718 \index{measurement}
1719 
1720 \subsection{Projective measurement}
1721 For projectors $\{P_\alpha\}$, the probability of outcome $\alpha$ is
1722 \[
1723 p_\alpha
1724 =
1725 \Tr(P_\alpha\rho),
1726 \]
1727 and the conditioned state is
1728 \[
1729 \rho_\alpha
1730 =
1731 \frac{P_\alpha\rho P_\alpha}{p_\alpha}
1732 \]
1733 when $p_\alpha>0$. Measurement is therefore packet selection followed by normalization.
1734 
1735 \subsection{Branching complexity}
1736 A measurement-assisted circuit produces a tree of outcomes. Classical simulation is efficient when the branch distribution can be sampled or summed without enumerating exponentially many relevant histories. Symmetry can merge histories that lead to the same packet state, but only if the feedforward policy respects the same equivalence.
1737 
1738 \subsection{Dynamic programming on packet states}
1739 Suppose each branch is represented by a pair $(\alpha,r)$, where $\alpha$ is a packet label and $r$ is a compact internal state. If polynomially many distinct pairs occur at every depth, identical pairs can be merged and their probabilities added. This gives a dynamic program instead of an exponential branch tree.
1740 
1741 \begin{proposition}[Branch-merging simulation]
1742 Suppose a measurement-and-feedback circuit has polynomial depth and polynomially many distinct reachable packet representations at each step. Assume that the initial representation is efficiently constructible, each representation has a polynomial-time canonical key sufficient for all future transitions, all successor representations and their transition probabilities can be enumerated in polynomial time, and the final predicate is efficient. Then the final acceptance probability is classically computable to the requested polynomial precision in polynomial time. The same conclusion holds for any polynomially supported final output distribution.
1743 \end{proposition}
1744 
1745 \begin{proof}
1746 Maintain a probability dictionary over distinct packet representations. Each measurement or controlled gate updates every entry into polynomially many successors. Merge equal successors. The dictionary remains polynomial by hypothesis.
1747 \end{proof}
1748 
1749 \subsection{Reset and dissipation}
1750 Reset is nonunitary but often simplifies a classical representation by removing entropy or closing branches. Conversely, measurement may expose a classical label while leaving a complex logical state. The resource value of measurement depends on the target, ancilla convention, and cost function.
1751 
1752 \subsection{Connection to catalytic gate models}
1753 The larger gate-set monograph studies temporary excursions into measurement, ancilla, or symmetry-breaking resources. The present monograph asks a different question: when does the resulting model remain classically simulable? A temporary resource may shorten a quantum circuit without making the computation classically easy.
1754 
1755 \section{Block encodings and polynomial operator transforms}
1756 \label{s:ch:block-encodings}
1757 \index{block encoding}
1758 
1759 \subsection{Projector block form}
1760 A block encoding places a generally nonunitary operator $A$ inside a larger unitary $U$ so that
1761 \[
1762 (\bra0\otimes I)
1763 U
1764 (\ket0\otimes I)
1765 =
1766 \frac{A}{\alpha}.
1767 \]
1768 With
1769 \[
1770 P_0=\ket0\bra0\otimes I,
1771 \]
1772 this is the selected block
1773 \[
1774 P_0UP_0
1775 =
1776 \frac{A}{\alpha}
1777 \]
1778 after identifying the encoded subspace.
1779 
1780 \subsection{Structural connection}
1781 The encoded operator is literally a projector block of a unitary. Polynomial transformations of singular values can be implemented by controlled phase sequences once the block encoding and access model are available. This makes block encodings a natural part of a projector calculus.
1782 
1783 \subsection{Why block encoding does not imply classical simulation}
1784 A block encoding can be efficient on a quantum computer because $U$ is supplied by an oracle or a succinct circuit. A classical algorithm may not have efficient access to the entries of $A$, to the block state, or to the polynomial transform. The selected block may still have exponential dimension.
1785 
1786 \begin{scopebox}
1787 The statement ``$A$ is a block of $U$'' is structural. A classical collapse requires a polynomial classical description of the active encoded state, efficient application of the selected block, and efficient evaluation of the output.
1788 \end{scopebox}
1789 
1790 \subsection{Symmetry-resolved block encodings}
1791 If $A$ commutes with a symmetry group, both the encoded system and the ancilla can be decomposed into packets. A symmetry-resolved block encoding may reduce normalization, memory, or simulation cost for selected sectors. The relevant objects are
1792 \[
1793 P_\chi P_0 U P_0P_\psi.
1794 \]
1795 Exact symmetry removes off-diagonal $\chi\neq\psi$ blocks. Approximate symmetry yields leakage terms that must be included in the error budget.
1796 
1797 \subsection{Research direction}
1798 A useful classical theorem would identify access models in which the active block has polynomial packet dimension or a compact internal representation. This could cover structured sparse matrices, low-rank updates, association-scheme operators, and fixed-particle Hamiltonians.
1799 
1800 \chapter{The complexity boundary}
1801 \section{Compressed packet simulation}
1802 \label{s:ch:compressed-packets}
1803 \index{compressed representation}
1804 
1805 \subsection{Beyond packet dimension}
1806 The small-packet theorem stores one amplitude per packet-basis state. This is not the only classical representation. A state in an exponentially large packet may lie on a polynomially parameterized manifold. Stabilizer states, Gaussian states, matrix-product states of bounded bond dimension, and low-rank operator states are standard examples of compact internal encodings.
1807 
1808 Let $\mathcal R_n$ be a class of classical descriptions, and let
1809 \[
1810 \operatorname{decode}:\mathcal R_n\to P_n\Hh_n
1811 \]
1812 associate a quantum state with each description.
1813 
1814 \begin{theorem}[Compressed-packet simulation]
1815 \label{s:thm:compressed-packet}
1816 A polynomial-time uniform quantum circuit family lies in $P$ if there is a polynomial-size classical representation satisfying:
1817 
1818 \begin{enumerate}
1819 \item the initial state has an efficiently constructible description $r_0\in\mathcal R_n$;
1820 \item every gate induces a polynomial-time update $r\mapsto T_j(r)$ with
1821 \[
1822 \operatorname{decode}(T_j(r))
1823 =
1824 G_j\operatorname{decode}(r);
1825 \]
1826 \item all intermediate description sizes remain polynomial;
1827 \item the acceptance probability is computable from the final description in polynomial time.
1828 \end{enumerate}
1829 \end{theorem}
1830 
1831 \begin{proof}
1832 Iterate the polynomial-time classical updates on the polynomial-size descriptions and evaluate the final measurement. The algorithm never reconstructs the full state vector.
1833 \end{proof}
1834 
1835 \subsection{Two-axis complexity}
1836 The records suggest the pair
1837 \[
1838 (D_{\rm packet},\chi_{\rm internal}),
1839 \]
1840 where $D_{\rm packet}$ measures active packet size or count and $\chi_{\rm internal}$ measures the representation cost inside the packet. Efficient simulation may follow from either coordinate:
1841 
1842 \begin{itemize}
1843 \item fixed weight has polynomial $D_{\rm packet}$ and can use explicit amplitudes;
1844 \item stabilizer states may have exponential support but polynomial $\chi_{\rm internal}$;
1845 \item Gaussian states may occupy large number sectors but have polynomial covariance descriptions;
1846 \item half-filled generic states may have both coordinates exponential.
1847 \end{itemize}
1848 
1849 \begin{figure}[H]
1850 \centering
1851 \includegraphics[width=.72\textwidth]{assets/s_two_axis_complexity.pdf}
1852 \caption{Packet dimension and internal representation cost are independent classical resources.}
1853 \end{figure}
1854 
1855 \subsection{Hybrid transfer graphs}
1856 Suppose packets are nodes of a sparse graph and each node carries an internal representation. A gate may update a node internally or transfer a compact component to neighboring nodes. The simulation cost depends on
1857 \[
1858 \sum_{\alpha\in A_t}\operatorname{size}(r_\alpha)
1859 +
1860 \#\{\text{nonzero transfers at time }t\}.
1861 \]
1862 This model combines symmetry selection rules with compact state classes.
1863 
1864 \subsection{Closure is the decisive condition}
1865 A compact representation may be destroyed by one gate. Clifford tableaux fail under generic non-Clifford rotations. Gaussian covariance matrices fail under generic non-Gaussian operations. Low-bond tensor networks may acquire exponential bond dimension. The theorem therefore requires closure or a proved polynomial growth bound, not merely a compact initial state.
1866 
1867 \begin{principle}[Representation growth audit]
1868 The correct complexity variable is the maximum representation size reached along the computation, not the size of the initial or final state alone.
1869 \end{principle}
1870 
1871 \section{Global interference and the failure of local packet collapse}
1872 \label{s:ch:global-interference}
1873 \index{Forrelation}
1874 \index{interference}
1875 
1876 \subsection{A different quantum mechanism}
1877 Invariant-packet reduction succeeds when large parts of Hilbert space are never occupied or can be compressed locally. A different regime stores the answer in coherent relations among many paths. The individual amplitudes may be simple, while their signed sum is the computational object.
1878 
1879 \subsection{Forrelation amplitude}
1880 Let $f,g:\{0,1\}^n\to\{-1,1\}$ and $N=2^n$. The circuit with alternating Hadamards and phase oracles has zero-state amplitude
1881 \begin{equation}
1882 \Phi(f,g)
1883 =
1884 \frac1{N^{3/2}}
1885 \sum_{x,y}
1886  f(x)(-1)^{x\cdot y}g(y).
1887 \label{s:eq:forrelation}
1888 \end{equation}
1889 The circuit does not evaluate the $N^2$ terms separately. It preserves phases and lets them interfere.
1890 
1891 \begin{figure}[H]
1892 \centering
1893 \includegraphics[width=.90\textwidth]{assets/s_forrelation_interference.pdf}
1894 \caption{Forrelation is governed by coherent Fourier transfer rather than a small invariant sector.}
1895 \end{figure}
1896 
1897 \subsection{Why Fourier structure is not automatically easy}
1898 The Walsh transform is explicit and highly symmetric. That does not imply that the bilinear expression in \cref{s:eq:forrelation} is classically polynomial-time computable when $f$ and $g$ are supplied through restricted query access. The difficulty lies in the access model and the coherent global relation, not in the absence of algebraic structure.
1899 
1900 \subsection{Truth tables versus succinct access}
1901 If the complete truth tables of $f$ and $g$ are part of the classical input, their length is already $N$, and an $O(N\log N)$ Walsh transform is polynomial in the explicit input length. In a query or succinct-circuit model, $n$ is the parameter and $N=2^n$. The same formula then represents exponentially many values.
1902 
1903 This distinction illustrates a general rule: complexity statements must be measured against the input encoding. A quotient of exponential dimension may be efficient relative to an explicit matrix input but exponential relative to a succinct circuit input.
1904 
1905 \subsection{Cross-packet coherence}
1906 Suppose a projector family gives many packets $P_\alpha$. Even if each diagonal block is simple, the output can depend on the phases of
1907 \[
1908 P_\alpha\ket\psi
1909 \quad\text{relative to}\quad
1910 P_\beta\ket\psi
1911 \]
1912 for exponentially many pairs. A simulator that retains only populations
1913 \[
1914 \|P_\alpha\ket\psi\|^2
1915 \]
1916 loses this information. The hard-side invariant must measure classical compression of coherent relations, not merely active dimension.
1917 
1918 \begin{frontierbox}
1919 A representation-independent lower bound on interference compression for an explicit, succinct, uniform circuit family would be a major complexity result. The packet framework states the missing object but does not provide that lower bound.
1920 \end{frontierbox}
1921 
1922 \section{Simulation complexity versus decision complexity}
1923 \label{s:ch:decision-complexity}
1924 
1925 \subsection{Why simulator lower bounds are insufficient}
1926 Showing that a circuit defeats one simulation strategy does not prove that its decision problem is outside $P$. A classical algorithm may compute the answer without reconstructing the quantum state. It is therefore insufficient to rule out only:
1927 
1928 \begin{itemize}
1929 \item full state-vector simulation,
1930 \item one projector family,
1931 \item bounded-width tensor-network contraction,
1932 \item path sampling,
1933 \item low-rank transfer matrices,
1934 \item stabilizer decompositions,
1935 \item any fixed catalogue of known simulators.
1936 \end{itemize}
1937 
1938 A proof of $P\neq BQP$ would need a lower bound against every deterministic polynomial-time classical algorithm for an explicit language.
1939 
1940 \subsection{A representation-relative invariant}
1941 For a declared classical representation class $\mathcal R$, define
1942 \[
1943 \operatorname{TC}^{\mathcal R}_\varepsilon(C)
1944 =
1945 \min\left\{
1946 \operatorname{cost}(R):
1947 R\in\mathcal R,
1948 \ |R(C)-p_C|\le\varepsilon
1949 \right\},
1950 \]
1951 where $p_C$ is the target acceptance probability. This permits a disciplined ladder:
1952 
1953 \begin{enumerate}
1954 \item exact polynomial-packet simulation for easy sectors;
1955 \item lower bounds for local packet-query methods;
1956 \item lower bounds for broader tensor, sampling, low-degree, and communication representations;
1957 \item a representation-independent lower bound;
1958 \item a separation of $P$ and $BQP$.
1959 \end{enumerate}
1960 
1961 Only the first step is completed here.
1962 
1963 \subsection{Universal packetization and its consequence}
1964 Consider the statement:
1965 
1966 \begin{conjecture}[Universal polynomial packetization]
1967 Every polynomial-time uniform quantum circuit family admits an efficiently discoverable exact or approximate packet representation of polynomial active size and polynomial transfer complexity, sufficient to compute its acceptance probability.
1968 \end{conjecture}
1969 
1970 If true, \cref{s:thm:poly-packet,s:thm:compressed-packet} would imply $BQP\subseteq P$, and hence $P=BQP$. The records do not establish this conjecture and explicitly identify global interference as an obstacle.
1971 
1972 \subsection{The opposite route}
1973 An explicit uniform family with a proved representation-independent classical lower bound and a polynomial quantum algorithm would establish $P\neq BQP$. The candidate succinct transfer-interference problem in the records illustrates the form of such a target, but the required lower bound is the unresolved theorem itself.
1974 
1975 \begin{scopebox}
1976 This monograph proves polynomial classical simulation for declared subclasses. It neither proves nor assumes a universal collapse of quantum computation.
1977 \end{scopebox}
1978 
1979 \subsection{Nonrelativizing issues}
1980 Oracle separations show that query complexity can distinguish quantum and classical access. They also show why a black-box argument alone cannot settle ordinary $P$ versus $BQP$. A full separation would have to use explicit features such as uniform circuit generation, arithmetic structure, algebraic degree, communication constraints, or another nonrelativizing mechanism.
1981 
1982 \section{Existence defects and quantum combinatorial realizations}
1983 \label{s:ch:existence-defects}
1984 
1985 \subsection{Metric collapse and existence collapse}
1986 The simulation theorems compare costs of two realizations that both exist. A broader restricted-realization framework also allows the restricted object to be absent. If
1987 \[
1988 \mathcal R(x)=\varnothing,
1989 \qquad
1990 \mathcal A(x)\neq\varnothing,
1991 \]
1992 then enlarging the realization category changes feasibility rather than merely runtime.
1993 
1994 \subsection{Quantum Latin-square example}
1995 The order-six quantum-Latin-square record supplies an existence-level example. Entangled quantum Latin squares of order six exist, while mutually orthogonal non-entangled quantum Latin squares of order six do not. This is an ambient-versus-restricted realization gap, not a proof of classical simulation and not a gate-count shortcut.
1996 
1997 The proof architecture uses support patterns, unitary-pattern constraints, graph orthonormal representations, projective-line closure, dimension contradictions, and a finite reduction to twelve classical Latin-square classes. Its conceptual relevance here is limited but useful: enlarging the allowed quantum resource can change whether a structure exists at all.
1998 
1999 \subsection{Why this does not imply computational advantage}
2000 Existence of an entangled combinatorial design does not by itself provide an algorithmic speedup. One must still specify an input problem, circuit family, output rule, and classical comparison. Likewise, nonexistence of a product realization does not prove classical hardness of the entangled realization.
2001 
2002 \begin{scopebox}
2003 The quantum Latin-square result is included as a contextual example of restricted-realization failure. It is not used as a premise in any packet-simulation theorem.
2004 \end{scopebox}
2005 
2006 \subsection{Unified terminology}
2007 For a target $x$, let $c_{\rm res}(x)$ and $c_{\rm amb}(x)$ be minimum costs, with $+\infty$ assigned when a realization does not exist. Then
2008 \[
2009 \Delta(x)
2010 =
2011 c_{\rm res}(x)-c_{\rm amb}(x)
2012 \]
2013 includes both finite metric defects and infinite existence defects. Symmetry collapse concerns the special case where the ambient quantum description has a cheaper classical realization because its reachable representation is compressed.
2014 
2015 \chapter{Algorithms and open directions}
2016 \section{Architecture of a symmetry-collapse compiler}
2017 \label{s:ch:compiler}
2018 \index{compiler}
2019 
2020 \subsection{The five-stage pipeline}
2021 A practical compiler must perform more than symbolic block diagonalization.
2022 
2023 \begin{enumerate}
2024 \item Detect exact or approximate symmetries.
2025 \item Construct an invariant basis, orbit quotient, or compact internal representation.
2026 \item Compile each gate into that representation.
2027 \item Track leakage, truncation, and numerical error.
2028 \item Evaluate the requested measurement and emit a complexity certificate.
2029 \end{enumerate}
2030 
2031 \begin{figure}[H]
2032 \centering
2033 \includegraphics[width=.94\textwidth]{assets/s_compiler_pipeline.pdf}
2034 \caption{A symmetry-collapse compiler and its required certificate.}
2035 \end{figure}
2036 
2037 \subsection{Symmetry detection}
2038 Detection may use declared conserved quantities, commutators, finite-group generators, graph automorphisms, stabilizer relations, occupation conservation, or numerical approximate symmetries. Exact symbolic detection is preferable when available. Numerical detection must specify tolerances and how they propagate.
2039 
2040 \subsection{Basis construction}
2041 Examples include:
2042 
2043 \begin{itemize}
2044 \item subset indexing for fixed weight,
2045 \item occupation vectors for bosons,
2046 \item Dicke states for full permutation symmetry,
2047 \item Schur coordinates for broader permutation symmetry,
2048 \item orbit states for graph walks,
2049 \item stabilizer tableaux,
2050 \item fermionic or bosonic covariance matrices,
2051 \item matrix-product states for bounded entanglement.
2052 \end{itemize}
2053 
2054 The compiler should avoid materializing an exponentially large change-of-basis matrix. It needs direct indexing and update formulas.
2055 
2056 \subsection{Gate plan caching}
2057 For a repeated circuit family, compile a packet plan containing affected index pairs, sparse matrix blocks, phase tables, and quotient couplings. The plan can be reused across parameter values when the sparsity pattern is fixed.
2058 
2059 \subsection{Fallback and adaptive enlargement}
2060 If a gate leaks from the current representation, the compiler can reject the reduction, merge packets, add neighboring sectors, or switch internal representations. The choice must preserve a certified error budget.
2061 
2062 \subsection{Output certificate}
2063 A useful machine-readable certificate should include:
2064 
2065 \begin{itemize}
2066 \item the symmetry or invariant-subspace proof,
2067 \item active dimensions or representation sizes,
2068 \item gate update complexity,
2069 \item leakage or approximation bounds,
2070 \item measurement complexity,
2071 \item benchmark and hardware metadata,
2072 \item the final complexity conclusion and its scope.
2073 \end{itemize}
2074 
2075 \section{Benchmark and validation protocol}
2076 \label{s:ch:benchmark-protocol}
2077 
2078 \subsection{Fair comparison}
2079 A packet simulator and a full simulator should use the same precision, gate parameters, initial state, observable, and arithmetic path wherever possible. Report compilation separately from repeated application.
2080 
2081 \subsection{Required metrics}
2082 A complete benchmark should report:
2083 
2084 \begin{enumerate}
2085 \item full and reduced dimensions,
2086 \item packet-discovery and compilation time,
2087 \item one-shot runtime,
2088 \item repeated-application runtime,
2089 \item peak memory,
2090 \item reconstruction or observable error,
2091 \item symmetry leakage,
2092 \item hardware and software versions,
2093 \item number of repetitions over which compilation is amortized.
2094 \end{enumerate}
2095 
2096 \subsection{Algebraic and numerical validation paths}
2097 For manageable $n$, embed a random packet state into the full space, apply identical gates in both representations, and compare final states. The included numerical validation program performs this check for structurally invariant fixed-weight circuits using complex floating-point arithmetic, with reconstruction tolerance $2\cdot10^{-12}$. The separate rational validation uses exact fractions and rational orthogonal gates. Exact subspace invariance is a property of the model, while near-machine-precision agreement is numerical evidence about this implementation.
2098 
2099 \subsection{Scaling studies}
2100 A scaling plot should include both fine packets and coarse packets. Fixed weight two demonstrates polynomial dimension. Parity demonstrates a constant-factor packet. Half filling demonstrates an exponential packet with a polynomial memory reduction factor. These controls prevent overinterpreting a speedup as a complexity collapse.
2101 
2102 \subsection{Leakage tests}
2103 Deliberately append a gate that breaks the proposed symmetry and verify that the simulator detects nonzero leakage. The archived tests break exact weight, parity, and weight modulo four, producing retained probabilities below one. A simulator that reports zero error after a symmetry-breaking gate without enlarging its representation is incorrect.
2104 
2105 \subsection{Reproducibility contract}
2106 The release preserves:
2107 
2108 \begin{itemize}
2109 \item the benchmark JSON data,
2110 \item the Python figure generator,
2111 \item packet and gate utilities,
2112 \item exact rational checks and separately labeled numerical validation tests,
2113 \item LaTeX source,
2114 \item deterministic build commands,
2115 \item checksums of final artifacts.
2116 \end{itemize}
2117 
2118 \begin{recordbox}
2119 The release validation reproduces fixed-weight basis dimensions, residue partitions, symmetric/bosonic/fermionic dimension formulas, hypercube quotient symmetry, and full-vs-packet state reconstruction near machine precision.
2120 \end{recordbox}
2121 
2122 \section{Atlas of candidate symmetry collapses}
2123 \label{s:ch:atlas}
2124 
2125 \begin{figure}[H]
2126 \centering
2127 \includegraphics[width=.94\textwidth]{assets/s_research_atlas.pdf}
2128 \caption{The main theorem and implementation directions organized around one certified compiler.}
2129 \end{figure}
2130 
2131 \subsection{High-confidence theorem families}
2132 \begin{longtable}{@{}L{.25\textwidth}L{.33\textwidth}L{.32\textwidth}@{}}
2133 \caption{High-priority collapse families.}\\
2134 \toprule
2135 Family & Compression mechanism & Decisive condition\\
2136 \midrule
2137 \endfirsthead
2138 \toprule
2139 Family & Compression mechanism & Decisive condition\\
2140 \midrule
2141 \endhead
2142 Fixed charge $k=O(1)$ & Explicit subset basis of size $\binom nk$ & Number-preserving gates and efficient measurement\\
2143 Permutation-symmetric qubits & Dicke basis of size $n+1$ & Collective or permutation-invariant dynamics\\
2144 Symmetric qudits, fixed $d$ & Occupation basis $\binom{n+d-1}{d-1}$ & Efficient occupation-space updates\\
2145 Polynomial-orbit walks & Quotient Hamiltonian on orbit states & Succinct quotient entries and orbit-invariant input/output\\
2146 Few bosons or fermions & Fixed-particle occupation basis & Fixed particle number and efficient few-body updates\\
2147 Stabilizer circuits & Tableau representation & Clifford closure and efficient Pauli measurement\\
2148 Gaussian circuits & Covariance representation & Gaussian closure and efficient observable evaluation\\
2149 \bottomrule
2150 \end{longtable}
2151 
2152 \subsection{Hybrid theorem targets}
2153 The strongest new classes may combine several resources:
2154 
2155 \begin{itemize}
2156 \item charge packets plus Gaussian covariance,
2157 \item permutation packets plus bounded-bond tensor networks,
2158 \item stabilizer tableaux plus a small syndrome transfer graph,
2159 \item orbit quotients plus Fourier diagonalization,
2160 \item adaptive approximate packets plus rigorous leakage accounting.
2161 \end{itemize}
2162 
2163 \subsection{Negative controls}
2164 A research atlas should preserve cases that do not collapse:
2165 
2166 \begin{itemize}
2167 \item parity alone,
2168 \item weight modulo a fixed constant,
2169 \item half filling with generic internal states,
2170 \item a syndrome label with exponentially many logical qubits,
2171 \item a block encoding without classical access,
2172 \item global phase interference without a compact representation.
2173 \end{itemize}
2174 
2175 \subsection{Priority order}
2176 The recommended sequence is:
2177 
2178 {\small
2179 \begin{enumerate}[nosep,leftmargin=*,label=\arabic*.]
2180 \item implement the Dicke and orbit-quotient simulators;
2181 \item combine fixed charge with Gaussian and stabilizer encodings;
2182 \item develop adaptive leakage-certified packet growth;
2183 \item build open-system four-index packet compilers;
2184 \item search for broader representations of global interference;
2185 \item separate simulator-specific lower bounds from decision-problem lower bounds.
2186 \end{enumerate}
2187 }
2188 
2189 \section{Open problems}
2190 \label{s:ch:open-problems}
2191 
2192 \subsection{Efficient hidden-symmetry discovery}
2193 \begin{question}
2194 Which uniform circuit families have polynomial-dimensional invariant subspaces that can be discovered in polynomial time from the circuit description?
2195 \end{question}
2196 A nonconstructive invariant subspace does not yield an algorithm. The problem includes symbolic commutant computation, graph-orbit discovery, representation decomposition, and approximate invariant-subspace detection.
2197 
2198 
2199 \subsection{Moving-frame discovery}
2200 \begin{question}
2201 Which circuit families admit efficiently computable frames \(W_t\) that expose one fixed polynomial packet even though no fixed laboratory-frame symmetry is preserved?
2202 \end{question}
2203 The theorem is exact, but the discovery problem is the substance. Useful frames must have compact descriptions and restricted gate matrices that can be generated without solving the original simulation problem.
2204 
2205 \subsection{Permutation-commutant compilers}
2206 \begin{question}
2207 For which succinct permutation-invariant Hamiltonians and channels can all Schur-commutant block updates be generated in polynomial time without explicitly performing the full Schur transform?
2208 \end{question}
2209 The parameter count is polynomial for fixed local dimension. The remaining algorithmic issue is efficient block access.
2210 
2211 \subsection{Dynamic packet graphs}
2212 \begin{question}
2213 Can local selection rules guarantee polynomial growth of the reachable packet graph for polynomially long circuits with weak but repeated symmetry breaking?
2214 \end{question}
2215 Bounded excitation gives one exact theorem. Broader results may require locality, energy penalties, or cancellation of packet-transfer paths.
2216 
2217 \subsection{Minimal packet complexity}
2218 \begin{question}
2219 Given a circuit and error tolerance $\varepsilon$, what is the minimum active representation size among all efficiently applicable exact or approximate packet decompositions?
2220 \end{question}
2221 This optimization should include internal encoding and transfer sparsity, not only projector rank.
2222 
2223 \subsection{Adaptive leakage}
2224 \begin{question}
2225 Can one prove polynomial active packet growth for physically local Hamiltonians with weak symmetry breaking over polynomial time?
2226 \end{question}
2227 The commutator bound is local in time and often conservative. Stronger bounds may use energy gaps, locality, Lieb--Robinson estimates, or destructive interference among leakage channels.
2228 
2229 \subsection{Permutation and Schur compilers}
2230 \begin{question}
2231 Which noncollective but globally permutation-invariant circuit layers admit sparse Schur-basis updates without constructing the full Schur transform?
2232 \end{question}
2233 
2234 \subsection{Orbit quotients under succinct access}
2235 \begin{question}
2236 For which succinct graph families are orbit counts, orbit sizes, and quotient couplings computable in polynomial time without enumerating the graph?
2237 \end{question}
2238 
2239 \subsection{Hybrid Gaussian and packet methods}
2240 \begin{question}
2241 Can a polynomial number of non-Gaussian packet corrections be maintained on top of a Gaussian reference for broad interacting few-particle dynamics?
2242 \end{question}
2243 
2244 \subsection{Open systems}
2245 \begin{question}
2246 When does the number of reachable population and coherence blocks remain polynomial under a local Lindblad generator?
2247 \end{question}
2248 
2249 \subsection{Universal packetization}
2250 \begin{question}
2251 Is every polynomial-size quantum circuit classically compressible by some efficiently discoverable representation of polynomial size?
2252 \end{question}
2253 A positive answer would imply $P=BQP$. The record does not support this as a universal empirical principle.
2254 
2255 \subsection{Interference lower bounds}
2256 \begin{question}
2257 Can one prove an explicit representation-independent exponential lower bound for the classical cost of the coherent interference needed by a uniform BQP language?
2258 \end{question}
2259 This is the hard-side frontier. Lower bounds against one simulator family are intermediate results, not the final theorem.
2260 
2261 \begin{frontierbox}
2262 The most achievable next theorem is not a universal complexity result. It is a complete compiler theorem for one new symmetry family, with explicit discovery, update, measurement, and leakage algorithms.
2263 \end{frontierbox}
2264 
2265 \section{Conclusion}
2266 The quantum state vector is a universal coordinate system, not always the computationally intrinsic one. Conserved charges, finite-group representations, permutation orbits, few-particle sectors, and operator packets can expose much smaller dynamics. When the packet is efficiently discoverable, polynomial in size, closed under the gates, and compatible with the measurement, the quantum computation collapses exactly to a deterministic classical polynomial-time simulation.
2267 
2268 The strongest current examples are concrete. Fixed charge at constant particle number is polynomial. Exact charge conservation is not necessary: moving packet schedules, efficiently computable moving frames, and bounded unions of low-excitation sectors also collapse to polynomial classical simulation. Fully symmetric fixed-local-dimension dynamics is polynomial. A stronger mixed-state theorem compresses all permutation-invariant Schur sectors into a polynomial commutant record, with $O(n^3)$ density-matrix parameters for qubits under efficient block access. Polynomial-orbit walks are polynomial under quotient-access hypotheses. Few-particle bosonic and fermionic systems are polynomial under efficient updates, while growing particle number gives a sharp progression through quasipolynomial, subexponential, and exponential sector sizes. Stabilizer and Gaussian representations show that an exponential packet can also be easy when its internal states admit compact closed coordinates. Recorded number-conserving benchmarks show large memory and repeated-application gains with zero reconstruction error at the recorded precision.
2269 
2270 The boundaries are equally sharp. Parity, modulo-four charge, and half filling do not generally change exponential scaling. Entanglement can remain hard inside one packet. A syndrome label does not compress logical information. A block encoding does not provide a classical access model. Global Fourier interference may be fully structured yet resist small packetization. Symmetry collapse is therefore not a slogan that all quantum computation is classical. It is a theorem architecture for identifying substantial subclasses that are.
2271 
2272 The core research invariant is the complete classical representation record
2273 \[
2274 \bigl(
2275 \text{discovery cost},
2276 N_{\rm packets},
2277 D_{\rm internal},
2278 S_{\rm transfer},
2279 L_{\rm leakage},
2280 \text{measurement cost}
2281 \bigr).
2282 \]
2283 A future compiler that computes and certifies this record can decide when the full state vector is unnecessary, when a hybrid representation is preferable, and when symmetry alone is insufficient.
2284 

Back to source controls

Back to Quantum and Circuits