7.4 Open problems
On this page · Permalink · Source line 2189
7.4.1 Efficient hidden-symmetry discovery
On this page · Permalink · Source line 2192
Question 7.1
Which uniform circuit families have polynomial-dimensional invariant subspaces that can be discovered in polynomial time from the circuit description?
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.
7.4.2 Moving-frame discovery
On this page · Permalink · Source line 2199
Question 7.2
Which circuit families admit efficiently computable frames \(W_t\) that expose one fixed polynomial packet even though no fixed laboratory-frame symmetry is preserved?
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.
7.4.3 Permutation-commutant compilers
On this page · Permalink · Source line 2205
Question 7.3
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?
The parameter count is polynomial for fixed local dimension. The remaining algorithmic issue is efficient block access.
7.4.4 Dynamic packet graphs
On this page · Permalink · Source line 2211
Question 7.4
Can local selection rules guarantee polynomial growth of the reachable packet graph for polynomially long circuits with weak but repeated symmetry breaking?
Bounded excitation gives one exact theorem. Broader results may require locality, energy penalties, or cancellation of packet-transfer paths.
7.4.5 Minimal packet complexity
On this page · Permalink · Source line 2217
Question 7.5
Given a circuit and error tolerance \(\varepsilon\), what is the minimum active representation size among all efficiently applicable exact or approximate packet decompositions?
This optimization should include internal encoding and transfer sparsity, not only projector rank.
7.4.6 Adaptive leakage
On this page · Permalink · Source line 2223
Question 7.6
Can one prove polynomial active packet growth for physically local Hamiltonians with weak symmetry breaking over polynomial time?
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.
7.4.7 Permutation and Schur compilers
On this page · Permalink · Source line 2229
Question 7.7
Which noncollective but globally permutation-invariant circuit layers admit sparse Schur-basis updates without constructing the full Schur transform?
7.4.8 Orbit quotients under succinct access
On this page · Permalink · Source line 2234
Question 7.8
For which succinct graph families are orbit counts, orbit sizes, and quotient couplings computable in polynomial time without enumerating the graph?
7.4.9 Hybrid Gaussian and packet methods
On this page · Permalink · Source line 2239
Question 7.9
Can a polynomial number of non-Gaussian packet corrections be maintained on top of a Gaussian reference for broad interacting few-particle dynamics?
7.4.10 Open systems
On this page · Permalink · Source line 2244
Question 7.10
When does the number of reachable population and coherence blocks remain polynomial under a local Lindblad generator?
7.4.11 Universal packetization
On this page · Permalink · Source line 2249
Question 7.11
Is every polynomial-size quantum circuit classically compressible by some efficiently discoverable representation of polynomial size?
A positive answer would imply \(P=BQP\). The record does not support this as a universal empirical principle.
7.4.12 Interference lower bounds
On this page · Permalink · Source line 2255
Question 7.12
Can one prove an explicit representation-independent exponential lower bound for the classical cost of the coherent interference needed by a uniform BQP language?
This is the hard-side frontier. Lower bounds against one simulator family are intermediate results, not the final theorem.
Open program or boundary
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.