Global interference and the failure of local packet collapse

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.

Permalink · Source line 1877

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

The circuit does not evaluate the \(N^2\) terms separately. It preserves phases and lets them interfere.

Permalink · Source line 1880

The Walsh transform is explicit and highly symmetric. That does not imply that the bilinear expression in Equation (6.1) 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.

Permalink · Source line 1898

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.

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.

Permalink · Source line 1901

Suppose a projector family gives many packets \(P_\alpha\). Even if each diagonal block is simple, the output can depend on the phases of

for exponentially many pairs. A simulator that retains only populations

loses this information. The hard-side invariant must measure classical compression of coherent relations, not merely active dimension.

Permalink · Source line 1906