6.3 Simulation complexity versus decision complexity
On this page · Permalink · Source line 1922
6.3.1 Why simulator lower bounds are insufficient
On this page · Permalink · Source line 1925
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:
full state-vector simulation,
one projector family,
bounded-width tensor-network contraction,
path sampling,
low-rank transfer matrices,
stabilizer decompositions,
any fixed catalogue of known simulators.
A proof of \(P\neq BQP\) would need a lower bound against every deterministic polynomial-time classical algorithm for an explicit language.
6.3.2 A representation-relative invariant
On this page · Permalink · Source line 1940
For a declared classical representation class \(\mathcal R\), define
where \(p_C\) is the target acceptance probability. This permits a disciplined ladder:
exact polynomial-packet simulation for easy sectors;
lower bounds for local packet-query methods;
lower bounds for broader tensor, sampling, low-degree, and communication representations;
a representation-independent lower bound;
a separation of \(P\) and \(BQP\).
Only the first step is completed here.
6.3.3 Universal packetization and its consequence
On this page · Permalink · Source line 1963
Consider the statement:
Conjecture 6.3: Universal polynomial packetization
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.
If true, Theorem 3.7 and Theorem 6.1 would imply \(BQP\subseteq P\), and hence \(P=BQP\). The records do not establish this conjecture and explicitly identify global interference as an obstacle.
6.3.4 The opposite route
On this page · Permalink · Source line 1972
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.
Scope boundary
This monograph proves polynomial classical simulation for declared subclasses. It neither proves nor assumes a universal collapse of quantum computation.
6.3.5 Nonrelativizing issues
On this page · Permalink · Source line 1979
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.