5.3 Measurement, conditioning, and classical feedback
On this page · Permalink · Source line 1716
5.3.1 Projective measurement
On this page · Permalink · Source line 1720
For projectors \(\{P_\alpha\}\), the probability of outcome \(\alpha\) is
and the conditioned state is
when \(p_\alpha>0\). Measurement is therefore packet selection followed by normalization.
5.3.2 Branching complexity
On this page · Permalink · Source line 1735
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.
5.3.3 Dynamic programming on packet states
On this page · Permalink · Source line 1738
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.
Proposition 5.1: Branch-merging simulation
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.
Proof
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.
5.3.4 Reset and dissipation
On this page · Permalink · Source line 1749
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.
5.3.5 Connection to catalytic gate models
On this page · Permalink · Source line 1752
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.