3.3 Uniform circuits and the classical cost model
On this page · Permalink · Source line 193
3.3.1 Circuit families
On this page · Permalink · Source line 198
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 \({\operatorname{poly}}(|x|)\) gates. Let
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.
3.3.2 The packet access model
On this page · Permalink · Source line 205
For each input length, suppose there is a packet projector \(P_n\) and a basis
of \(P_n{\mathcal H}_n\). The simulation interface has four routines.
Discovery and indexing. Produce or index \({\mathcal B}_n\) in polynomial time.
Initialization. Express the initial state in this basis.
Gate update. Apply each restricted gate \(P_nG_jP_n\) to the packet coordinates in polynomial time.
Measurement. Compute the final acceptance probability to the needed precision.
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.
3.3.3 Precision and promise gaps
On this page · Permalink · Source line 222
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.
3.3.4 State-vector cost inside a packet
On this page · Permalink · Source line 225
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
The corresponding full state-vector path is
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.
3.3.5 Reuse and amortization
On this page · Permalink · Source line 236
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.
Scope boundary
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.