Quantum Circuits with Mixed States

• Mixed-state quantum circuits with arbitrary quantum operations are polynomially equivalent in computational power to the standard unitary model.Source: §1 · p. 2
• The model naturally incorporates intermediate measurements, whose post-measurement states are mixed rather than pure.Source: §1 · pp. 2–3
• Noise and decoherence become natural non-unitary operations in the mixed-state framework.Source: §1 · pp. 2–3
• The paper defines general probabilistic subroutines for quantum superpositions and proves that they do not strengthen the model, FQP^FQP = FQP.Source: §1 · p. 3
• Density matrices provide a unique state description, while trace and diamond metrics support formal analysis of computation errors.Source: §1 · p. 4
• If a circuit uses L gates or probabilistic subroutines with at most ε error each, its computed function has at most O(Lε) error.Source: §1 · p. 4

• A mixed state is represented by a density matrix, an equivalent and generally non-unique-independent description of mixtures of pure states.Source: §2 · p. 5
• A density matrix is Hermitian, positive semidefinite, and has trace one.Source: §2 · p. 5
• Reducing a subsystem uses the partial trace, which averages over the discarded system and commutes with operations acting elsewhere.Source: §2 · p. 5
• Physically allowed quantum operations are linear, trace-preserving, completely positive maps, including unitary embeddings and partial traces.Source: §2 · pp. 5–6
• Measurements produce a classical probabilistic output and update the quantum state through projection and normalization.Source: §2 · pp. 6–7

• A quantum gate is a trace-preserving, completely positive linear map between density matrices, with standard unitary gates as a special case.Source: §3 · p. 7
• A circuit is a directed acyclic graph whose gates act on inputs, blank wires, and result outputs.Source: §3 · p. 7
• The circuit’s final density matrix is obtained by composing its gates in any topological order.Source: §3 · p. 8
• Different topological orders yield the same operation because gates acting on different qubits commute.Source: §3 · p. 8
• The circuit computes a probabilistic function by measuring its designated result outputs in the computational basis.Source: §3 · pp. 7–9

4.1 Substituting General Gates by Unitary Gates

• A general non-unitary gate can be represented by a unitary operation on 2n + m qubits whose first m qubits reproduce the gate’s output.The remaining systems are traced out after applying the unitary embedding.Source: §4.1 · p. 9
• Mixed-state quantum circuits are polynomially equivalent in computational power to the standard unitary model.General non-unitary gates can therefore be simulated efficiently using unitary gates with ancillary qubits.Source: §4.1 · p. 9

4.2 Using General Subroutines

• Probabilistic subroutines are defined as input-dependent output distributions and implemented as density-matrix operations over all compatible deterministic functions.This construction generalizes deterministic subroutines on superpositions and probabilistic subroutines on classical inputs.Source: §4.2 · pp. 9–10

lemma 5

• A probabilistic subroutine can be simulated with n + l(O(k) + O(r) + O(m)) gates from UG ∪ U†G ∪ C while preserving the computed function.The construction copies outputs, tracks residual garbage with an auxiliary control, conditionally copies inputs, and discards garbage and ancillas.Source: lemma 5 · p. 11

4.3 Simple Lower Bounds on Probabilistic Functions

• Causality implies that correlated output qubits must share an earlier gate with directed paths to both outputs.The proof uses the fact that gates acting outside a subsystem leave its reduced density matrix unchanged.Source: §4.3 · p. 13
• For fan-in at most k, a circuit computing a probabilistic function with maximum correlation degree c has depth D(Q) ≥ log_k(c).A function outputting 0^r and 1^r with equal probability therefore requires depth larger than log(r).Source: §4.3 · p. 14

5.1 The Natural Distance Between Probabilistic Functions

• The total variation distance provides the natural metric for comparing probabilistic functions.For probabilistic outputs, the distance is based on the ℓ1-norm between their output distributions.Source: §5.1 · p. 15

lemma 10

• Trace distance equals the maximum total variation distance obtainable from measuring two density matrices with any observable.This gives the trace metric an operational interpretation as measurable distinguishability.Source: lemma 10 · p. 15

5.3 The Diamond Metric on Quantum Gates

• The diamond norm is introduced because the naive super-operator norm is not stable under tensoring with an identity operator.The stabilized norm is presented as a useful tool for reasoning about quantum errors.Source: §5.3 · p. 16

lemma 12

• The diamond norm is the stabilized version of the naive trace norm and has multiplicative behavior under tensor products.The paper also states that every physically allowed super-operator has diamond norm 1.Source: §5.3 · p. 16, lemma 12 · p. 16
• For contractions V and W, the induced super-operators satisfy ∥V · V† − W · W†∥♦ ≤ 2∥V − W∥.The bound connects differences between implementations with differences between their induced quantum operations.Source: lemma 12 · p. 17

5.4 Bounding the Overall Error

• A probabilistic subroutine error of at most ǫ changes its composed super-operator by at most 5ǫ in diamond norm.This supplies the subroutine-specific bound used alongside the additive gate-error result.Source: §5.4 · p. 18
• An error of at most ǫ in each of L probabilistic subroutines and gates yields at most O(Lǫ) error in the computed function.This is the section’s overall error-accumulation theorem.Source: §5.4 · p. 19