Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Preparation error need not increase purification output error

Abstract

A tight purification circuit has strictly decreasing output error between two preparation error rates.

Definition 1.1 (CNOT and Toffoli gates).

Formalization. D5/S3/Quantum/Codes/PurificationCircuitMonotonicityRefutation.Gate (✓ std3).

Citation. Ben Barber; Neil I. Gillespie; J. M. Taylor (2023). Post-selection-free preparation of high-quality physical qubits. DOI: 10.22331/q-2023-05-04-994. URL: https://arxiv.org/abs/2209.05391v3.

Commentary.

Gate n is the disjoint sum of ordered pairs of distinct qubits and ordered triples of pairwise distinct qubits. A pair specifies a CNOT control and target; a triple specifies two Toffoli controls followed by its target. Qubits n means Fin n → Bool. These are the gate types used in purification circuits (purification.tex, line 203).

Definition 1.2 (The qubits touched by a gate).

Formalization. D5/S3/Quantum/Codes/PurificationCircuitMonotonicityRefutation.gateSet (✓ std3).

Source. Repository-derived.

Acknowledgement. Ben Barber; Neil I. Gillespie; J. M. Taylor (2023). Post-selection-free preparation of high-quality physical qubits. DOI: 10.22331/q-2023-05-04-994. URL: https://arxiv.org/abs/2209.05391v3.

Commentary.

The support of a CNOT is its control and target; the support of a Toffoli is its two controls and target. Taking a finite set forgets their order while retaining exactly the qubits exposed to that gate’s depolarisation.

Definition 1.3 (Clearing all low-weight inputs).

Formalization. D5/S3/Quantum/Codes/PurificationCircuitMonotonicityRefutation.IsPurification (✓ std3).

Citation. Ben Barber; Neil I. Gillespie; J. M. Taylor (2023). Post-selection-free preparation of high-quality physical qubits. DOI: 10.22331/q-2023-05-04-994. URL: https://arxiv.org/abs/2209.05391v3.

Commentary.

A circuit purifies through weight e when every input with at most e true bits gives false at each nominated output after the ideal gates. The gates act in list order: a CNOT flips its target when its control is true, and a Toffoli flips its target when both controls are true. This is the purification condition of purification.tex, line 203; the number of nominated outputs is their finite-set cardinality.

Definition 1.4 (Expected output error under independent noise).

Formalization. D5/S3/Quantum/Codes/PurificationCircuitMonotonicityRefutation.pOut (✓ std3).

Citation. Ben Barber; Neil I. Gillespie; J. M. Taylor (2023). Post-selection-free preparation of high-quality physical qubits. DOI: 10.22331/q-2023-05-04-994. URL: https://arxiv.org/abs/2209.05391v3.

Commentary.

The initial mass is the product of independent Bernoulli masses with parameter p0. Each round first applies its ideal gate, then depolarises the gate’s support with probability pC or pT, then independently depolarises each remaining qubit with probability pI. Depolarising a set retains the old mass with weight 1 − p and adds p times the uniform average over all assignments agreeing outside that set. The final mass is summed over states true at each output and divided by the output cardinality, explicitly cast from ℕ to ℝ. This is the error model at purification.tex, lines 219–243, and the average output error at lines 711–713, specialised to one gate per round. The real-valued formula is defined for every parameter and output set; an empty output set gives zero by real division by zero.

Definition 1.5 (Coordinatewise monotonicity for tight circuits).

Formalization. D5/S3/Quantum/Codes/PurificationCircuitMonotonicityRefutation.claim (✓ std3).

Source. Repository-derived.

Acknowledgement. Ben Barber; Neil I. Gillespie; J. M. Taylor (2023). Post-selection-free preparation of high-quality physical qubits. DOI: 10.22331/q-2023-05-04-994. URL: https://arxiv.org/abs/2209.05391v3.

Commentary.

For natural n, k and e with 1 ≤ k ≤ n and 1 ≤ e ≤ n, choose any circuit and exactly k outputs. If it purifies through weight e and the binomial space bound is an equality, the assertion requires output error to be nondecreasing separately in each of p0, pI, pC and pT, holding the other three fixed. Both parameter vectors must satisfy 0 ≤ p0 < 1/2 and 0 ≤ pI, pC, pT ≤ 1. This is the nondecreasing reading of the question at purification.tex, lines 859–862, for circuits with one gate per round; the space bound and its parameter range appear at lines 265–270.

Theorem 1.6 (A six-gate circuit refutes monotonicity).

Proof. Machine-checked in Lean as D5/S3/Quantum/Codes/PurificationCircuitMonotonicityRefutation.result (✓ std3). ∎

Resolves. Problems/barber-gillespie-taylor-2023-purification-monotonicity (refuted) by D5/S3/Quantum/Codes/PurificationCircuitMonotonicityRefutation.result.

Source. Repository-derived.

Acknowledgement. Ben Barber; Neil I. Gillespie; J. M. Taylor (2023). Post-selection-free preparation of high-quality physical qubits. DOI: 10.22331/q-2023-05-04-994. URL: https://arxiv.org/abs/2209.05391v3.

Commentary.

At depolarisation probability zero, the retained mass has coefficient one and the averaged mass has coefficient zero. Thus each such operation is the identity, and folding zero-probability idle operations also leaves the distribution unchanged. There are exactly eight states on three qubits, obtained by independently choosing false or true at coordinates 0, 1 and 2.

If two distinct coordinates are true, the Hamming distance from the all-false state is at least two. Now take n = 3, k = 1, e = 1, output set {0}, and the gate list CNOT(0→1), CNOT(1→2), CNOT(1→0), CNOT(0→2), CNOT(1→0), Toffoli(1,2→0). Splitting on the three input bits gives eight cases. Direct gate evaluation makes output 0 false in the all-false case and the three cases with one true bit. Each remaining case has two distinct true coordinates, contradicting weight at most one. The circuit therefore purifies through weight one. Its space bound is tight because the two binomial coefficients are 1 and 3, with sum 4 = 2^(3−1).

Set pI = pT = 0 and pC = 1/4. Expand the six rounds of the distribution, remove the zero-probability idle operations, and sum over the eight states. The preparation law is the product of the three Bernoulli masses. With p0 = 0, exact arithmetic gives output error 1481/4096. The same finite calculation with p0 = 1/100 gives 23121347/64000000.

Assume the coordinatewise assertion. Apply it to this circuit, these outputs and n = 3, k = e = 1, using the purification property and space equality just established. Its first conjunct gives monotonicity in p0. Both (0,0,1/4,0) and (1/100,0,1/4,0) lie in the required parameter region, and their last three coordinates agree. Since 0 ≤ 1/100, monotonicity would give 1481/4096 ≤ 23121347/64000000. Subtracting the right side from the left gives 9639/32000000 > 0, a contradiction. Thus the full coordinatewise assertion fails already in the preparation coordinate. This conclusion imposes no claim about monotonicity in the other three coordinates or about shortest circuits.

References