CCS Concepts: • Theory of computation → Program verification. • Software and its engineering → Compilers.
Introduction
Fault-tolerant quantum computation encodes logical qubits in quantum error-correcting codes. A compiler must translate an algorithm’s gates into operations on these encoded qubits. For surface codes, lattice surgery implements logical gates through joint Pauli measurements [20 , 24 ] . This measurement interface also extends to quantum low-density parity-check (qLDPC) codes.
Code-surgery constructions for qLDPC codes support logical Pauli-product measurements (PPMs) [9 , 32 ] , including joint measurements across code blocks [12 ] and parallel measurements on logically disjoint sets of qubits [11 ] . Despite different connectivity requirements and physical costs, these constructions share a logical measurement interface.
This interface already connects algorithms to proposed architectures. Cain et al. [2026] estimate the resources for Shor’s algorithm, including RSA−2048 factorization, on neutral-atom architectures using lifted-product codes. In their compilation strategy, PPMs serve as an intermediate representation: Clifford gates are absorbed into the measured Pauli operators, and code surgery implements the measurements. Their time-efficient estimates assume parallel code surgery for layers of logically disjoint PPMs. This use of PPMs motivates the interface in Figure 1 .
Figure 1. Compilation stages. Synthesis error is certified per input, lowering to QPPM is verified under explicit magic-state assumptions, and exact transformations preserve the public specifications. Algorithm 1 specifies the solid arrows. The dashed stage is code-specific physical mapping.
Existing lattice-surgery compilers translate circuits into measurement instructions [31 ] (LeBlond et al. 2024). They do not provide a machine-checked proof of that translation preserves an algorithm’s behavior, leaving a gap between algorithm verification and error-correcting
Authors’ addresses: John Zhuoyang Ye, University of California Los Angeles, Los Angeles, USA, yehzhuoyang@cs.ucla.edu. Jens Palsberg, University of California Los Angeles, Los Angeles, USA, palsberg@cs.ucla.edu. implementations. Such a proof must cover both quantum outputs and classical outcomes: a correction reads a measurement result, a gate’s private outcomes must be hidden from its caller, and public outcomes must survive optimization.
We formalize this measurement interface in QPPM, a language for Pauli-product measurements and classical feedback. Its Hoare logic composes specifications according to program structure: a verified phase-gate specification can be reused without expanding the gate’s internal measurements.
Quantum Hoare logic interprets assertions as matrices whose expectations describe quantum states [34 ] . Following Feng and Ying [ [15 ] , these matrices depend on the classical store. An assertion can relate a measurement’s output state to its recorded outcome. Sequencing (H-Seq) connects that specification to a later correction. We prove soundness and relative completeness for QPPM’s weakest-precondition semantics. A forward semantics gives the output states and their probabilities.
Compiled-gate specifications hide private outcomes by summing over their possible values. Optimizations preserve the outcomes available to a continuation. We verify measurement elimination and rotation scheduling under these respective conditions.
Approximate synthesis changes a program’s behavior. We bound the change in the expectation of every effect, a matrix predicate whose expectation lies between zero and one. These bounds compose: replacing a command with allowance ε \varepsilon ε lowers its Hoare guarantee by at most ε \varepsilon ε . Our compiler checks a finite collection of Clifford+T T T approximations and, among those meeting the user’s error limit, selects the implementation with the smallest certified measurement-depth bound (§ 8.1 ).
Our contributions are:
We define QPPM and prove a sound and relatively complete Hoare logic for its measurements, classical control, and scoped ancillas (§ 3 –§ 4 ).
We verify compilation into QPPM and optimizations that preserve public quantum outputs and measurement results. Worked derivations show how their specifications compose (§ 5 –§ 6 ).
We prove compositional approximation bounds and their connection to Hoare specifications and classical–quantum trace distance. A separate implementation contract adds logical-noise bounds without extending the core calculus (§ 7 ).
We mechanize these results in Lean and evaluate them on QASMBench. Verified fusion and scheduling reduce logical measurement depth by 11.8–28.6% in six of eight Clifford circuits, against a parallel baseline with matched ancilla resources. Our proofs concern typed source circuits and ideal logical measurements. Physical mapping and decoding remain outside their scope.
Background and compilation overview
Pauli-product measurements
A qubit has basis states ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ and ∣ 1 ⟩ \lvert1\rangle ∣ 1 ⟩ , and an n n n -qubit register has basis vectors indexed by n n n -bit strings.
We use density matrices to include probabilistic mixtures: a state ρ \rho ρ is a positive semidefinite 2 n × 2 n 2^n \times2^n 2 n × 2 n complex matrix with tr ( ρ ) = 1 \operatorname{tr}(\rho)=1 tr ( ρ ) = 1 , a pure state ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ has density matrix ∣ ψ ⟩ ⟨ ψ ∣ \lvert\psi\rangle\langle\psi\rvert ∣ ψ ⟩ ⟨ ψ ∣ , and a unitary gate U U U acts as ρ ↦ U ρ U † \rho\mapsto U\rho U^\dagger ρ ↦ U ρ U † , where † \dagger † denotes conjugate transpose.
The Pauli matrices are
I = ( 1 0 0 1 ) , X = ( 0 1 1 0 ) , Y = ( 0 − i i 0 ) , Z = ( 1 0 0 − 1 ) . I=\begin{pmatrix}1&0\\0&1\end{pmatrix},\quad X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}. I = ( 1 0 0 1 ) , X = ( 0 1 1 0 ) , Y = ( 0 i − i 0 ) , Z = ( 1 0 0 − 1 ) .
We form a signed Pauli product P = ( − 1 ) η P 1 ⊗ ⋯ ⊗ P n P=(-1)^\eta P_1\otimes\cdots\otimes P_n P = ( − 1 ) η P 1 ⊗ ⋯ ⊗ P n by choosing a sign bit η \eta η and one Pauli matrix for each qubit. The tensor product ⊗ \otimes ⊗ places these operators on their respective qubits. An I I I factor leaves a qubit unchanged. Since P P P is Hermitian and P 2 = I P^2=I P 2 = I , its possible measurement outcomes are + 1 +1 + 1 and − 1 -1 − 1 . We encode them by a bit b b b , with eigenvalue ( − 1 ) b (-1)^b ( − 1 ) b .
Figure 2 illustrates a measurement of Z ⊗ Z Z\otimes Z Z ⊗ Z , which returns the parity of two qubits in the computational basis: outcome zero selects the span of ∣ 00 ⟩ , ∣ 11 ⟩ \lvert00\rangle,\lvert11\rangle ∣ 00 ⟩ , ∣ 11 ⟩ and outcome one the span of ∣ 01 ⟩ , ∣ 10 ⟩ \lvert01\rangle,\lvert10\rangle ∣ 01 ⟩ , ∣ 10 ⟩ , preserving superpositions within the selected subspace, whereas measuring each qubit separately would destroy such coherence. We write r : = measure P r:=\operatorname{measure} P r := measure P for measuring P P P and recording its outcome in r r r . The column in the figure denotes one joint measurement with one result bit. Both quantum wires remain available afterwards. Lattice surgery implements such measurements on encoded qubits [24 ] .
Figure 2. Input qubits q 0 q_0 q 0 , q 1 q_1 q 1 and classical location r r r . One outlined column denotes one joint measurement. In all circuit figures, orange, purple, and blue identify X X X , Y Y Y , Z Z Z . Gray denotes I I I . A meter marks a measurement. The quantum wires continue after the measurement, while the double line carries its classical result.
For a product P P P , define the projectors
Π 0 P = I + P 2 , Π 1 P = I − P 2 . \Pi^P_0=\frac{I+P}{2},\qquad\Pi^P_1=\frac{I-P}{2}. Π 0 P = 2 I + P , Π 1 P = 2 I − P .
The output associated with bit b b b is Π b P ρ Π b P \Pi^P_b\rho\Pi^P_b Π b P ρ Π b P , and its trace gives the probability of that outcome. We retain this unnormalized matrix throughout the semantics: it records the probability and the quantum state in one object. The projectors satisfy
( Π b P ) † = Π b P , ( Π b P ) 2 = Π b P , Π 0 P Π 1 P = Π 1 P Π 0 P = 0 , Π 0 P + Π 1 P = I . (1) (\Pi^P_b)^\dagger=\Pi^P_b,\qquad(\Pi^P_b)^2=\Pi^P_b,\qquad\Pi^P_0\Pi^P_1=\Pi^P_1\Pi^P_0=0,\qquad\Pi^P_0+\Pi^P_1=I. \tag*{(1)} ( Π b P ) † = Π b P , ( Π b P ) 2 = Π b P , Π 0 P Π 1 P = Π 1 P Π 0 P = 0 , Π 0 P + Π 1 P = I . (1)
We prove these identities from the Pauli matrices and use them in the measurement and optimization proofs.
Classical feedback and gate compilation
A measurement program can read a stored outcome to choose a correction. In a gate implementation, these corrections make the output implement the required gate after summing over internal outcomes. Results returned to the caller must remain distinguishable.
We use the phase gate S = diag ( 1 , i ) S = \operatorname{diag}(1, i) S = diag ( 1 , i ) as a running example. Consider an application that measures X X X , applies S S S , and then measures Y Y Y . Since S X S † = Y S X S^\dagger= Y S X S † = Y , the two measurements return the same bit. We verify this property after replacing S S S by measurements and feedback. The application reads its initial and final results. The gate implementation’s outcomes stay private.
To specify this property, we use assertions that relate a stored bit to a quantum eigenspace, following Feng and Ying [ [15 ] . § 4.1 composes the two measurement specifications with the compiled phase gate’s specification.
The Clifford gates H H H , S S S , CNOT map Pauli products to Pauli products by conjugation. Adding T = diag ( 1 , e i π / 4 ) T = \operatorname{diag}(1, e^{i\pi/4}) T = diag ( 1 , e iπ /4 ) permits approximation of arbitrary single-qubit rotations Ross and Selinger [ [27 ] .
When synthesis approximates a source rotation, we bound the change in observable probabilities. § 7 composes these bounds along a circuit and transfers its Hoare specification to the approximate implementation.
QPPM: syntax and semantics
Syntax
A QPPM command c ∈ C n , m c \in\mathcal{C}_{n,m} c ∈ C n , m operates on n n n data qubits and m m m classical bits. Its input and output registers have the same widths. Temporary qubits are introduced by an ancilla scope. The syntax and metatheory are parameterized by n n n and m m m :
e : : = 0 ∣ 1 ∣ read r ∣ ¬ e ∣ e ⊕ e , c : : = skip ∣ r : = e ∣ r : = measure P ∣ correct P ∣ c ▹ c ∣ if e then c else c ∣ let ν = ancilla ∣ b ⟩ in c . \begin{aligned}
e &::= 0 \mid1 \mid\operatorname{read}\ r \mid\neg e \mid e \mathbin{\oplus} e,\\
c &::= \operatorname{skip} \mid r := e \mid r := \operatorname{measure}\ P \mid\operatorname{correct}\ P\\
&\quad\mid c \mathbin{\triangleright} c \mid\operatorname{if}\ e\ \operatorname{then}\ c\ \operatorname{else}\ c\\
&\quad\mid\operatorname{let}\ \nu= \operatorname{ancilla}\ \lvert b\rangle\ \operatorname{in}\ c.
\end{aligned} e c ::= 0 ∣ 1 ∣ read r ∣ ¬ e ∣ e ⊕ e , ::= skip ∣ r := e ∣ r := measure P ∣ correct P ∣ c ▹ c ∣ if e then c else c ∣ let ν = ancilla ∣ b ⟩ in c .
Here e e e is a Boolean expression, r r r is a bit position, and b ∈ { 0 , 1 } b \in\{0, 1\} b ∈ { 0 , 1 } is an initialization value. The operator ⊕ \oplus ⊕ denotes exclusive-or. The product P P P contains one Pauli factor for each qubit in the current register. The correction command applies P P P by conjugation. The sequence c ▹ d c \mathbin{\triangleright} d c ▹ d executes c c c then d d d . Programs have declared input contexts Γ = ( q 0 , … , q n − 1 ) \Gamma= (q_0, \ldots, q_{n-1}) Γ = ( q 0 , … , q n − 1 ) for qubits and Δ = ( r 0 , … , r m − 1 ) \Delta= (r_0, \ldots, r_{m-1}) Δ = ( r 0 , … , r m − 1 ) for classical locations, with distinct names in each. These ordered lists name register positions, and ( ) () ( ) denotes an empty register. Every qubit reference must belong to the current Γ \Gamma Γ , and every bit read or write must refer to Δ \Delta Δ . Measurement overwrites a declared location rather than allocating one. The caller supplies the input state and initial classical values. A scope binds a fresh name ν ∉ Γ \nu\notin\Gamma ν ∈ / Γ to a first qubit prepared in ∣ b ⟩ \lvert b\rangle ∣ b ⟩ , executes its body in C n + 1 , m \mathcal{C}_{n+1,m} C n + 1 , m with context ( ν , Γ ) (\nu,\Gamma) ( ν , Γ ) , and discards ν \nu ν . Existing qubits keep their names and move up one position inside the scope. The name ν \nu ν is local to the body. Classical writes remain available afterwards. On a one-qubit register we omit the qubit subscript. Unmentioned tensor factors are I I I .
We abbreviate r : = measure P r := \operatorname{measure}\ P r := measure P by M P ( r ) M_P(r) M P ( r ) and read r r r by r r r in guards and assignments. Figure 3 uses these commands to reset a qubit to ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ while returning a copy of the measurement record. Measurement supplies the record. The conditional applies a correction only to outcome one. Assignment makes the copy. We use this same program for the backward, forward, and Hoare derivations below.
Figure 3. Inputs: Γ = ( q ) \Gamma= (q) Γ = ( q ) , Δ = ( r , u ) \Delta= (r,u) Δ = ( r , u ) . Measure Z Z Z , correct outcome 1, and copy the result. The double wire carries r r r to the correction and assignment. When r = 0 r = 0 r = 0 , the data wire passes through unchanged.
Assertions and weakest preconditions
A classical store s s s maps the m m m bit positions to Boolean values. We use assertions A A A that map each store to a Hermitian matrix on the quantum register. For a quantum state ρ \rho ρ , the value tr ( ρ A ( s ) ) \operatorname{tr}(\rho A(s)) tr ( ρ A ( s )) is its expectation. An effect satisfies 0 ⪯ A ( s ) ⪯ I 0 \preceq A(s) \preceq I 0 ⪯ A ( s ) ⪯ I for every store, so this expectation lies between zero and one on normalized states. The mechanization admits arbitrary complex matrices, which is convenient for intermediate calculations. Every assertion in this paper is Hermitian.
The classical locations of a program are divided into public bits, which the caller may read, and private bits, which a component uses for its internal measurement outcomes. Let π \pi π map a store to its public part. A public assertion has the form A ∘ π A \circ\pi A ∘ π : it ignores the private bits. The contracts of § 5 are stated for public assertions, so that a compiled gate’s internal outcomes are hidden from its caller, whereas the optimizer of § 6 compares assertions on the full store because the continuation may read any retained bit.
Two forms recur. A classical event E E E gives the effect [ E ] [E] [ E ] , with [ E ] ( s ) = I [E](s) = I [ E ] ( s ) = I if E ( s ) E(s) E ( s ) holds and 0 0 0 otherwise, whose expected value on a program output is the probability of E E E . A quantum property that depends on a measurement result uses A ( s ) = Π s ( r ) P A(s) = \Pi_{s(r)}^{P} A ( s ) = Π s ( r ) P : expectation one states that the output lies in the eigenspace recorded in r r r , and multiplying by [ s ( u ) = s ( r ) ] [s(u) = s(r)] [ s ( u ) = s ( r )] also requires two result bits to agree. Both forms appear in the reset and phase-gate examples.
In the Löwner order, A ⊑ B A \sqsubseteq B A ⊑ B means that B ( s ) − A ( s ) B(s) - A(s) B ( s ) − A ( s ) is positive semidefinite for every store s s s . This order compares expectations on all positive states. Effects are the assertions used for probability and approximation allowances.
We define wp ( c , A ) \operatorname{wp}(c,A) wp ( c , A ) by reasoning backwards from the postcondition A A A through c c c : assignment substitutes the new bit value into A A A , measurement performs this substitution for each outcome and applies the corresponding projectors, and an ancilla scope ignores the temporary qubit in the postcondition and assumes its initial state in the precondition.
Write s [ r ↦ b ] s[r \mapsto b] s [ r ↦ b ] for the store obtained by updating bit r r r to b b b . Let E b E_b E b be the inclusion ∣ ψ ⟩ ↦ ∣ b ⟩ ⊗ ∣ ψ ⟩ \lvert\psi\rangle\mapsto\lvert b\rangle\otimes\lvert\psi\rangle ∣ ψ ⟩ ↦ ∣ b ⟩ ⊗ ∣ ψ ⟩ . Write prep b ∗ ( A ) = E b † A E b \operatorname{prep}^{*}_{b}(A) = E_b^{\dagger} A E_b prep b ∗ ( A ) = E b † A E b and drop ∗ ( B ) = ∑ j = 0 1 E j B E j † = I 2 ⊗ B \operatorname{drop}^{*}(B) = \sum_{j=0}^{1} E_j B E_j^{\dagger} = I_2 \otimes B drop ∗ ( B ) = ∑ j = 0 1 E j B E j † = I 2 ⊗ B , acting pointwise on assertions. The weakest-precondition equations are:
wp ( skip , A ) = A \operatorname{wp}(\operatorname{skip}, A) = A wp ( skip , A ) = A
wp ( r : = e , A ) ( s ) = A ( s [ r ↦ e ( s ) ] ) \operatorname{wp}(r := e, A)(s) = A(s[r \mapsto e(s)]) wp ( r := e , A ) ( s ) = A ( s [ r ↦ e ( s )])
wp ( correct P , A ) ( s ) = P A ( s ) P \operatorname{wp}(\operatorname{correct}\ P, A)(s) = P A(s) P wp ( correct P , A ) ( s ) = P A ( s ) P
wp ( c ▹ d , A ) = wp ( c , wp ( d , A ) ) \operatorname{wp}(c \mathbin{\triangleright} d, A) = \operatorname{wp}(c,\operatorname{wp}(d,A)) wp ( c ▹ d , A ) = wp ( c , wp ( d , A ))
wp ( M P ( r ) , A ) ( s ) = ∑ j = 0 1 Π j P A ( s [ r ↦ j ] ) Π j P \operatorname{wp}(M_P(r),A)(s) = \sum_{j=0}^{1} \Pi_j^P A(s[r \mapsto j]) \Pi_j^P wp ( M P ( r ) , A ) ( s ) = j = 0 ∑ 1 Π j P A ( s [ r ↦ j ]) Π j P
wp ( if e then c else d , A ) ( s ) = { wp ( c , A ) ( s ) e ( s ) = 1 , wp ( d , A ) ( s ) e ( s ) = 0 , \operatorname{wp}(\operatorname{if}\ e\ \operatorname{then}\ c\ \operatorname{else}\ d,A)(s) =
\begin{cases}
\operatorname{wp}(c,A)(s) & e(s) = 1,\\
\operatorname{wp}(d,A)(s) & e(s) = 0,
\end{cases} wp ( if e then c else d , A ) ( s ) = { wp ( c , A ) ( s ) wp ( d , A ) ( s ) e ( s ) = 1 , e ( s ) = 0 ,
wp ( let v = ancilla ∣ b ⟩ in c , A ) = prep b ∗ ( wp ( c , drop ∗ ( A ) ) ) . \operatorname{wp}(\operatorname{let}\ v = \operatorname{ancilla}\ \lvert b\rangle\ \operatorname{in}\ c,A)
= \operatorname{prep}^{*}_{b}(\operatorname{wp}(c,\operatorname{drop}^{*}(A))). wp ( let v = ancilla ∣ b ⟩ in c , A ) = prep b ∗ ( wp ( c , drop ∗ ( A ))) .
We prove that wp \operatorname{wp} wp is linear and monotone, that wp ( c , I ) = I \operatorname{wp}(c,I)=I wp ( c , I ) = I , and that it maps effects to effects. These properties justify H-Cons and the approximation rules of Theorem 4 .
Example: calculate the reset precondition. For the program in Figure 3 , set
Q 0 = Π 0 Z = ( 1 0 0 0 ) , Q 1 = Π 1 Z = ( 0 0 0 1 ) , R ( s ) = Q s ( r ) . Q_0=\Pi^Z_0=\begin{pmatrix}1&0\\0&0\end{pmatrix},\qquad Q_1=\Pi^Z_1=\begin{pmatrix}0&0\\0&1\end{pmatrix},\qquad R(s)=Q_{s(r)}. Q 0 = Π 0 Z = ( 1 0 0 0 ) , Q 1 = Π 1 Z = ( 0 0 0 1 ) , R ( s ) = Q s ( r ) .
The desired postcondition is B r e s e t ( s ) = [ s ( u ) = s ( r ) ] Q 0 B_{\mathrm{reset}}(s)=[s(u)=s(r)]Q_0 B reset ( s ) = [ s ( u ) = s ( r )] Q 0 : the qubit is in ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ and the two records agree. We calculate backwards, placing each command fragment beside its substitution. A schematic wire carries the quantum register and classical store. A box denotes a command. A fork selects a branch. In the expanded circuits, single wires are qubits and double wires carry bits.
1. Copy the record. Since r ≠ u r\ne u r = u , Equation (W-Asgn) gives
wp ( u : = r , B r e s e t ) ( s ) = B r e s e t ( s [ u ↦ s ( r ) ] ) = [ s ( r ) = s ( r ) ] Q 0 = Q 0 . \operatorname{wp}(u:=r,B_{\mathrm{reset})(s)=B_{\mathrm{reset}}(s[u\mapsto s(r)])
=[s(r)=s(r)]Q_0=Q_0.} wp ( u := r , B reset ) ( s ) = B reset ( s [ u ↦ s ( r )]) = [ s ( r ) = s ( r )] Q 0 = Q 0 .
2. Correct the measured state. Write g g g for the conditional in the figure. The two arms require different input eigenspaces by (W-If), (W-Corr), and (W-Skip):
wp ( g , Q 0 ) ( s ) = { X Q 0 X s ( r ) = 1 , Q 0 s ( r ) = 0 = { Q 1 s ( r ) = 1 , Q 0 s ( r ) = 0 = R ( s ) . \operatorname{wp}(g,Q_0)(s)=
\begin{cases}
XQ_0X & s(r)=1,\\
Q_0 & s(r)=0
\end{cases}
=
\begin{cases}
Q_1 & s(r)=1,\\
Q_0 & s(r)=0
\end{cases}
=R(s). wp ( g , Q 0 ) ( s ) = { X Q 0 X Q 0 s ( r ) = 1 , s ( r ) = 0 = { Q 1 Q 0 s ( r ) = 1 , s ( r ) = 0 = R ( s ) .
The correction equation X Q 0 X = Q 1 XQ_0X=Q_1 X Q 0 X = Q 1 can be checked entry by entry.
3. Measure and substitute each outcome. In (W-Meas), the update inside R R R selects the matching projector:
wp ( M Z ( r ) , R ) ( s ) = Q 0 R ( s [ r ↦ 0 ] ) Q 0 + Q 1 R ( s [ r ↦ 1 ] ) Q 1 = Q 0 3 + Q 1 3 = Q 0 + Q 1 = I . \operatorname{wp}(M_Z(r),R)(s)=Q_0R(s[r\mapsto0])Q_0+Q_1R(s[r\mapsto1])Q_1
=Q_0^3+Q_1^3=Q_0+Q_1=I. wp ( M Z ( r ) , R ) ( s ) = Q 0 R ( s [ r ↦ 0 ]) Q 0 + Q 1 R ( s [ r ↦ 1 ]) Q 1 = Q 0 3 + Q 1 3 = Q 0 + Q 1 = I .
Applying (W-Seq) twice yields wp ( c r e s e t , B r e s e t ) = I \operatorname{wp}(c_{\mathrm{reset}},B_{\mathrm{reset}})=I wp ( c reset , B reset ) = I for every initial store. In particular, the postcondition has expectation one on every normalized input. For a fresh qubit measured in X X X and discarded, (W-Anc) and (W-Meas) give wp ( l e t ν = a n c i l l a ∣ 0 ⟩ i n M X ( ν ) ( r ) , [ r = 1 ] ) = E 0 † E 1 † E 0 = 1 2 \operatorname{wp}(\mathop{\mathrm{let}}\nu=\mathrm{ancilla}\ \lvert0\rangle\mathop{\mathrm{in}} M_X(\nu)(r),[r=1])=E_0^\dagger E_1^\dagger E_0=\frac{1}{2} wp ( let ν = ancilla ∣ 0 ⟩ in M X ( ν ) ( r ) , [ r = 1 ]) = E 0 † E 1 † E 0 = 2 1 : the record is a fair bit.
Forward semantics
To describe execution, we assign a quantum output matrix to each final store. For input store s s s , input matrix ρ \rho ρ , and final store t t t , write this matrix as I c ( s , ρ , t ) \mathcal{I}_c(s,\rho,t) I c ( s , ρ , t ) . Together these matrices form the program’s instrument . On a normalized input, the trace of each matrix is the probability of that final store. We prove
ρ ⪰ 0 ⟹ I c ( s , ρ , t ) ⪰ 0 , ∑ t tr ( I c ( s , ρ , t ) ) = tr ( ρ ) . \rho\succeq0\Longrightarrow\mathcal{I}_c(s,\rho,t)\succeq0,\qquad\sum_t\operatorname{tr}(\mathcal{I}_c(s,\rho,t))=\operatorname{tr}(\rho). ρ ⪰ 0 ⟹ I c ( s , ρ , t ) ⪰ 0 , t ∑ tr ( I c ( s , ρ , t )) = tr ( ρ ) .
The forward scope prepares E b ρ E b † E_b\rho E_b^\dagger E b ρ E b † , executes the body, and applies partial trace separately to each final-store block, even when the ancilla is entangled with the data. The following duality equation connects the execution semantics to weakest preconditions:
( s , ρ ) ⟶ c ⟶ { I c ( s , ρ , t ) } t wp ( c , A ) ( s ) ⟵ { A ( t ) } t \begin{aligned}
(s,\rho)&\longrightarrow c \longrightarrow\{\mathcal{I}_c(s,\rho,t)\}_t\\
\operatorname{wp}(c,A)(s)&\longleftarrow\{A(t)\}_t
\end{aligned} ( s , ρ ) wp ( c , A ) ( s ) ⟶ c ⟶ { I c ( s , ρ , t ) } t ⟵ { A ( t ) } t
tr ( ρ wp ( c , A ) ( s ) ) = ∑ t tr ( I c ( s , ρ , t ) A ( t ) ) (2) \operatorname{tr}(\rho\,\operatorname{wp}(c,A)(s))=\sum_t\operatorname{tr}\left(\mathcal{I}_c(s,\rho,t)A(t)\right) \tag*{(2)} tr ( ρ wp ( c , A ) ( s )) = t ∑ tr ( I c ( s , ρ , t ) A ( t ) ) (2)
Execution runs rightwards. Assertions are pulled back leftwards. The dotted pairings evaluate the same expected value at the input and at the complete output distribution. For a component with private bits, its public output at public store t t t sums the blocks of all final stores with that public part:
I c p u b l i c ( s , ρ , t ) = ∑ u : π ( u ) = t I c ( s , ρ , u ) . \mathcal{I}^{\mathrm{public}}_c(s,\rho,t)=\sum_{u:\pi(u)=t}\mathcal{I}_c(s,\rho,u). I c public ( s , ρ , t ) = u : π ( u ) = t ∑ I c ( s , ρ , u ) .
By duality, the expectation of A A A on this output equals that of A ∘ π A\circ\pi A ∘ π on the full output. Hiding bits is part of a public specification. An ancilla scope itself retains all classical writes.
Duality is proved by a finite path construction in which every execution path contributes one Kraus operator and one final store.
Example: execute the reset program. Take the initial store ( r , u ) = ( 0 , 0 ) (r,u)=(0,0) ( r , u ) = ( 0 , 0 ) and the state ∣ + ⟩ = ( ∣ 0 ⟩ + ∣ 1 ⟩ ) / 2 \lvert+\rangle=(\lvert0\rangle+\lvert1\rangle)/\sqrt{2} ∣ + ⟩ = (∣ 0 ⟩ + ∣ 1 ⟩) / 2 , with density matrix ρ + = ∣ + ⟩ ⟨ + ∣ = 1 2 ( 1 1 1 1 ) \rho_+=\lvert+\rangle\langle+\rvert=\frac{1}{2}\begin{pmatrix}1&1\\1&1\end{pmatrix} ρ + = ∣ + ⟩ ⟨ + ∣ = 2 1 ( 1 1 1 1 ) . Each row below follows one outcome. The matrix at a boundary retains the probability of reaching it. The pair below it is the current store ( r , u ) (r,u) ( r , u ) .
ρ + Z Q 0 / 2 skip Q 0 / 2 u : = r Q 0 / 2 r = 0 ( 0 , 0 ) ( 0 , 0 ) ( 0 , 0 ) ρ + Z Q 1 / 2 X Q 0 / 2 u : = r Q 0 / 2 r = 1 ( 1 , 0 ) ( 1 , 0 ) ( 1 , 1 ) \begin{array}{ccccccc}
\rho_+ & Z & Q_0/2 & \operatorname{skip} & Q_0/2 & u:=r & Q_0/2\\
& r=0 & (0,0) & & (0,0) & & (0,0)\\[4pt]
\rho_+ & Z & Q_1/2 & X & Q_0/2 & u:=r & Q_0/2\\
& r=1 & (1,0) & & (1,0) & & (1,1)
\end{array} ρ + ρ + Z r = 0 Z r = 1 Q 0 /2 ( 0 , 0 ) Q 1 /2 ( 1 , 0 ) skip X Q 0 /2 ( 0 , 0 ) Q 0 /2 ( 1 , 0 ) u := r u := r Q 0 /2 ( 0 , 0 ) Q 0 /2 ( 1 , 1 )
The first boundary uses Q b ρ + Q b = Q b / 2 Q_b\rho_+Q_b=Q_b/2 Q b ρ + Q b = Q b /2 , the lower correction uses X ( Q 1 / 2 ) X = Q 0 / 2 X(Q_1/2)X=Q_0/2 X ( Q 1 /2 ) X = Q 0 /2 , and assignment changes only the store. The two nonzero final blocks, I c r e s e t ( ( 0 , 0 ) , ρ + , ( 0 , 0 ) ) \mathcal{I}_{c_{\mathrm{reset}}}((0,0),\rho_+,(0,0)) I c reset (( 0 , 0 ) , ρ + , ( 0 , 0 )) and I c r e s e t ( ( 0 , 0 ) , ρ + , ( 1 , 1 ) ) \mathcal{I}_{c_{\mathrm{reset}}}((0,0),\rho_+,(1,1)) I c reset (( 0 , 0 ) , ρ + , ( 1 , 1 )) , both equal Q 0 / 2 Q_0/2 Q 0 /2 and have trace 1 / 2 1/2 1/2 , so the records remain distinguishable although their quantum outputs agree. For B r e s e t B_{\mathrm{reset}} B reset , Equation (2) reads tr ( ρ + I ) = 1 = tr ( ( Q 0 / 2 ) Q 0 ) + tr ( ( Q 0 / 2 ) Q 0 ) \operatorname{tr}(\rho_+I)=1=\operatorname{tr}((Q_0/2)Q_0)+\operatorname{tr}((Q_0/2)Q_0) tr ( ρ + I ) = 1 = tr (( Q 0 /2 ) Q 0 ) + tr (( Q 0 /2 ) Q 0 ) , and for the event [ r = 1 ] [r=1] [ r = 1 ] only the second block contributes, giving probability 1 / 2 1/2 1/2 .
Hoare logic
We define validity of a triple { A } c { B } \{A\}\ c\ \{B\} { A } c { B } by A ⊑ wp ( c , B ) A\sqsubseteq\operatorname{wp}(c,B) A ⊑ wp ( c , B ) . For Hermitian assertions, duality means that executing c c c establishes an expected value of B B B at least as large as the initial expected value of A A A . We write ⊢ { A } c { B } \vdash\{A\}\ c\ \{B\} ⊢ { A } c { B } when the triple is derivable using the following rules. Commands c c c , d d d , Boolean expression e e e , and assertions A A A , B B B , C C C , Q Q Q use the same declared contexts, except at a scope boundary. Here p p p ranges over assignment, measurement, and correction, and A ◃ e B A\mathrel{\triangleleft_e}B A ◃ e B selects A ( s ) A(s) A ( s ) when e ( s ) = 1 e(s)=1 e ( s ) = 1 and B ( s ) B(s) B ( s ) otherwise.
We draw the command inside its judgment:
{ A } c { B } denotes { A } c { B } , r : = measure P (3) \{A\}\ c\ \{B\}\ \text{ denotes }\ \{A\}\ c\ \{B\},\qquad
r:=\operatorname{measure}\ P \tag*{(3)} { A } c { B } denotes { A } c { B } , r := measure P (3)
Joining command boxes means sequencing, and braces mark assertions at their boundaries. Colored rounded boxes inside assertions denote the displayed matrices, without applying an operation.
H-Skip { A } s k i p { A } H-Prim { wp ( p , B ) } p { B } ( p primitive ) \begin{aligned}
&\text{H-Skip}\qquad\{A\}\ \boxed{\mathit{skip}}\ \{A\}\\
&\text{H-Prim}\qquad\{\operatorname{wp}(p,B)\}\ \boxed{p}\ \{B\}\qquad(p\text{ primitive})
\end{aligned} H-Skip { A } skip { A } H-Prim { wp ( p , B )} p { B } ( p primitive )
{ A } c { B } { B } d { C } { A } c d { C } H-Seq \frac{\{A\}\ \boxed{c}\ \{B\}\qquad\{B\}\ \boxed{d}\ \{C\}}{\{A\}\ \boxed{c}\ \boxed{d}\ \{C\}}
\qquad\text{H-Seq} { A } c d { C } { A } c { B } { B } d { C } H-Seq
{ A } c { Q } { B } d { Q } { A ▹ e B } if e then c else d { Q } H-If \frac{\{A\}\ \boxed{c}\ \{Q\}\qquad\{B\}\ \boxed{d}\ \{Q\}}{\{A \mathbin{\triangleright_e} B\}\ \boxed{\text{if }e\text{ then }c\text{ else }d}\ \{Q\}}
\qquad\text{H-If} { A ▹ e B } if e then c else d { Q } { A } c { Q } { B } d { Q } H-If
{ A } c { drop ∗ ( B ) } { prep b ∗ ( A ) } let ν = ancilla ∣ b ⟩ in c { B } H-Anc \frac{\{A\}\ \boxed{c}\ \{\operatorname{drop}^{*}(B)\}}{\{\operatorname{prep}_{b}^{*}(A)\}\ \boxed{\text{let }\nu=\text{ancilla }|b\rangle\text{ in }c}\ \{B\}}
\qquad\text{H-Anc} { prep b ∗ ( A )} let ν = ancilla ∣ b ⟩ in c { B } { A } c { drop ∗ ( B )} H-Anc
A ⊑ A ′ { A ′ } c { B ′ } B ′ ⊑ B { A } c { B } H-Cons \frac{A\sqsubseteq A'\qquad\{A'\}\ \boxed{c}\ \{B'\}\qquad B'\sqsubseteq B}{\{A\}\ \boxed{c}\ \{B\}}
\qquad\text{H-Cons} { A } c { B } A ⊑ A ′ { A ′ } c { B ′ } B ′ ⊑ B H-Cons
In H-Anc, the premise uses context ( ν , Γ ) (\nu,\Gamma) ( ν , Γ ) and the conclusion uses Γ \Gamma Γ . The body postcondition ignores the temporary qubit. Compressing the body precondition by prep b ∗ \operatorname{prep}_{b}^{*} prep b ∗ accounts for its initialization.
Example: derive the reset triple. We now use the rules to prove the specification whose precondition we calculated above. Rules H-Prim and H-Skip supply the premises of H-If:
{ Q 1 } X { Q 0 } { Q 0 } s k i p { Q 0 } { Q 1 ▹ r Q 0 } if r then X else skip { Q 0 } \frac{\{Q_1\}\ \boxed{X}\ \{Q_0\}\qquad\{Q_0\}\ \boxed{\mathit{skip}}\ \{Q_0\}}{\{Q_1\mathbin{\triangleright_r}Q_0\}\ \boxed{\text{if }r\text{ then }X\text{ else skip}}\ \{Q_0\}} { Q 1 ▹ r Q 0 } if r then X else skip { Q 0 } { Q 1 } X { Q 0 } { Q 0 } skip { Q 0 }
The correction premise uses X Q 0 X = Q 1 XQ_0X=Q_1 X Q 0 X = Q 1 . The guard reads r r r , so Q 1 ▹ r Q 0 Q_1\mathbin{\triangleright_r}Q_0 Q 1 ▹ r Q 0 selects Q 1 Q_1 Q 1 on outcome one and Q 0 Q_0 Q 0 on outcome zero. Rule H-Prim, instantiated with (W-Meas) and (W-Asgn), gives the other two triples:
{ I } Z { R } { Q 0 } u : = r { B r e s e t } . \{I\}\ \boxed{Z}\ \{R\}\qquad\{Q_0\}\ \boxed{u:=r}\ \{B_{\mathrm{reset}}\}. { I } Z { R } { Q 0 } u := r { B reset } .
Two uses of H-Seq join the equal assertion boundaries:
{ I } Z { R } { R } r then X else skip { Q 0 } { Q 0 } u : = r { B r e s e t } { I } c r e s e t { B r e s e t } (4) \frac{\{I\}\ \boxed{Z}\ \{R\}\qquad\{R\}\ \boxed{r\text{ then }X\text{ else skip}}\ \{Q_0\}\qquad\{Q_0\}\ \boxed{u:=r}\ \{B_{\mathrm{reset}}\}}{\{I\}\ \boxed{c_{\mathrm{reset}}}\ \{B_{\mathrm{reset}}\}} \tag*{(4)} { I } c reset { B reset } { I } Z { R } { R } r then X else skip { Q 0 } { Q 0 } u := r { B reset } (4)
This is a derivation of ⊢ { I } c r e s e t { B r e s e t } \vdash\{I\}\ c_{\mathrm{reset}}\ \{B_{\mathrm{reset}}\} ⊢ { I } c reset { B reset } . To keep only the classical guarantee, put E ( s ) ≡ s ( u ) = s ( r ) E(s)\equiv s(u)=s(r) E ( s ) ≡ s ( u ) = s ( r ) . At an agreeing store, [ E ] ( s ) − B r e s e t ( s ) = I − Q 0 = Q 1 ⪰ 0 [E](s)-B_{\mathrm{reset}}(s)=I-Q_0=Q_1\succeq0 [ E ] ( s ) − B reset ( s ) = I − Q 0 = Q 1 ⪰ 0 . At a disagreeing store, the difference is zero. Hence B r e s e t ⊑ [ E ] B_{\mathrm{reset}}\sqsubseteq[E] B reset ⊑ [ E ] , and H-Cons gives
I ⊑ I { I } c r e s e t { B r e s e t } B r e s e t ⊑ [ E ] { I } c r e s e t { [ E ] } \frac{I\sqsubseteq I\qquad\{I\}\ \boxed{c_{\mathrm{reset}}}\ \{B_{\mathrm{reset}}\}\qquad B_{\mathrm{reset}}\sqsubseteq[E]}{\{I\}\ \boxed{c_{\mathrm{reset}}}\ \{[E]\}} { I } c reset {[ E ]} I ⊑ I { I } c reset { B reset } B reset ⊑ [ E ]
Thus the records agree with probability one.
The rules are a syntactic presentation of the weakest-precondition equations: each primitive rule instantiates one equation, and the structural rules follow the recursion of wp \operatorname{wp} wp . Since every QPPM command terminates, the following theorem is therefore immediate, and partial and total correctness coincide.
Theorem 1 (Soundness and relative completeness). For every QPPM command c c c and assertions A A A , B B B , ⊢ { A } c { B } \vdash\{A\}\ c\ \{B\} ⊢ { A } c { B } if and only if A ⊑ wp ( c , B ) A\sqsubseteq\operatorname{wp}(c,B) A ⊑ wp ( c , B ) .
Proof. Soundness is induction on the derivation, using monotonicity of wp \operatorname{wp} wp and positivity of the preparation map. For completeness, structural induction on c c c derives ⊢ { wp ( c , B ) } c { B } \vdash\{ \operatorname{wp}(c,B) \}\ c\ \{B\} ⊢ { wp ( c , B )} c { B } , and H-Cons supplies any valid precondition:
A ⊑ wp ( c , B ) { wp ( c , B ) } c { B } { A } c { B } \frac{A \sqsubseteq\operatorname{wp}(c,B) \qquad\{ \operatorname{wp}(c,B) \}\ c\ \{B\}}{\{A\}\ c\ \{B\}} { A } c { B } A ⊑ wp ( c , B ) { wp ( c , B )} c { B }
Completeness is relative to proofs of the matrix-order side conditions. The value of the rules lies in composition: a derived triple for a component is reused at every call site without recomputing its weakest precondition. In the soundness case for H-Seq , monotonicity and (W-Seq) give A ⊑ wp ( c , B ) ⊑ wp ( c , wp ( d , C ) ) A \sqsubseteq\operatorname{wp}(c,B) \sqsubseteq\operatorname{wp}(c,\operatorname{wp}(d,C)) A ⊑ wp ( c , B ) ⊑ wp ( c , wp ( d , C )) . For H-Anc , positive compression by E b E_b E b preserves the matrix order, and (W-Anc) gives the conclusion.
Define exact equivalence c ≡ d c \equiv d c ≡ d by equality of their weakest preconditions for every matrix assertion. The theorem immediately transports all Hoare specifications between equivalent commands. The instrument development also proves equality of their output matrices for each final store. We use this equivalence as the correctness condition for QPPM optimizations.
Verification of the phase-gate application
We now verify the application introduced in § 2 , with inputs Γ = ( d ) \Gamma=(d) Γ = ( d ) and Δ = ( a , b , r , t ) \Delta=(a,b,r,t) Δ = ( a , b , r , t ) . Locations r , t r,t r , t are public. Locations a , b a,b a , b are private to the phase implementation C S C_S C S of Figure 5 . The application is
Figure 5. Clifford gates using only Pauli measurements and conditional corrections. Here M P ( r ) M_P(r) M P ( r ) is r : = measure P r := \text{measure }P r := measure P . Every meter records the indicated bit. An ⊕ \oplus ⊕ node controls a correction when the two outcomes differ. Double end bars discard an ancilla. Each following ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ begins a fresh scope. A gray I I I factor is drawn only inside a joint measurement column. The output specification hides a , b a,b a , b .
c a p p = M X ( r ) ▹ C S ▹ M Y ( t ) . c_{\mathrm{app}}=M_X(r)\mathbin{\triangleright} C_S\mathbin{\triangleright} M_Y(t). c app = M X ( r ) ▹ C S ▹ M Y ( t ) .
We want the final bits to agree and the quantum state to lie in the corresponding Y Y Y eigenspace. Define
A X ( s ) = Π s ( r ) X , A Y ( s ) = Π s ( r ) Y , B ( s ) = [ s ( t ) = s ( r ) ] Π s ( r ) Y . A_X(s)=\Pi^{X}_{s(r)}, \qquad A_Y(s)=\Pi^{Y}_{s(r)}, \qquad B(s)=[s(t)=s(r)]\Pi^{Y}_{s(r)}. A X ( s ) = Π s ( r ) X , A Y ( s ) = Π s ( r ) Y , B ( s ) = [ s ( t ) = s ( r )] Π s ( r ) Y .
Our specification is
{ I } c a p p { B } . (5) \{I\}\ c_{\mathrm{app}}\ \{B\}. \tag*{(5)} { I } c app { B } . (5)
Figure 4 places each intermediate assertion below its position in the circuit and the corresponding triples beside it.
Figure 4. Inputs: Γ = ( d ) \Gamma=(d) Γ = ( d ) , Δ = ( a , b , r , t ) \Delta=(a,b,r,t) Δ = ( a , b , r , t ) . Assertions under the wire mark the intermediate specifications. The result bits r , t r,t r , t are public. The phase component’s private bits are hidden from these assertions.
Step 1: establish A X A_X A X . Step 3 of the reset calculation, with X X X in place of Z Z Z , establishes the eigenspace named by r r r : for A P ( s ) = Π s ( r ) P A_P(s)=\Pi^P_{s(r)} A P ( s ) = Π s ( r ) P , (W-Meas) gives wp ( M P ( r ) , A P ) ( s ) = ∑ b Π b P Π b P Π b P = I \operatorname{wp}(M_P(r),A_P)(s)=\sum_b \Pi^P_b\Pi^P_b\Pi^P_b=I wp ( M P ( r ) , A P ) ( s ) = ∑ b Π b P Π b P Π b P = I .
Step 2: transport the projector through the component. The component contract established in § 5 says that public postconditions are pulled back by S † ( ⋅ ) S S^{\dagger}(\cdot)S S † ( ⋅ ) S . The relevant matrix calculation is S X S † = diag ( 1 , i ) X diag ( 1 , − i ) = ( 0 − i i 0 ) = Y SXS^{\dagger}=\operatorname{diag}(1,i)X\operatorname{diag}(1,-i)=\begin{pmatrix}0&-i\\i&0\end{pmatrix}=Y S X S † = diag ( 1 , i ) X diag ( 1 , − i ) = ( 0 i − i 0 ) = Y . Conjugation distributes over I ± X I\pm X I ± X , so S Π b X S † = Π b Y S\Pi_{b}^{X}S^{\dagger}=\Pi_{b}^{Y} S Π b X S † = Π b Y . Unitarity then gives S † Π b Y S = Π b X S^{\dagger}\Pi_{b}^{Y}S=\Pi_{b}^{X} S † Π b Y S = Π b X . As the component preserves public stores, the label s ( r ) s(r) s ( r ) is unchanged. Its weakest precondition for A Y A_{Y} A Y is exactly A X A_{X} A X , proving { A X } C S { A Y } \{A_{X}\}C_{S}\{A_{Y}\} { A X } C S { A Y } . Both assertions depend only on the public bit r r r and the data qubit.
Step 3: establish agreement and the final eigenspace. A second measurement of the same product copies the recorded eigenspace: since t ≠ r t\ne r t = r , (W-Meas) gives wp ( M Y ( t ) , B ) ( s ) = ∑ b Π b Y [ b = s ( r ) ] Π b Y = Π s ( r ) Y = A Y ( s ) \operatorname{wp}(M_{Y}(t),B)(s)=\sum_{b}\Pi_{b}^{Y}[b=s(r)]\Pi_{b}^{Y}=\Pi_{s(r)}^{Y}=A_{Y}(s) wp ( M Y ( t ) , B ) ( s ) = ∑ b Π b Y [ b = s ( r )] Π b Y = Π s ( r ) Y = A Y ( s ) . The precondition is exactly A Y A_{Y} A Y , so there is no intervening matrix inequality to guess. Two uses of H-Seq, shown in Figure 4 , prove Equation (5) .
Step 4: extract an ordinary probability guarantee. Let E ( s ) E(s) E ( s ) be s ( t ) = s ( r ) s(t)=s(r) s ( t ) = s ( r ) . Since 0 ⪯ Π s ( r ) Y ⪯ I 0\preceq\Pi_{s(r)}^{Y}\preceq I 0 ⪯ Π s ( r ) Y ⪯ I , we have B ⊑ [ E ] B\sqsubseteq[E] B ⊑ [ E ] , so H-Cons gives { I } c a p p { [ E ] } \{I\}\,c_{\mathrm{app}}\,\{[E]\} { I } c app {[ E ]} . Duality on a positive trace-one input yields 1 ≤ ∑ u : E ( u ) tr ( I c a p p ( s , ρ , u ) ) 1\le\sum_{u:E(u)}\operatorname{tr}(\mathcal{I}_{c_{\mathrm{app}}}(s,\rho,u)) 1 ≤ ∑ u : E ( u ) tr ( I c app ( s , ρ , u )) , and total trace preservation gives the reverse inequality, so agreement has probability one.
Step 5: reuse the proof after transformation. Exact optimization preserves this triple, and a certificate O ( c a p p ) ≈ ε d O(c_{\mathrm{app}})\approx_{\varepsilon}d O ( c app ) ≈ ε d transfers the effect postcondition B B B to d d d with precondition ( 1 − ε ) I (1-\varepsilon)I ( 1 − ε ) I , so Pr d [ E ] ≥ 1 − ε \Pr_{d}[E]\ge1-\varepsilon Pr d [ E ] ≥ 1 − ε .
An incorrect phase-gate implementation
Delete the phase component and call the resulting program d = M X ( r ) ▹ M Y ( t ) d=M_{X}(r)\mathbin{\triangleright}M_{Y}(t) d = M X ( r ) ▹ M Y ( t ) . For the event E E E , (W-Seq) and (W-Meas) give the exact precondition:
wp ( d , [ E ] ) = ∑ b = 0 1 Π b X Π b Y Π b X = 1 2 ∑ b Π b X = 1 2 I , { 1 2 I } → X r → Y t { [ E ] } , I ⪯̸ 1 2 I . \begin{aligned}
\operatorname{wp}(d,[E])&=\sum_{b=0}^{1}\Pi_{b}^{X}\Pi_{b}^{Y}\Pi_{b}^{X}
=\frac{1}{2}\sum_{b}\Pi_{b}^{X}
=\frac{1}{2}I,\\
\left\{\frac{1}{2}I\right\}&\xrightarrow{X_{r}}\xrightarrow{Y_{t}}\{[E]\},
\qquad I\not\preceq\frac{1}{2}I.
\end{aligned} wp ( d , [ E ]) { 2 1 I } = b = 0 ∑ 1 Π b X Π b Y Π b X = 2 1 b ∑ Π b X = 2 1 I , X r Y t {[ E ]} , I ⪯ 2 1 I .
Every normalized input has agreement probability 1 / 2 1/2 1/2 . Soundness therefore rules out the desired precondition I I I , regardless of the proof-search strategy.
The same event witnesses a necessary approximation allowance. If a certificate related the optimized correct program to d d d with allowance ε \varepsilon ε , specification transfer would give 1 − ε ≤ 1 / 2 1-\varepsilon\le1/2 1 − ε ≤ 1/2 , hence ε ≥ 1 / 2 \varepsilon\ge1/2 ε ≥ 1/2 . The event proves only a lower bound on the uniform error. A matching upper bound would require a proof for every effect.
Verified compilation
Compilation replaces each source gate by a measurement program whose private outcomes are hidden from the caller, who observes only the data register and the public bits. Let π \pi π drop the two private bits a , b a,b a , b . A component c c c implements a source weakest-precondition transformer W W W when
∀ A . wp ( c , A ∘ π ) = ( W A ) ∘ π . (6) \forall A.\quad\operatorname{wp}(c,A\circ\pi)=(WA)\circ\pi. \tag*{(6)} ∀ A . wp ( c , A ∘ π ) = ( W A ) ∘ π . (6)
The equation quantifies over every initial value of the private bits, so sequential components can reuse the same two bits. For a unitary component, W ( A ) ( s ) = U † A ( s ) U W(A)(s)=U^{\dagger}A(s)U W ( A ) ( s ) = U † A ( s ) U . For a Clifford circuit with matrix U U U , composing the contracts of its gates gives output U ρ U † U\rho U^{\dagger} U ρ U † with the public store unchanged.
Implementing a universal gate set
Figure 5 gives measurement implementations of H , S , CNOT H,S,\operatorname{CNOT} H , S , CNOT . Equation (7) gives T T T injection. Each diagram shows individual Pauli measurements and corrections beside its QPM program. Each row declares its input registers. The caller supplies d d d (or c , t c,t c , t ). The distinct locations a , b a,b a , b are private. Each binder introduces the fresh qubit ν \nu ν shown on its circuit wire and discards it after the correction. Sequential scopes reuse the name for distinct qubits. Subscripts locate Pauli factors in the current context, and all others are I I I . Scopes retain classical writes. The output specification hides a , b a,b a , b .
Measuring X ν P X_\nu P X ν P and then Y ν Y_\nu Y ν , and correcting P P P when the outcomes differ, implements the matrix U ( P ) = Π P 0 + i Π P 1 U(P)=\Pi_P^0+i\Pi_P^1 U ( P ) = Π P 0 + i Π P 1 after discarding ν \nu ν . The identities U ( Z ) = S U(Z)=S U ( Z ) = S , U ( Z ) U ( X ) U ( Z ) = e i π / 4 H U(Z)U(X)U(Z)=e^{i\pi/4}H U ( Z ) U ( X ) U ( Z ) = e iπ /4 H , and U ( − Z c X t ) U ( X t ) U ( Z c ) = i CNOT c , t U(-Z_cX_t)U(X_t)U(Z_c)=i\operatorname{CNOT}_{c,t} U ( − Z c X t ) U ( X t ) U ( Z c ) = i CNOT c , t verify the Clifford sequences. Global phases cancel in conjugation, including the sign of the final CNOT correction. For T T T , supply ∣ M ⟩ = ( ∣ 0 ⟩ + e i π / 4 ∣ 1 ⟩ ) / 2 \lvert M\rangle=(\lvert0\rangle+e^{i\pi/4}\lvert1\rangle)/\sqrt{2} ∣ M ⟩ = (∣ 0 ⟩ + e iπ /4 ∣ 1 ⟩) / 2 on wire μ \mu μ . The conditional branch performs the explicit S S S sequence.
Theorem 2 (Clifford+T T T implementation by PPM). Every finite circuit over H H H , S S S , CNOT, T T T , with distinct control and target wires for each CNOT, has a QPPM implementation with the same channel on its data register. The implementation assumes one ideal ∣ M ⟩ \lvert M\rangle ∣ M ⟩ input per T T T gate. It uses basis-state ancillas, Pauli-product measurements, and conditional Pauli corrections, and hides its private outcomes and consumed magic-state qubits.
Proof. Each diagram implements its gate after summing over its private outcomes. § 5.3 proves the two-measurement contract, and § 5.2 proves the injection contract. The displayed matrix identities give H H H and CNOT. Induction on the source circuit composes these contracts. Each holds for every initial value of the private bits. Successive implementations can therefore reuse them. □
With the standard universality of Clifford+T T T [[5 ] ], which we take from the literature, this gives universal quantum computation with PPM and supplied magic states.
Clifford+T compilation with magic states
For data context Γ \Gamma Γ , let P P P be a signed product on Γ \Gamma Γ . Injection takes quantum inputs ( μ , Γ ) (\mu,\Gamma) ( μ , Γ ) , with μ ∉ Γ \mu\notin\Gamma μ ∈ / Γ , and distinct private locations a , b a,b a , b in Δ \Delta Δ . The map π \pi π removes a , b a,b a , b from the store. Set ω = e i π / 4 \omega=e^{i\pi/4} ω = e iπ /4 , ∣ M ⟩ = ( ∣ 0 ⟩ + ω ∣ 1 ⟩ ) / 2 |M\rangle=(|0\rangle+\omega|1\rangle)/\sqrt{2} ∣ M ⟩ = ( ∣0 ⟩ + ω ∣1 ⟩) / 2 , and T P = Π 0 P + ω Π 1 P T_P=\Pi^P_0+\omega\Pi^P_1 T P = Π 0 P + ω Π 1 P . The isometry V ψ = ∣ M ⟩ ⊗ ψ V\psi=|M\rangle\otimes\psi V ψ = ∣ M ⟩ ⊗ ψ supplies this magic state on μ \mu μ . Let C P C_P C P be the displayed QPPM body of the standard injection construction [24 ] .
Inside the local scope, the context is ( ν , μ , Γ ) (\nu,\mu,\Gamma) ( ν , μ , Γ ) . Products on the data act as identity on ν , μ \nu,\mu ν , μ . For a public assertion B B B , put D ( B ) ( s ) = I ⊗ B ( π ( s ) ) D(B)(s)=I\otimes B(\pi(s)) D ( B ) ( s ) = I ⊗ B ( π ( s )) . The circuit and its contract are
C P ≡ M Z μ P ( a ) ▹ if a then let ν = ancilla ∣ 0 ⟩ in ( M X ν P ( a ) ▹ M Y ν ( b ) ▹ if a ⊕ b then correct P else skip) ▹ else skip) ▹ M X μ ( b ) ▹ if b then correct P else skip (7) \begin{aligned}
C_P &\equiv M_{Z_\mu}P(a)\triangleright\\
&\quad\text{if }a\text{ then let }\nu=\text{ancilla }|0\rangle\text{ in}\\
&\qquad(M_{X_\nu}P(a)\triangleright M_{Y_\nu}(b)\triangleright\\
&\qquad\quad\text{if }a\oplus b\text{ then correct }P\text{ else skip) }\triangleright\\
&\quad\text{else skip)}\triangleright\\
&\quad M_{X_\mu}(b)\triangleright\\
&\quad\text{if }b\text{ then correct }P\text{ else skip} \tag*{(7)}
\end{aligned} C P ≡ M Z μ P ( a ) ▹ if a then let ν = ancilla ∣0 ⟩ in ( M X ν P ( a ) ▹ M Y ν ( b ) ▹ if a ⊕ b then correct P else skip) ▹ else skip) ▹ M X μ ( b ) ▹ if b then correct P else skip (7)
V † wp ( C P , D ( B ) ) ( s ) V = T P † B ( π ( s ) ) T P . V^\dagger\operatorname{wp}(C_P,D(B))(s)V=T_P^\dagger B(\pi(s))T_P. V † wp ( C P , D ( B )) ( s ) V = T P † B ( π ( s )) T P .
The dashed branch reads its guard before overwriting a , b a,b a , b . It is skipped when a = 0 a=0 a = 0 . Double end bars discard the fresh ancilla ν \nu ν . Once the inner phase gadget is summed to the unitary U ( P ) U(P) U ( P ) (its own eight branches are in § 5.3 ), the injection has eight effective Kraus branches, indexed by the joint outcome a a a , the readout b b b , and the basis index j j j of the consumed qubit μ \mu μ , which D ( B ) D(B) D ( B ) ignores. Each branch is a scalar multiple of T P T_P T P with squared magnitude 1 / 8 1/8 1/8 . Summing them proves the equation and the public output T P ρ T P † T_P\rho T_P^\dagger T P ρ T P † . Negating P P P gives the inverse action. Setting P = Z P=Z P = Z gives T T T . Induction extends the contract to a finite Clifford+T circuit c c c with public readouts. If c c c uses k k k injections, supply distinct inputs μ 0 , … , μ k − 1 \mu_0,\ldots,\mu_{k-1} μ 0 , … , μ k − 1 before its data register, set V k ψ = ∣ M ⟩ ⊗ k ⊗ ψ V_k\psi=|M\rangle^{\otimes k}\otimes\psi V k ψ = ∣ M ⟩ ⊗ k ⊗ ψ and D k ( B ) ( s ) = I ⊗ B ( π ( s ) ) D_k(B)(s)=I\otimes B(\pi(s)) D k ( B ) ( s ) = I ⊗ B ( π ( s )) , and let W c W_c W c compose the source instruction transformers. The compiler leaves each consumed qubit idle and keeps temporary basis ancillas scoped. Writing L ( c ) L(c) L ( c ) for the compiled QPPM program, we prove, for every assertion B B B and store s s s ,
V k † wp ( L ( c ) , D k ( B ) ) ( s ) V k = W c ( B ) ( π ( s ) ) . (8) V_k^\dagger\operatorname{wp}(L(c),D_k(B))(s)V_k=W_c(B)(\pi(s)). \tag*{(8)} V k † wp ( L ( c ) , D k ( B )) ( s ) V k = W c ( B ) ( π ( s )) . (8)
Hoare transfer is one application of Theorem 1 : if A ⊑ W c ( B ) A\sqsubseteq W_c(B) A ⊑ W c ( B ) , then Q = wp ( L ( c ) , D k ( B ) ) Q=\operatorname{wp}(L(c),D_k(B)) Q = wp ( L ( c ) , D k ( B )) satisfies ⊢ { Q } L ( c ) { D k ( B ) } \vdash\{Q\}L(c)\{D_k(B)\} ⊢ { Q } L ( c ) { D k ( B )} and A ( π ( s ) ) ⪯ V k † Q ( s ) V k A(\pi(s))\preceq V_k^\dagger Q(s)V_k A ( π ( s )) ⪯ V k † Q ( s ) V k for every s s s . Replacing ∣ M ⟩ |M\rangle ∣ M ⟩ by ∣ 0 ⟩ |0\rangle ∣0 ⟩ changes the transformer to B ↦ ∑ a Π a P B Π a P B\mapsto\sum_a\Pi^P_aB\Pi^P_a B ↦ ∑ a Π a P B Π a P . Thus the magic-state premise is necessary.
Correctness of the phase measurement sequence
Fix data inputs Γ \Gamma Γ , private locations a ≠ b a\ne b a = b , and a signed product P P P on Γ \Gamma Γ . The sequence of Figure 5 (a), with P P P in place of Z d Z_d Z d , binds a fresh zero ancilla ν \nu ν , measures X ⊗ P X\otimes P X ⊗ P into a a a and Y ⊗ I Y\otimes I Y ⊗ I into b b b , applies I ⊗ P I\otimes P I ⊗ P when the outcomes differ, and discards ν \nu ν . Let x , y ∈ { 0 , 1 } x,y\in\{0,1\} x , y ∈ { 0 , 1 } be the recorded values, j ∈ { 0 , 1 } j\in\{0,1\} j ∈ { 0 , 1 } the partial-trace index, and C x y = I ⊗ P x ⊕ y C_{xy}=I\otimes P^{x\oplus y} C x y = I ⊗ P x ⊕ y . The data-register Kraus operator of one branch is
K x y j = E j † C x y Π y Y ⊗ I Π x X ⊗ P E 0 . (9) K_{xyj}=E_j^\dagger C_{xy}\Pi_y^{Y\otimes I}\Pi_x^{X\otimes P}E_0. \tag*{(9)} K x y j = E j † C x y Π y Y ⊗ I Π x X ⊗ P E 0 . (9)
Boxes are linear maps composed left to right. The matrix product runs right to left. Set e = x ⊕ y e=x\oplus y e = x ⊕ y . Expanding the two projectors with the X X X and Y Y Y matrices and using P 2 = I P^2=I P 2 = I gives
K x y 0 = 1 4 P e ( I − i ( − 1 ) e P ) = 1 − i ( − 1 ) e 4 U ( P ) , K x y 1 = i ( − 1 ) y K x y 0 . K_{xy0}=\frac{1}{4}P^e\left(I-i(-1)^eP\right)=\frac{1-i(-1)^e}{4}U(P),\qquad K_{xy1}=i(-1)^yK_{xy0}. K x y 0 = 4 1 P e ( I − i ( − 1 ) e P ) = 4 1 − i ( − 1 ) e U ( P ) , K x y 1 = i ( − 1 ) y K x y 0 .
Thus K x y j = α x y j U ( P ) K_{xyj}=\alpha_{xyj}U(P) K x y j = α x y j U ( P ) with α x y j = [ i ( − 1 ) y j ] ( 1 − i ( − 1 ) x ⊕ y ) / 4 \alpha_{xyj}=[i(-1)^{y_j}](1-i(-1)^{x\oplus y})/4 α x y j = [ i ( − 1 ) y j ] ( 1 − i ( − 1 ) x ⊕ y ) /4 . Writing u = ( 1 − i ) / 4 u=(1-i)/4 u = ( 1 − i ) /4 and v = ( 1 + i ) / 4 v=(1+i)/4 v = ( 1 + i ) /4 , the eight coefficients are
and every entry has squared magnitude 1 / 8 1/8 1/8 . Summing the branches therefore gives
∑ x , y , j K x y j † B K x y j = U ( P ) † B U ( P ) , { S † B S } ⊑ { C S } ⊑ { B } ( P = Z ) . \sum_{x,y,j}K_{xyj}^{\dagger}BK_{xyj}=U(P)^{\dagger}BU(P),\qquad\{S^{\dagger}BS\}\mathrel{\sqsubseteq} \{C_S\}\mathrel{\sqsubseteq}\{B\}\quad(P=Z). x , y , j ∑ K x y j † B K x y j = U ( P ) † B U ( P ) , { S † B S } ⊑ { C S } ⊑ { B } ( P = Z ) .
Here B B B ignores the two private bits. Both are overwritten before the guard reads them, and public bits are preserved, so the contract holds for every initial value of the private bits. The proof retains the off-diagonal blocks of joint assertions, so the contract also holds when the data qubit is entangled with an idle qubit of the caller.
Verified optimization
The QPPM optimizer, denoted O \mathcal{O} O , combines measurement-run optimization, adjacent repetition and empty-scope cleanup, and lowering to unsigned products. A negative measurement becomes an unsigned measurement followed by a flip of its result bit. The sign of a correction can be removed because its two conjugating factors cancel the global sign.
The nonlocal rewrite follows a pending measurement through a sequence of measurements. It can cross a measurement of Q Q Q when P P P and Q Q Q commute and the intervening destination does not overwrite the pending result. A later measurement of the same signed P P P can then copy the saved result. The commutation test is executable and its matrix interpretation is proved. The intervening measurements need not commute with each other.
In Figure 6 , with inputs Γ = ( q 0 , q 1 ) \Gamma=(q_0,q_1) Γ = ( q 0 , q 1 ) and Δ = ( r 0 , r 1 , r 2 , r 3 ) \Delta=(r_0,r_1,r_2,r_3) Δ = ( r 0 , r 1 , r 2 , r 3 ) , the first measurement of Z ⊗ I Z\otimes I Z ⊗ I moves past I ⊗ X I\otimes X I ⊗ X and I ⊗ Z I\otimes Z I ⊗ Z , which anticommute with each other but commute with Z ⊗ I Z\otimes I Z ⊗ I . The two identical measurements are then adjacent, so the last is replaced by a copy. The result has three measurements and retains all four classical outcomes.
Figure 6. Measurement elimination in QPPM. Each outlined column is one measurement and the label below it names the destination bit. All four destinations are distinct. The first Z ⊗ I Z\otimes I Z ⊗ I measurement moves past I ⊗ X I\otimes X I ⊗ X and I ⊗ Z I\otimes Z I ⊗ Z , then its result replaces the final measurement. The green box is a classical assignment. The two rules preserve both the quantum output and every final bit.
With inputs Γ = ( q ) \Gamma=(q) Γ = ( q ) and Δ = ( r , t ) \Delta=(r,t) Δ = ( r , t ) , the following attempted rewrite copies a result that the middle measurement has overwritten:
I r − I r I t } r = 1 , t = 0 ≠ I r − I r t : = r } r = 1 , t = 1 \left.
\begin{array}{c}
I_r\\
-I_r\\
I_t
\end{array}
\right\}_{r=1,\ t=0}
\ne
\left.
\begin{array}{c}
I_r\\
-I_r\\
t:=r
\end{array}
\right\}_{r=1,\ t=1} I r − I r I t ⎭ ⎬ ⎫ r = 1 , t = 0 = I r − I r t := r ⎭ ⎬ ⎫ r = 1 , t = 1
The scanner stops at such overwrites and at noncommuting products. Assignments, corrections, conditionals, and scopes are scan barriers. The optimizer recursively visits conditional arms and scope bodies.
Theorem 3 (Exact optimization). For every c c c , O ( c ) ≡ c O(c)\equiv c O ( c ) ≡ c . The result uses only unsigned products and has no more syntactic measurement nodes than c c c . It has the same forward output matrix for each input store, input matrix, and final store, and the same derivable Hoare triples.
Proof. The rewrites in Figure 6 show that scanning preserves the pending measurement followed by its continuation, scan ( P , r , d ) ≡ M P ( r ) ▹ d \operatorname{scan}(P,r,d)\equiv M_P(r)\mathbin{\triangleright}d scan ( P , r , d ) ≡ M P ( r ) ▹ d , using projector commutation, record substitution, and repetition elimination. Sequence reassociation and structural induction lift the invariant to whole programs, and composition with the cleanup and sign-lowering passes proves the result. Count inequalities are proved separately by induction. Duality gives equality of every output block. Theorem 1 gives equivalence of the derivable Hoare specifications. □
The count adds both arms of a conditional.
Rotation fusion and scheduling
For the phase unitary U ( P ) = ( I + P ) / 2 + i ( I − P ) / 2 U(P)=(I+P)/2+i(I-P)/2 U ( P ) = ( I + P ) /2 + i ( I − P ) /2 , we prove U ( P ) 2 = P U(P)^2=P U ( P ) 2 = P and U ( P ) 4 = I U(P)^4=I U ( P ) 4 = I , so a quarter-turn count k ∈ { 0 , 1 , 2 , 3 } k\in\{0,1,2,3\} k ∈ { 0 , 1 , 2 , 3 } expands to skip, the two-measurement gadget, a Pauli correction, or the inverse gadget. We optimize these source rotations before expanding them to QPPM programs. Their component specifications hold for every signed product and register width. With data inputs Γ = ( q 0 , q 1 ) \Gamma=(q_0,q_1) Γ = ( q 0 , q 1 ) , put P = Z ⊗ I P=Z\otimes I P = Z ⊗ I and Q = I ⊗ Z Q=I\otimes Z Q = I ⊗ Z . The following diagram places each source unitary on its data wire. Commutation moves the first box. Adding turns modulo four removes the upper pair.
before
P = Z ⊗ I , Q = I ⊗ Z P=Z\otimes I,\ Q=I\otimes Z P = Z ⊗ I , Q = I ⊗ Z
U ( P ) ▹ U ( Q ) ▹ U ( P ) 3 U(P)\mathbin{\triangleright}U(Q)\mathbin{\triangleright}U(P)^3 U ( P ) ▹ U ( Q ) ▹ U ( P ) 3
swap
P Q = Q P PQ=QP P Q = QP
U ( Q ) ▹ U ( P ) ▹ U ( P ) 3 U(Q)\mathbin{\triangleright}U(P)\mathbin{\triangleright}U(P)^3 U ( Q ) ▹ U ( P ) ▹ U ( P ) 3
fuse
U ( P ) 4 = I U(P)^4=I U ( P ) 4 = I
U ( Q ) U(Q) U ( Q )
U ( P ) 4 = I (10) U(P)^4=I \tag*{(10)} U ( P ) 4 = I (10)
With two private ancillas, the parallel baseline groups the first two disjoint rotations, costing four logical rounds overall. The result costs two. Lean checks this derivation and both costs.
The scheduling checker replays each proposed edit after verifying its commutation and classical-dependency conditions, then compares the result with the proposed schedule. Induction proves equality of public weakest preconditions, and composing gadget contracts transfers every public Hoare specification and output block. Private measurement results may differ. Rotation motion stops at readouts, and swapping readouts requires distinct destinations.
For the two disjoint gadgets, allocation binds fresh v 0 , v 1 v_0,v_1 v 0 , v 1 and private locations Δ = ( a 0 , b 0 , a 1 , b 1 ) \Delta=(a_0,b_0,a_1,b_1) Δ = ( a 0 , b 0 , a 1 , b 1 ) . The labels J i J_i J i , R i R_i R i , and F i F_i F i denote the joint measurement into a i a_i a i , the ancilla readout into b i b_i b i , and the conditional correction of gadget i i i . Each wire groups a gadget’s data, ancilla, and private bits.
columns mark simultaneous logical rounds after three guarded exchanges:
gadget 0: J 0 R 0 F 0 ⟶ J 0 R 0 F 0 gadget 1: J 1 R 1 F 1 ⟶ J 1 R 1 F 1 four logical rounds two logical rounds (11) \begin{aligned}
\text{gadget 0:}\quad&J_0\quad R_0\quad F_0 &&\longrightarrow&& J_0\quad R_0\quad F_0\\
\text{gadget 1:}\quad&&J_1\quad R_1\quad F_1 &&\longrightarrow&& J_1\quad R_1\quad F_1\\
&\text{four logical rounds} &&&& \text{two logical rounds} \tag*{(11)}
\end{aligned} gadget 0: gadget 1: J 0 R 0 F 0 four logical rounds J 1 R 1 F 1 ⟶ ⟶ J 0 R 0 F 0 two logical rounds J 1 R 1 F 1 (11)
J 1 J_1 J 1 moves left across F 0 F_0 F 0 and R 0 R_0 R 0 . Then R 1 R_1 R 1 moves left across F 0 F_0 F 0 . Quantum commutation and independent result bits justify each exchange. The checker verifies disjoint supports, distinct private bits, and the ancilla budget, and we prove that the allocated program has the macros’ public weakest precondition. We charge two logical rounds per odd turn, one per readout, and zero for corrections. Routing and hardware timing remain outside this model.
Compilation of a complete circuit
The source has inputs Γ = ( q 0 , q 1 ) \Gamma= (q_0, q_1) Γ = ( q 0 , q 1 ) and Δ = ( ) \Delta= () Δ = ( ) . Figure 7 applies S S S to each qubit, CNOT from q 0 q_0 q 0 to q 1 q_1 q 1 , R θ = diag ( 1 , e i θ ) R_\theta= \operatorname{diag}(1, e^{i\theta}) R θ = diag ( 1 , e i θ ) to q 0 q_0 q 0 , and X X X to q 1 q_1 q 1 . Here θ = π / 2 + δ \theta= \pi/2 + \delta θ = π /2 + δ and δ = π / 2 26 \delta= \pi/2^{26} δ = π / 2 26 . We round R θ R_\theta R θ to S S S , then compile and optimize. Let U θ U_\theta U θ be its circuit matrix and W θ ( B ) = U θ † B U θ W_\theta(B) = U_\theta^\dagger B U_\theta W θ ( B ) = U θ † B U θ the source transformer and W 0 W_0 W 0 the rounded circuit’s transformer.
Figure 7. Source unitaries, rotations after certified rounding, and optimization. A split blue–orange box denotes U ( Z ⊗ X ) 3 U(Z \otimes X)^3 U ( Z ⊗ X ) 3 . Each dashed column costs two logical rounds. The unmarked X X X correction costs zero. The baseline already runs disjoint rotations in parallel. Figure 8 shows the individual Pauli measurements.
Step 1: certify the approximation. The bound ∣ e i θ − i ∣ ≤ δ < 2 − 24 \lvert e^{i\theta} - i\rvert\le\delta< 2^{-24} ∣ e i θ − i ∣ ≤ δ < 2 − 24 gives the conservative allowance ε = 16 ⋅ 2 − 24 = 2 − 20 < 9.54 × 10 − 7 \varepsilon= 16 \cdot2^{-24} = 2^{-20} < 9.54 \times10^{-7} ε = 16 ⋅ 2 − 24 = 2 − 20 < 9.54 × 1 0 − 7 : expanding ( S ⊗ I ) † B ( S ⊗ I ) − ( R θ ⊗ I ) † B ( R θ ⊗ I ) (S \otimes I)^\dagger B(S \otimes I) - (R_\theta\otimes I)^\dagger B(R_\theta\otimes I) ( S ⊗ I ) † B ( S ⊗ I ) − ( R θ ⊗ I ) † B ( R θ ⊗ I ) in matrix units gives sixteen terms, each of operator norm at most 2 − 24 2^{-24} 2 − 24 for an effect B B B . All other gates are exact, so − ε I ⊑ W θ ( B ) − W 0 ( B ) ⊑ ε I -\varepsilon I \sqsubseteq W_\theta(B) - W_0(B) \sqsubseteq\varepsilon I − ε I ⊑ W θ ( B ) − W 0 ( B ) ⊑ ε I for every two-qubit effect B B B , including observations on entangled inputs.
Step 2: expand the gates into measurement gadgets. Put P = Z ⊗ I P = Z \otimes I P = Z ⊗ I , Q = I ⊗ Z Q = I \otimes Z Q = I ⊗ Z , and R = I ⊗ X R = I \otimes X R = I ⊗ X , so P R = Z ⊗ X PR = Z \otimes X P R = Z ⊗ X . The S S S gates become U ( P ) U(P) U ( P ) or U ( Q ) U(Q) U ( Q ) , CNOT becomes U ( P ) ▹ U ( R ) ▹ U ( P R ) 3 U(P) \triangleright U(R) \triangleright U(PR)^3 U ( P ) ▹ U ( R ) ▹ U ( P R ) 3 , and X X X becomes the correction R R R . Each odd turn uses two measurements and feedback through the phase gadget. The expanded circuit therefore has twelve measurements.
Step 3: commute, fuse, and allocate. Since P P P commutes with Q Q Q , R R R , P R PR P R , move its three turns together and fuse them into U ( P ) 3 U(P)^3 U ( P ) 3 . Since R R R commutes with P R PR P R , move the final correction next to U ( R ) U(R) U ( R ) and fuse them into U ( R ) 3 U(R)^3 U ( R ) 3 . This gives
U ( Q ) ▹ U ( P ) 3 ▹ U ( R ) 3 ⏟ disjoint supports ▹ U ( P R ) 3 U(Q) \triangleright\underbrace{U(P)^3 \triangleright U(R)^3}_{\text{disjoint supports}} \triangleright U(PR)^3 U ( Q ) ▹ disjoint supports U ( P ) 3 ▹ U ( R ) 3 ▹ U ( P R ) 3
Six gadgets become four. The first two run in parallel. The others share q 1 q_1 q 1 and run in order (Figure 8 ), with at most two ancillas and four private bits. Against the parallel baseline, measurements fall from twelve to eight and depth from eight to six logical rounds, a 25% reduction. Pauli feedback costs zero logical rounds.
Figure 8. Inputs: Γ = ( q 0 , q 1 ) \Gamma= (q_0, q_1) Γ = ( q 0 , q 1 ) , Δ = ( r Q , s Q , r P , s P ) \Delta= (r_Q, s_Q, r_P, s_P) Δ = ( r Q , s Q , r P , s P ) , all bits private. Eight measurements occupy six rounds. The first two rounds use two fresh ancillas. Subsequent pairs each prepare and discard one ancilla. Double end bars denote discard. The later labels are aliases: ( r R , s R ) = ( r P R , s P R ) = ( r Q , s Q ) (r_R, s_R) = (r_{PR}, s_{PR}) = (r_Q, s_Q) ( r R , s R ) = ( r P R , s P R ) = ( r Q , s Q ) . The expression f j f_j f j abbreviates a guard, not a stored bit. A minus sign changes the measured product. Unsigned lowering implements it by flipping that measurement’s recorded bit.
Step 4: retain the specification and allowance. For the allocated program d d d , let π \pi π forget the four private bits. Exact rewriting and allocation give wp ( d , B ∘ π ) = W 0 ( B ) ∘ π \operatorname{wp}(d, B \mathbin{\circ} \pi) = W_0(B) \mathbin{\circ} \pi wp ( d , B ∘ π ) = W 0 ( B ) ∘ π . Thus every effect B B B and precondition A ⊑ W θ ( B ) A \sqsubseteq W_\theta(B) A ⊑ W θ ( B ) give
{ ( A − 2 − 20 I ) ∘ π } d { B ∘ π } . \{(A - 2^{-20}I) \mathbin{\circ} \pi\}\ d\ \{B \mathbin{\circ} \pi\}. {( A − 2 − 20 I ) ∘ π } d { B ∘ π } .
For every normalized input and initial private store, public effect expectations therefore differ from the source by at most 2 − 20 2^{-20} 2 − 20 . Optimization adds zero error.
Approximate compilation
An approximate implementation may change the probability of an observation. We bound this change uniformly over all effects. For commands of the same type, write c ≈ ε d c \approx_\varepsilon d c ≈ ε d when ε ≥ 0 \varepsilon\ge0 ε ≥ 0 and, for every effect B B B ,
wp ( c , B ) ⊑ wp ( d , B ) + ε I and wp ( d , B ) ⊑ wp ( c , B ) + ε I . \operatorname{wp}(c, B) \sqsubseteq\operatorname{wp}(d, B) + \varepsilon I
\quad\text{and}\quad
\operatorname{wp}(d, B) \sqsubseteq\operatorname{wp}(c, B) + \varepsilon I. wp ( c , B ) ⊑ wp ( d , B ) + ε I and wp ( d , B ) ⊑ wp ( c , B ) + ε I .
This relation bounds observations on the entire declared quantum register and the retained classical records, uniformly over the initial classical store. It is defined on the declared register only: a certified subroutine must be recertified when it is placed inside a larger register, and the per-rotation certificates of § 8.5 are therefore computed on the full register of each circuit. The following theorem uses this relation to transfer an exact Hoare specification to an approximate implementation.
Theorem 4 (Composition and specification transfer). Sequential approximation allowances add. Conditional approximations with the same guard use the maximum of their branch allowances. Applying the same ancilla preparation and scope to two approximated bodies preserves their allowance. If c ≈ ε d c \approx_{\varepsilon} d c ≈ ε d , ⊢ { A } c { B } \vdash\{A\}\ c\ \{B\} ⊢ { A } c { B } , and B B B is an effect, then ⊢ { A − ε I } d { B } \vdash\{A-\varepsilon I\}\ d\ \{B\} ⊢ { A − ε I } d { B } .
Proof. Composition uses effect preservation, monotonicity, and identity preservation: wp ( d ′ , B ) \operatorname{wp}(d',B) wp ( d ′ , B ) is an effect, wp ( c , ⋅ ) \operatorname{wp}(c,\cdot) wp ( c , ⋅ ) is monotone, and wp ( c , δ I ) = δ I \operatorname{wp}(c,\delta I)=\delta I wp ( c , δ I ) = δ I , so the two allowances add. The conditional selects one branch in each input store. For scopes, (W-Anc) lifts effects and preserves order. Hoare transfer follows from soundness, the first approximation inequality, and completeness. □
For an event guaranteed by an exact triple with precondition I I I , this yields probability at least 1 − ε 1-\varepsilon 1 − ε on positive trace-one inputs, and exact optimization preserves the relation, so applying O O O to both programs does not change the valid allowances.
Trace-distance interpretation. Let Δ ( t ) = I c ( s , ρ , t ) − I d ( s , ρ , t ) \Delta^{(t)}=\mathcal{I}_{c}(s,\rho,t)-\mathcal{I}_{d}(s,\rho,t) Δ ( t ) = I c ( s , ρ , t ) − I d ( s , ρ , t ) for a positive trace-one input, and let ∥ ⋅ ∥ 1 \lVert\cdot\rVert_{1} ∥ ⋅ ∥ 1 be the spectral trace norm. Then
c ≈ ε d ⟹ 1 2 ∑ t ∥ Δ ( t ) ∥ 1 ≤ ε . (12) c \approx_{\varepsilon} d \quad\Longrightarrow\quad\frac{1}{2}\sum_{t}\lVert\Delta^{(t)}\rVert_{1}\leq\varepsilon. \tag*{(12)} c ≈ ε d ⟹ 2 1 t ∑ ∥ Δ ( t ) ∥ 1 ≤ ε . (12)
The proof identifies the half-sum with the largest absolute expectation difference over store-indexed effects. Total trace preservation gives ∑ t tr ( Δ ( t ) ) = 0 \sum_{t}\operatorname{tr}(\Delta^{(t)})=0 ∑ t tr ( Δ ( t ) ) = 0 . Individual blocks need not have trace zero. Section 8.5 applies the composition theorem to synthesized rotations.
Adding logical implementation error
Synthesis error compares ideal programs. A noisy implementation needs a second bound. A transformer on the source register type is additive, order preserving, and fixes every scalar identity. The duals of trace-preserving channels, and the weakest-precondition maps of QPPM commands, are transformers. A location is an ideal transformer F i F_i F i , an implemented transformer F ~ i \widetilde{F}_i F i that includes its classical records, and a rate p i ≥ 0 p_i\geq0 p i ≥ 0 such that, for every effect B B B ,
F i ( B ) ⊑ F ~ i ( B ) + p i I , F ~ i ( B ) ⊑ F i ( B ) + p i I . F_i(B)\sqsubseteq\widetilde{F}_i(B)+p_iI,\qquad\widetilde{F}_i(B)\sqsubseteq F_i(B)+p_iI. F i ( B ) ⊑ F i ( B ) + p i I , F i ( B ) ⊑ F i ( B ) + p i I .
The contract concerns the complete declared register. A measured failure frequency or a code distance alone does not establish it.
Theorem 5 (Synthesis and logical noise). Let ℓ 1 , … , ℓ N \ell_1,\ldots,\ell_N ℓ 1 , … , ℓ N be a sequential list of locations on the source register type, with rates p 1 , … , p N p_1,\ldots,p_N p 1 , … , p N , and let W W W be the source transformer. Suppose that for every effect B B B the ideal composite F 1 ∘ ⋯ ∘ F N F_1\circ\cdots\circ F_N F 1 ∘ ⋯ ∘ F N is within ε \varepsilon ε of W W W in both inequalities above. If A ⊑ W ( B ) A\sqsubseteq W(B) A ⊑ W ( B ) and B B B is an effect, then A − ( ε + ∑ i p i ) I ⊑ ( F ~ 1 ∘ ⋯ ∘ F ~ N ) ( B ) A-(\varepsilon+\sum_i p_i)I\sqsubseteq(\widetilde{F}_1\circ\cdots\circ\widetilde{F}_N)(B) A − ( ε + ∑ i p i ) I ⊑ ( F 1 ∘ ⋯ ∘ F N ) ( B ) .
Proof. Replace one location at a time:
F 1 ⟶ F ~ 1 ⟶ F 2 ⟶ F ~ 2 ⟶ ⋯ ⟶ F ~ 1 ⟶ F ~ 2 . F_1 \longrightarrow\widetilde{F}_1 \longrightarrow F_2 \longrightarrow\widetilde{F}_2 \longrightarrow\cdots\longrightarrow\widetilde{F}_1 \longrightarrow\widetilde{F}_2. F 1 ⟶ F 1 ⟶ F 2 ⟶ F 2 ⟶ ⋯ ⟶ F 1 ⟶ F 2 .
The suffix preserves effects. The prefix preserves order and scalar allowances. Induction adds the local rates, then the synthesis allowance. □
The compiled program enters through Equation (8) , whose left side is a transformer on the source register type. The ideal F i F_i F i can therefore be the compressed transformers of compiled segments and ε \varepsilon ε their certified allowance. For N L N_L N L logical, N T N_T N T magic-state, and N I N_I N I idle locations with uniform rates p L , p T , p I p_L,p_T,p_I p L , p T , p I , the total allowance is ε + p L N L + p T N T + p I N I \varepsilon+p_LN_L+p_TN_T+p_IN_I ε + p L N L + p T N T + p I N I . The rates need not describe independent faults, because each contract must cover the state reaching its location. In the two-qubit example, with only measurements noisy at rate p L p_L p L , the 12-to-8 measurement reduction changes the allowance from 2 − 20 + 12 p L 2^{-20} + 12p_L 2 − 20 + 12 p L to 2 − 20 + 8 p L 2^{-20} + 8p_L 2 − 20 + 8 p L . A physical backend must also count routing, preparation, and idle locations and establish their contracts before it can determine whether reducing depth reduces error. An X X X fault with probability p p p after an ideal command is a location of rate p p p : its transformer B ↦ ( 1 − p ) B + p X B X B \mapsto(1-p)B + pXBX B ↦ ( 1 − p ) B + pX B X satisfies both inequalities because ( I − B ) + X B X (I-B) + XBX ( I − B ) + X B X and B + ( I − X B X ) B + (I-XBX) B + ( I − X B X ) are positive for every effect B B B .
Evaluation
We use complete QASMBench circuits to evaluate lowering, depth optimization, and approximation. A lowering certificate (§ 8.2 ) starts from a compiled gate sequence. A depth certificate (§ 8.3 ) checks a parallel schedule. A selection certificate (§ 8.4 ) checks an allowance against the requested limit. A source certificate (§ 8.5 ) also accounts for synthesis. Lean checks the certificates. External tools parse sources, synthesize gate sequences, and propose schedules. Magic states are ideal throughout. Every experiment includes mutation tests : deliberately corrupted certificates, such as an altered gate, an understated allowance, or an invalid swap, which the checker must reject. Appendices § 19 and § 20 derive full compilation proofs for cat_state_n4 and grover_n2, using the Hoare rules at every target step.
Compilation under a requested error limit
Algorithm 1 specifies the solid arrows in Figure 1 . Its input is a typed circuit c c c , an error limit ε u s e r ≥ 0 \varepsilon_{\mathrm{user}} \ge0 ε user ≥ 0 , an ancilla budget a ≥ 1 a \ge1 a ≥ 1 , and a finite ordered collection S S S of synthesis proposals. Each proposal supplies Clifford+T T T words and local error certificates, which the checks compose over the whole source before verifying the emitted target. A failed check discards the proposal. A requested synthesis tolerance alone is insufficient.
Algorithm 1 Certified compilation and depth selection
Require: c c c , ε u s e r \varepsilon_{\mathrm{user}} ε user , a a a , finite ordered collection S S S
Ensure: A QPPM implementation, a public-effect allowance, and a depth upper bound, or failure
V ← [ ] \mathcal{V} \leftarrow[\ ] V ← [ ]
for each proposal w ∈ S w \in S w ∈ S do
Check c → ε w c w c \xrightarrow{\varepsilon_w} c_w c ε w c w by local matrix bounds and their composition
continue if the check fails or ε w > ε u s e r \varepsilon_w > \varepsilon_{\mathrm{user}} ε w > ε user
Lower c w c_w c w to d w d_w d w using the verified gadgets and their magic-state contracts
Check the complete instruction sequence, public interface, and magic-state inputs
continue if the check fails
s d w ← sd_w \leftarrow s d w ← the proved serial depth bound of d w d_w d w
Propose exact rewrites and a schedule under budget a a a
Replay the rewrites and check allocation, feedback order, and the claimed depth
if this check succeeds then
( d w , s d w ) ← (d_w,sd_w) \leftarrow ( d w , s d w ) ← the checked optimized target and its depth bound
end if
Append ( d w , ε w , s d w ) (d_w,\varepsilon_w,sd_w) ( d w , ε w , s d w ) and its certificates to V \mathcal{V} V
end for
return failure if V = [ ] \mathcal{V} = [\ ] V = [ ]
return the first element with least s d w sd_w s d w
Every returned target meets the error limit by Theorem 4 , exact rewrites preserve it, and the selected depth is the smallest certified bound among the supplied proposals. If no proposal has checks, compilation fails. The artifact implements the checks in separate synthesis, lowering, and scheduling drivers, with Ross–Selinger synthesis proposals. The evaluation exercises the schedule step on Clifford circuits (§ 8.3 ) and the selection step on T T T -containing circuits with the serial bound alone (§ 8.4 ). Parallel scheduling of T T T injections is future work. The optional physical backend in the figure needs the contracts of § 7.1 in addition to this algorithm.
The greedy proposal algorithm for fusion and parallel scheduling scans backwards from each turn to an equal axis across commuting turns, adds exponents modulo four, and then fills layers of disjoint supports in source order up to the ancilla budget. It does not prove a minimum. All variants use the same layer costs and resource limit.
Lowering the Qiskit outputs
We select the 39 canonical small-suite QASMBench inputs [23 ] at revision 357b942 after excluding the three error-correction circuits. The selection is by application domain, independent of compilation results. Qiskit 2.3.1 compiles valid inputs to Clifford+T T T using Ross–Selinger synthesis [27 ] , optimization level 1, seed 0, and requested local tolerance 10 − 8 10^{-8} 1 0 − 8 . Four sources reference undeclared registers and fail parsing. Eight outputs contain only Clifford gates and Z Z Z readouts. Their expanded QPPM targets support the depth study below. The magic-state compiler handles 19 further outputs containing T T T gates, with one ideal magic state per T T T or inverse T T T . For each, we check the emitted instructions and apply the compilation theorem to obtain public Hoare specifications and static measurement bounds. The remaining eight outputs contain barriers, reset, or classical control, which this frontend does not accept: it takes only the gate set of Figure 5 with Z Z Z readouts, whereas the typed-source frontend of § 8.5 expands reset into a private measurement with a conditional correction and register guards into nested conditionals, and so covers those inputs. Eight mutation tests are rejected. A separate audit of the 56 large-suite inputs yields 23 complete source certificates and eleven depth certificates. At four ancillas, the 280-qubit Bernstein–Vazirani circuit falls from 1,069 to 715 logical rounds (33.1%) with zero approximation error.
Logical measurement depth
Table 1. Certified logical rounds with the same budget of four private gadget ancillas, for all eight complete Clifford circuits in the selected application suite. Inputs are the Qiskit optimization-level-1 outputs. The 19 T T T -containing lowering certificates are not included.
This experiment fixes synthesis error at zero and varies the ancilla budget. The eight expanded Clifford circuits contain 337 measurements in total. Measurement elimination removes two of them, both readouts of bb84_n8. Table 1 instead evaluates the rotation optimizer of § 6.1 under the scheduler of § 8.1 : the baseline schedules disjoint macros in parallel while preserving source order on overlapping supports. Commute relaxes that order when the checked swap permits it, and Fuse+commute also combines equal-axis turns. With matched budgets 1, 2, and 4, Lean checks 72 schedules across three variants. Certificates check source expansion, macro and primitive replay, scoped allocation, disjoint logical rounds, depth, and public weakest-precondition equality. Seventeen mutation tests are rejected.
At budget four, fusion plus commutation improves six cases by 11.8–28.6%. Two remain unchanged. The median reduction across all eight is 17.9%. Commutation alone changes one row, so most of the reduction comes from combining rotations before their expansion into measurements. Across the eight circuits, fusion reduces the expanded measurement count from 337 to 281 before readout cleanup. For learning parity with noise, budgets 1, 2, and 4 give baseline/optimized depths 43/31, 23/17, and 21/15. The optimizer does not reduce the number of magic states. The magic-input counts reported below are the T-counts of the emitted circuits. Repeating the compilation at Qiskit optimization level 3 produces the same gate sequences for these eight inputs. All 24 level-3 schedules are certified, and their depths equal the corresponding level-1 depths in Table 1. The comparison measures the contribution of our passes under one scheduler. We do not compare with an unverified PPM scheduler, so the baseline is our own pipeline. The depth model counts logical measurements and excludes routing and magic-state preparation latency.
Varying the requested error limit
We hold the complete typed expansion of q f t _ n 4 \mathrm{qft\_n4} qft_n4 fixed and vary ε u s e r \varepsilon_{\mathrm{user}} ε user over 10 − 2 10^{-2} 1 0 − 2 , 10 − 4 10^{-4} 1 0 − 4 , 10 − 6 10^{-6} 1 0 − 6 . Three candidate circuits use local synthesis tolerances 10 − 5 10^{-5} 1 0 − 5 , 10 − 7 10^{-7} 1 0 − 7 , 10 − 9 10^{-9} 1 0 − 9 for the non-exact phases. Each certificate covers all 41 source steps and four public readouts. The checker establishes the whole-circuit allowance ε ^ \hat{\varepsilon} ε ^ , the inequality ε ^ ≤ ε u s e r \hat{\varepsilon} \le\varepsilon_{\mathrm{user}} ε ^ ≤ ε user , and the serial depth bound s d ‾ = 6 n H + 6 n C X + 2 n S + 4 n T + n M \overline{\mathrm{sd}} = 6n_H + 6n_{\mathrm{CX}} + 2n_S + 4n_T + n_M sd = 6 n H + 6 n CX + 2 n S + 4 n T + n M , a gate-count formula (two logical rounds per phase gadget, four per injection, one per readout) rather than a parallel schedule. Candidates use one basis ancilla at a time. Ideal magic inputs are counted in the table.
Relaxing the limit from 10 − 6 10^{-6} 1 0 − 6 to 10 − 2 10^{-2} 1 0 − 2 lowers the selected depth bound by 43%. At 10 − 10 10^{-10} 1 0 − 10 , none of these candidates meets the requested limit, so the compiler returns no result. Other synthesis proposals might still meet it. For a requested limit of 10 − 3 10^{-3} 1 0 − 3 , the coarsest candidate is infeasible and the middle one is selected because 7,540 < 9,184. Its allowance bounds the change in the probability of any event on the four public readouts by 5.859 × 10 − 6 5.859 \times10^{-6} 5.859 × 1 0 − 6 . This experiment measures precision selection under serial bounds. Parallel scheduling of T T T injections is future work.
Source approximation allowances
We bound compilation error for all 35 valid typed source expansions in the selected suite, assuming ideal magic states. Their checked outputs are synthesized separately from the Qiskit outputs above. Eight Ross–Selinger certificates cover phases ± π / 2 k \pm\pi/2^k ± π / 2 k for k = 3 , 4 , 5 , 6 k = 3, 4, 5, 6 k = 3 , 4 , 5 , 6 , with 204–210 gates including 81–84 T or inverse-T gates. Lean checks exact Q ( 2 , i ) \mathbb{Q}(\sqrt{2}, i) Q ( 2 , i ) matrices, rational enclosures, and Taylor remainders, and derives an effect allowance below 1.263 × 10 − 7 1.263 \times10^{-7} 1.263 × 1 0 − 7 for each rotation on a selected wire of the full circuit register, including when it is entangled with the other wires.
The four-qubit QFT expansion contains 18 phase rotations. Its certificate adds the local synthesis allowances and preserves their sum through exact lowering, giving ε Q F T = 9 ε π / 4 + 6 ε π / 8 + 3 ε π / 16 < 1.132 × 10 − 6 \varepsilon_{\mathrm{QFT}} = 9\varepsilon_{\pi/4} + 6\varepsilon_{\pi/8} + 3\varepsilon_{\pi/16} < 1.132 \times10^{-6} ε QFT = 9 ε π /4 + 6 ε π /8 + 3 ε π /16 < 1.132 × 1 0 − 6 . Eighteen inputs have nonzero allowances. Table 3 reports the ten for which a numerical cross-check is available. The other eight (dnn_n8, qaoa_n6, inverseqft_n4, ipea_n2, pea_n5, qpe_n9, hhl_n7, and ising_n10) have certified allowances between 1.264 × 10 − 7 1.264 \times10^{-7} 1.264 × 1 0 − 7 and 4.057 × 10 − 5 4.057 \times10^{-5} 4.057 × 1 0 − 5 . Appendix § 21 derives the Ising guarantee step by step. Let c c c be the typed source, d d d its QPPM target, k k k the number of ideal magic inputs, s ~ \tilde{s} s ~ the store s s s extended by two zero private bits, and ε \varepsilon ε the certified allowance. For every effect B B B and store s s s , the certificate proves
Table 3. Nonzero approximation allowances for the typed source expansions with at most four qubits and no reset or classical control. Output instructions are the emitted Clifford+T T T instructions lowered to QPPM. The magic-input count is the T-count, with one ideal magic state per injection. The numeric distance d d d is the phase-free operator-norm distance between the source and output unitaries, computed in floating point.
− ε I ⊑ V k † wp ( d , D k ( B ) ) ( s ~ ) V k − W c ( B ) ( s ) ⊑ ε I . -\varepsilon I \sqsubseteq V_k^{\dagger}\operatorname{wp}(d,D_k(B))(\tilde{s})V_k-W_c(B)(s)\sqsubseteq\varepsilon I. − ε I ⊑ V k † wp ( d , D k ( B )) ( s ~ ) V k − W c ( B ) ( s ) ⊑ ε I .
This is the approximate form of Equation (8) . Theorem 1 then turns a source specification A ⊑ W c ( B ) A \sqsubseteq W_c(B) A ⊑ W c ( B ) into a target triple ⊢ { Q } d { D k ( B ) } \vdash\{Q\}\ d\ \{D_k(B)\} ⊢ { Q } d { D k ( B )} whose compressed precondition dominates A − ε I A-\varepsilon I A − ε I . The inverse-
QFT certificate includes six guarded phases and four public readouts, with each guard checked in both branches. The PEA certificate checks words prefixed by T or inverse T directly against ± 3 π / 8 \pm3\pi/8 ± 3 π /8 . Exact identities reduce X X X , Y Y Y , and general single-qubit rotations to phases, and macro expansion (SWAP in basis-Trotter, Qiskit’s legacy square-root-X convention in VQE) adds no error. Decimal radian literals denote exact rationals and π \pi π the mathematical constant. HHL uses both. Exported instruction sequences are compared with the source expansion. Parsing and macro inlining remain outside the proof.
How tight are the allowances? For the ten inputs with at most four qubits and no reset or classical control, we computed numerically (Qiskit, NumPy) the distance d = min ϕ ∥ U c − e i ϕ U d ∥ o p d = \min_{\phi}\lVert U_c-e^{i\phi}U_d\rVert_{\mathrm{op}} d = min ϕ ∥ U c − e i ϕ U d ∥ op between the source and the certified Clifford+T T T unitaries, readouts removed. The effect error that the certificate bounds lies between about d d d and 2 d 2d 2 d for small d d d , and the certified allowance exceeds d d d by a factor of 20 (wstate_n3) to 204 (dnn_n2). The slack has two sources: each per-rotation allowance applies a uniform bound to sixteen matrix-unit terms, costing up to a factor of 16 (§ 6.2 ), and the certificate adds local allowances along the circuit although the errors of successive rotations do not add coherently, so the ratio grows with the number of synthesized rotations. The numeric distance is a floating-point cross-check, not a certificate.
The other seventeen inputs compile exactly. Twelve use Clifford+T T T directly and three (adder, SAT, and Simon) admit exact macro expansion. These fifteen (seven with T T T gates) emit 603 instructions with zero error, and Simon’s two barriers are proved erasable. The remaining two are Bell and Shor. Shor preserves two resets, four register guards, and three readouts. Appendix § 16 derives its feedback contract. IPEA composes approximation with three resets, eleven guards, and four readouts. Mutation tests reject altered gates, guards, magic-input counts, and understated allowances in every certificate.
Appendix D works through the four-qubit adder and its measurement bound.
Mechanization and reproduction
The Lean audit permits only propositional extensionality, classical choice, and quotient soundness across the compilation, matrix, and spectral results, and it rejects proof holes and kernel bypasses. Table 4 separates the trusted components from the verified ones. A result is certified when the Lean kernel checks its certificate for one input. The theorems of § 3 –§ 7 are proved once for all inputs.
Table 4. Trust boundary of the pipeline. A proposal from the left column is accepted only when its certificate is checked by the right column.
The default build audits 1,476 theorems against these three assumptions with Lean and its mathematical library at version 4.29.1. An isolated rebuild of all 48 source files reuses only pinned third-party caches and checks source hashes. Reproduction has been tested on one Windows x86-64 machine (Intel Core i5-12400) with two prover workers per check.
Of 7,739 physical lines, 317 define the syntax, semantics, and logic, with seven commands and eight rule constructors. Supplemental certificates are checked and axiom-audited separately.
Limitations
The parallel depth study excludes T T T injections. The QFT selection instead uses serial depth upper bounds. Neither includes layout, code distance, or magic-state production. Depth selection compares only the supplied proposals and schedules and does not establish a global minimum. We do not compare against an unverified PPM scheduler, so our baseline is our own pipeline. The optimizer does not reduce the number of magic states. Parsing and macro expansion are compared with exported sequences but remain unverified. The logical-noise theorem composes supplied contracts. It does not certify physical error rates for a surface-code or lifted-product backend.
Related work
Quantum program logics. D’Hondt and Panangaden [ [14 ] introduced quantum weakest preconditions as duals of completely positive maps. Ying [ [34 ] proved Hoare-logic soundness and relative completeness, and Feng and Ying [ [15 ] added the store-indexed assertions we adopt. QPPM specializes these logics to terminating measurement programs to verify compilation optimization. Unruh [ [29 ] adds ghost variables entangled with program variables. We express the magic-state premise through compression V k V_k V k of the compiled precondition. Relational quantum Hoare logic [2 ] uses couplings, and aQHL [37 ] gives error-robustness rules. Our uniform effect bound ≈ ε \approx\varepsilon ≈ ε weakens Hoare triples by a scalar and composes through classical control. Unlike the predicate-constrained diamond distance of Hung et al. [ [21 ] , it covers only the declared register and store. Its reference-system extension remains open. CoqQ mechanizes local and parallel reasoning [36 ] , and CoqQLR uses distribution formulas [33 ] . Neither hides reusable result bits behind a component contract.
Verified compilers and circuit languages. VOQC verifies gate-level optimizations against matrix semantics [19 ] , and SQIR proves algorithms correct in the same framework [18 ] . QWIRE embeds a typed circuit language in Coq [26 ] , Qbricks automates proofs of parametric circuit families [Chareton et al. 2021], and CertiQ verifies Qiskit passes by SMT solving [28 ] . These developments treat gates as unitaries. QPPM transformations are verified at the measurement level, where feedback and private outcomes are part of the semantics. The measurement calculus [13 ] gives compositional semantics for measurement-based computation. QPPM restricts to lattice-surgery operations and adds Hoare specifications. Booth and Comfort [ [4 ] give fully abstract semantics for stabiliser programs. QPPM’s complex-matrix instruments additionally support T T T injection and approximate synthesis.
Pauli-based and lattice-surgery compilation. Bravyi et al. [ [6 ] execute Clifford+T T T circuits as adaptive Pauli-product measurements on magic states. Litinski [ [24 ] gives a lattice-surgery instruction set and the rotation fusion and commutation rules used in § 6.1 . We verify these rules and check proposed schedules on complete circuits. Paler and Basmadjian [ [25 ] schedule T T T gates using queueing models, and Beverland et al. [ [3 ] route operations along edge-disjoint paths. The Lattice Surgery Compiler [31 ] and LeBlond et al. [2024] place surface-code operations and estimate resources. Our logical depth model excludes their layout and routing costs. Wakizaka et al. [ [30 ] verify path availability. CircLS lowers PPMs to physical circuits and checks them by simulation [35 ] . These checks address physical implementation. Our proof establishes source-to-PPM semantic preservation. Cowtan et al. [ [10 ] synthesise phase gadgets for shallow circuits. Our rotation fusion handles commuting equal-axis turns and is proved exact. T T T -count reduction [1 , 17 ] reduces magic-state consumption, which our optimizer leaves unchanged.
Conclusion
QPPM’s Hoare logic verifies measurement-based compilation and optimization, transfers specifications through approximate synthesis and logical noise, and certifies complete QASMBench circuits. Physical backends, broader source coverage, and parameterized circuits remain future work.
AI-ASSISTANCE STATEMENT
OpenAI Codex was used to generate and revise Lean definitions and proofs, investigate literature, and draft and revise the manuscript. Lean checked the formal development, including the proof-dependency audit in § 8.6 .
DATA-AVAILABILITY STATEMENT
Artifact: https://anonymous.4open.science/r/PPMCompilation-FE38/ . The artifact contains the Lean development, compiler passes, pinned benchmark inputs, certificates, proof audit, dependency versions, and instructions for reproducing the proofs and evaluation. We plan to submit the artifact for Artifact Evaluation when the paper becomes eligible.
References
A fresh qubit: execution, precondition, and scope rule
With inputs Γ = ( ) \Gamma= () Γ = ( ) and Δ = ( r ) \Delta= (r) Δ = ( r ) , the program f = let ν = ancilla ∣ 0 ⟩ in M X ν ( r ) f = \text{let } \nu= \text{ancilla } |0\rangle\text{ in } M_{X_\nu}(r) f = let ν = ancilla ∣0 ⟩ in M X ν ( r ) returns one bit and no quantum register. Its input state is the scalar 1 1 1 , viewed as a 1 × 1 1 \times1 1 × 1 density matrix. The scope changes the quantum width from zero to one for the duration of its body. Inside this one-qubit scope, X ν = X X_\nu= X X ν = X and Z ν = Z Z_\nu= Z Z ν = Z . The inclusion matrices and the measurement projectors are
E 0 = ( 1 0 ) , E 1 = ( 0 1 ) , Π 0 X = 1 2 ( 1 1 1 1 ) , Π 1 X = 1 2 ( 1 − 1 − 1 1 ) . E_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad E_1 = \begin{pmatrix} 0 \\ 1 \end{pmatrix}, \qquad\Pi_0^X = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}, \qquad\Pi_1^X = \frac{1}{2}\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}. E 0 = ( 1 0 ) , E 1 = ( 0 1 ) , Π 0 X = 2 1 ( 1 1 1 1 ) , Π 1 X = 2 1 ( 1 − 1 − 1 1 ) .
Step 1: prepare, measure, and discard. Preparation gives E 0 1 E 0 † = Q 0 E_0 1 E_0^\dagger= Q_0 E 0 1 E 0 † = Q 0 . The two paths are
Q 0 → X , r = 0 1 4 ( 1 1 1 1 ) → drop 1 2 , Q 0 → X , r = 1 1 4 ( 1 − 1 − 1 1 ) → drop 1 2 . Q_0 \xrightarrow{X,\ r=0} \frac{1}{4}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \xrightarrow{\operatorname{drop}} \frac{1}{2}, \qquad
Q_0 \xrightarrow{X,\ r=1} \frac{1}{4}\begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix} \xrightarrow{\operatorname{drop}} \frac{1}{2}. Q 0 X , r = 0 4 1 ( 1 1 1 1 ) drop 2 1 , Q 0 X , r = 1 4 1 ( 1 − 1 − 1 1 ) drop 2 1 .
For a one-qubit matrix H H H , discarding the only qubit gives E 0 † H E 0 + E 1 † H E 1 = H 00 + H 11 E_0^\dagger H E_0 + E_1^\dagger H E_1 = H_{00} + H_{11} E 0 † H E 0 + E 1 † H E 1 = H 00 + H 11 . Thus both displayed matrices yield the scalar 1 / 2 1/2 1/2 . These are the two final-store blocks I f ( s , 1 , s [ r ↦ b ] ) I_f(s,1,s[r \mapsto b]) I f ( s , 1 , s [ r ↦ b ]) , for b = 0 , 1 b = 0,1 b = 0 , 1 . The qubit disappears, but the record distinguishes the branches.
Step 2: calculate backwards from a recorded one. Let F ( s ) = [ s ( r ) = 1 ] F(s) = [s(r) = 1] F ( s ) = [ s ( r ) = 1 ] be the scalar event. Lifting through discard gives drop ∗ ( F ) ( s ) = I 2 F ( s ) \operatorname{drop}^*(F)(s) = I_2F(s) drop ∗ ( F ) ( s ) = I 2 F ( s ) . By (W-Meas) and (W-Anc), the body updates r r r before evaluating this assertion:
wp ( M X ( r ) , drop ∗ ( F ) ) ( s ) = Π 0 X ( 0 I 2 ) Π 0 X + Π 1 X ( I 2 ) Π 1 X = Π 1 X . \operatorname{wp}(M_X(r),\operatorname{drop}^*(F))(s) = \Pi_0^X(0I_2)\Pi_0^X + \Pi_1^X(I_2)\Pi_1^X = \Pi_1^X. wp ( M X ( r ) , drop ∗ ( F )) ( s ) = Π 0 X ( 0 I 2 ) Π 0 X + Π 1 X ( I 2 ) Π 1 X = Π 1 X .
prep 0 ∗ ( Π 1 X ) = E 0 † Π 1 X E 0 = ( 1 0 ) 1 2 ( 1 − 1 − 1 1 ) ( 1 0 ) = 1 2 . \operatorname{prep}_0^*(\Pi_1^X) = E_0^\dagger\Pi_1^X E_0 = (1\ \ 0)\frac{1}{2}\begin{pmatrix}1 & -1 \\ -1 & 1\end{pmatrix}\begin{pmatrix}1 \\ 0\end{pmatrix} = \frac{1}{2}. prep 0 ∗ ( Π 1 X ) = E 0 † Π 1 X E 0 = ( 1 0 ) 2 1 ( 1 − 1 − 1 1 ) ( 1 0 ) = 2 1 .
Consequently wp ( f , F ) = 1 / 2 \operatorname{wp}(f,F) = 1/2 wp ( f , F ) = 1/2 , matching the lower forward branch. For an arbitrary scalar assertion A A A , the same calculation replaces 0 , 1 0,1 0 , 1 by A ( s [ r ↦ 0 ] ) , A ( s [ r ↦ 1 ] ) A(s[r \mapsto0]), A(s[r \mapsto1]) A ( s [ r ↦ 0 ]) , A ( s [ r ↦ 1 ]) and gives Equation (28) .
Step 3: apply the scope rule. Rule H-Prim supplies the premise of H-Anc. The compression just calculated supplies the conclusion’s precondition:
{ Π 1 X } → X r { drop ∗ ( F ) } \{ \Pi_1^X \} \xrightarrow{X_r} \{ \operatorname{drop}^*(F) \} { Π 1 X } X r { drop ∗ ( F )}
{ 1 2 } → ∣ 0 ⟩ → X r → drop { F } . \left\{ \frac{1}{2} \right\} \xrightarrow{|0\rangle} \xrightarrow{X_r} \xrightarrow{\operatorname{drop}} \{F\}. { 2 1 } ∣0 ⟩ X r drop { F } .
The boxes for preparation and discard show the scope boundary, rather than additional commands in the grammar. The triple gives a lower bound of 1 / 2 1/2 1/2 for recording one. The exact weakest-precondition calculation gives equality.
The initialization bit also has an observable role. Replacing X X X by Z Z Z gives prep b ∗ ( Π 1 Z ) = b \operatorname{prep}_b^*(\Pi_1^Z) = b prep b ∗ ( Π 1 Z ) = b for b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } . Thus let ν = ancilla ∣ 0 ⟩ in M Z ν ( r ) \text{let } \nu= \text{ancilla } |0\rangle\text{ in } M_{Z_\nu}(r) let ν = ancilla ∣0 ⟩ in M Z ν ( r ) always records zero, whereas let ν = ancilla ∣ 1 ⟩ in M Z ν ( r ) \text{let } \nu= \text{ancilla } |1\rangle\text{ in } M_{Z_\nu}(r) let ν = ancilla ∣1 ⟩ in M Z ν ( r ) always records one.
Names and register positions. The binder makes the qubit in the diagram available by name inside its body. With inputs Γ = ( d ) \Gamma= (d) Γ = ( d ) and Δ = ( r ) \Delta= (r) Δ = ( r ) , consider
c = let ν = ancilla ∣ 0 ⟩ in M X ν Z d ( r ) . c = \text{let } \nu= \text{ancilla } |0\rangle\text{ in } M_{X_{\nu}Z_{d}}(r). c = let ν = ancilla ∣0 ⟩ in M X ν Z d ( r ) .
Γ = ( d ) , ( ν , Γ ) = ( ν , d ) , \Gamma= (d), \qquad(\nu,\Gamma) = (\nu,d), Γ = ( d ) , ( ν , Γ ) = ( ν , d ) ,
d ↦ 0 , ν ↦ 0 , d ↦ 1 , d \mapsto0,\qquad\nu\mapsto0,\qquad d \mapsto1, d ↦ 0 , ν ↦ 0 , d ↦ 1 ,
X ν Z d = X ⊗ Z . X_{\nu}Z_{d} = X \otimes Z. X ν Z d = X ⊗ Z .
Names in a context are distinct, and each bound name is fresh for the surrounding context. Tensor factors follow context order. Omitted factors are I I I . If an inner scope binds a fresh μ \mu μ , the context becomes ( μ , ν , d ) (\mu,\nu,d) ( μ , ν , d ) : the same product X ν Z d X_{\nu}Z_{d} X ν Z d then denotes I ⊗ X ⊗ Z I \otimes X \otimes Z I ⊗ X ⊗ Z . The inner scope discards μ \mu μ and restores ( ν , d ) (\nu,d) ( ν , d ) . The outer scope discards ν \nu ν and restores ( d ) (d) ( d ) . Thus a name continues to refer to the same qubit when its position changes.
Signs and classical expressions
With inputs Γ = ( q ) \Gamma= (q) Γ = ( q ) and Δ = ( r ) \Delta= (r) Δ = ( r ) , take the signed product P = − Z P = -Z P = − Z , so its sign bit is η = 1 \eta= 1 η = 1 and its single factor is Z Z Z . Its projectors exchange those of Z Z Z : Π b − Z = ( I + ( − 1 ) b ( − Z ) ) / 2 = Π 1 − b Z \Pi_b^{-Z} = (I + (-1)^b(-Z))/2 = \Pi_{1-b}^{Z} Π b − Z = ( I + ( − 1 ) b ( − Z )) /2 = Π 1 − b Z . Unsigned lowering therefore has the following concrete instance:
measurement of − Z on r ≡ measurement of Z on r ; r : = ¬ r . \text{measurement of }-Z\text{ on }r \equiv\text{measurement of }Z\text{ on }r;\qquad r := \neg r. measurement of − Z on r ≡ measurement of Z on r ; r := ¬ r .
On input Q 0 = ∣ 0 ⟩ ⟨ 0 ∣ Q_0 = |0\rangle\langle0| Q 0 = ∣0 ⟩ ⟨ 0∣ , the left circuit records one with output Q 0 Q_0 Q 0 . The right circuit first records zero, then changes the record to one. For any postcondition A A A , (W-Seq), (W-Asgn), and (W-Meas) give
wp ( M Z ( r ) ▹ r : = ¬ r , A ) ( s ) = ∑ b = 0 1 Q b A ( s [ r ↦ 1 − b ] ) Q b = ∑ a = 0 1 Π a − Z A ( s [ r ↦ a ] ) Π a − Z . \operatorname{wp}(M_Z(r) \mathbin{\triangleright} r := \neg r,A)(s)
= \sum_{b=0}^{1} Q_b A(s[r \mapsto1-b])Q_b
= \sum_{a=0}^{1} \Pi_a^{-Z} A(s[r \mapsto a])\Pi_a^{-Z}. wp ( M Z ( r ) ▹ r := ¬ r , A ) ( s ) = b = 0 ∑ 1 Q b A ( s [ r ↦ 1 − b ]) Q b = a = 0 ∑ 1 Π a − Z A ( s [ r ↦ a ]) Π a − Z .
The second equality changes the index to a = 1 − b a = 1-b a = 1 − b . In (W-Corr), the sign cancels without changing the store: ( − X ) A ( s ) ( − X ) = X A ( s ) X (-X)A(s)(-X) = XA(s)X ( − X ) A ( s ) ( − X ) = X A ( s ) X . Hence − X ≡ X -X \equiv X − X ≡ X as correction commands.
Literal, read, negation, and exclusive-or expressions can all be checked on this short classical program, with inputs Γ = ( ) \Gamma= () Γ = ( ) and Δ = ( r , t , u ) \Delta= (r,t,u) Δ = ( r , t , u ) . Each annotation shows the updated store:
r : = 0 r = 0 r := 0 \qquad r=0 r := 0 r = 0
t : = 1 r = 0 , t = 1 t := 1 \qquad r=0,\ t=1 t := 1 r = 0 , t = 1
r : = ¬ read r r = 1 , t = 1 r := \neg\operatorname{read} r \qquad r=1,\ t=1 r := ¬ read r r = 1 , t = 1
u : = ( read r ) ⊕ ( read t ) r = 1 , t = 1 , u = 0 u := (\operatorname{read} r) \oplus(\operatorname{read} t) \qquad r=1,\ t=1,\ u=0 u := ( read r ) ⊕ ( read t ) r = 1 , t = 1 , u = 0
For the last assignment and event [ u = 0 ] [u = 0] [ u = 0 ] , H-PRIM and (W-Asgn) give [ s ( r ) ⊕ s ( t ) = 0 ] [s(r) \oplus s(t) = 0] [ s ( r ) ⊕ s ( t ) = 0 ] , which is true at its displayed input store. In the phase gadget with inputs Γ = ( d ) \Gamma= (d) Γ = ( d ) , Δ = ( a , b ) \Delta= (a,b) Δ = ( a , b ) , the same exclusive-or expression controls a quantum correction: the outcomes ( a , b ) = ( 0 , 1 ) (a,b) = (0,1) ( a , b ) = ( 0 , 1 ) give a ⊕ b = 1 a \oplus b = 1 a ⊕ b = 1 , so the circuit applies Z Z Z . The outcomes ( 1 , 1 ) (1,1) ( 1 , 1 ) give zero, so it skips the correction.
Shor's circuit: register guards and qubit reuse
The QASMBench input shor_n5 uses iterative phase estimation. It reuses one qubit for three readouts and chooses later phase gates from earlier outcomes. Declare quantum inputs Γ = ( q 0 , … , q 4 ) \Gamma= (q_0,\ldots,q_4) Γ = ( q 0 , … , q 4 ) , public locations Δ = ( c 0 , … , c 4 ) \Delta= (c_0,\ldots,c_4) Δ = ( c 0 , … , c 4 ) , and private locations u , v ∉ Δ u,v \notin\Delta u , v ∈ / Δ . Only c 0 , c 1 , c 2 c_0,c_1,c_2 c 0 , c 1 , c 2 are written. The unused public bits still participate in the source’s register comparisons. The proof therefore covers arbitrary initial values of all five bits.
Step 1: expose the finite source. Figure 9 shows the three stages in execution order. The joint blocks abbreviate
Figure 9. The complete five-qubit Shor source, read one stage at a time from top to bottom. A four-qubit bus carries the data register. Qubit q 4 q_4 q 4 is measured and reset between stages. Green conditions test the full public register w = c 0 + 2 c 1 + 4 c 2 + 8 c 3 + 16 c 4 w = c_0 + 2c_1 + 4c_2 + 8c_3 + 16c_4 w = c 0 + 2 c 1 + 4 c 2 + 8 c 3 + 16 c 4 . Blue phase gates are the exact words for the source angles. The joint blocks U 2 , U 3 U_2,U_3 U 2 , U 3 are defined in the text.
U 2 = CNOT 4 , 2 ▹ CNOT 4 , 0 , U 3 = CSWAP 4 , 1 , 0 ▹ CSWAP 4 , 2 , 1 ▹ CSWAP 4 , 3 , 2 ▹ CNOT 4 , 3 ▹ CNOT 4 , 2 ▹ CNOT 4 , 1 ▹ CNOT 4 , 0 . \begin{aligned}
U_2 &= \operatorname{CNOT}_{4,2} \triangleright\operatorname{CNOT}_{4,0},\\
U_3 &= \operatorname{CSWAP}_{4,1,0} \triangleright\operatorname{CSWAP}_{4,2,1} \triangleright\operatorname{CSWAP}_{4,3,2}\\
&\quad\triangleright\operatorname{CNOT}_{4,3} \triangleright\operatorname{CNOT}_{4,2} \triangleright\operatorname{CNOT}_{4,1} \triangleright\operatorname{CNOT}_{4,0}.
\end{aligned} U 2 U 3 = CNOT 4 , 2 ▹ CNOT 4 , 0 , = CSWAP 4 , 1 , 0 ▹ CSWAP 4 , 2 , 1 ▹ CSWAP 4 , 3 , 2 ▹ CNOT 4 , 3 ▹ CNOT 4 , 2 ▹ CNOT 4 , 1 ▹ CNOT 4 , 0 .
Each controlled swap expands into its standard Clifford+T T T sequence. The 25 source statements become 73 typed steps. The complete certificate retains both resets, all four phase guards, and all three readouts.
Step 2: lower reset without erasing public outcomes. Put Q b = Π q 4 Z Q_b = \Pi_{q_4}^{Z} Q b = Π q 4 Z and X 4 = X q 4 X_4 = X_{q_4} X 4 = X q 4 . A reset uses the private bit u u u :
For an assertion B B B that reads only Δ \Delta Δ , substitution removes the private record. Measurement and conditional give
wp ( reset0 ( q 4 ) , B ) ( s ) = Q 0 B ( s ) Q 0 + Q 1 X 4 B ( s ) X 4 Q 1 . \operatorname{wp}(\operatorname{reset0}(q_4),B)(s) = Q_0B(s)Q_0 + Q_1X_4B(s)X_4Q_1. wp ( reset0 ( q 4 ) , B ) ( s ) = Q 0 B ( s ) Q 0 + Q 1 X 4 B ( s ) X 4 Q 1 .
These are the two Kraus terms for replacing q 4 q_4 q 4 by ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ . In particular, the first reset leaves c 0 c_0 c 0 available to the next stage. The second leaves both c 0 , c 1 c_0,c_1 c 0 , c 1 available. This is the reset derivation of § 3.2 , instantiated on a reused algorithm qubit.
Step 3: derive a whole-register guard. Write w ( s ) = ∑ j = 0 4 2 j s ( c j ) w(s) = \sum_{j=0}^{4} 2^j s(c_j) w ( s ) = ∑ j = 0 4 2 j s ( c j ) , interpreting each Boolean as zero or one, and R θ = diag ( 1 , e i θ ) R_\theta= \operatorname{diag}(1,e^{i\theta}) R θ = diag ( 1 , e i θ ) on q 4 q_4 q 4 . The last guarded phase, G 1 G_1 G 1 , executes R π / 4 = T R_{\pi/4} = T R π /4 = T only when w = 1 w = 1 w = 1 . Its core guard is five nested bit tests. A true c 0 c_0 c 0 continues to the next test, each of c 1 , … , c 4 c_1,\ldots,c_4 c 1 , … , c 4 must be false, and every other branch skips. Repeated use of (W-If) gives
W G 1 ( B ) ( s ) = { T † B ( s ) T s ( c 0 ) = 1 , s ( c 1 ) = ⋯ = s ( c 4 ) = 0 , B ( s ) otherwise. W_{G_1}(B)(s) =
\begin{cases}
T^\dagger B(s)T & s(c_0)=1,\ s(c_1)=\cdots=s(c_4)=0,\\
B(s) & \text{otherwise.}
\end{cases} W G 1 ( B ) ( s ) = { T † B ( s ) T B ( s ) s ( c 0 ) = 1 , s ( c 1 ) = ⋯ = s ( c 4 ) = 0 , otherwise.
Here T T T is the gate matrix on q 4 q_4 q 4 . Its exact measurement implementation has the same public weakest precondition after resource compression. The required magic input is the same as for an unconditional injection.
The preceding guards execute R π / 2 = S R_{\pi/2}=S R π /2 = S when w = 2 w=2 w = 2 and R 3 π / 4 = S T R_{3\pi/4}=ST R 3 π /4 = S T when w = 3 w=3 w = 3 . None writes a public location. Their conditions are disjoint, so sequencing gives a calculation for every initial store:
Table 1 (PDF p. 29).
The last row checks why the unused high bits cannot be dropped from the guards. The earlier w = 1 w=1 w = 1 guard is derived in the same way, with S S S in place of T T T .
Step 4: compose the complete contract. The exact phase words produce 74 instructions and require k = 23 k=23 k = 23 ideal magic inputs. Let c c c be the complete typed source and d d d its QPPM target. For any public postcondition B B B , set A = W c ( B ) A=W_c(B) A = W c ( B ) . Composition gives
⊢ { Q } d { D k ( B ) } , V k † Q ( σ ) V k = A ( π ( σ ) ) , ε = 0. \vdash\{Q\}\,\boxed{d}\,\{D_k(B)\}, \qquad V_k^\dagger Q(\sigma)V_k=A(\pi(\sigma)), \qquad\varepsilon=0. ⊢ { Q } d { D k ( B )} , V k † Q ( σ ) V k = A ( π ( σ )) , ε = 0.
The equality covers the whole circuit, including both resets and all feedback branches. It preserves the source specification for every input state and public store. Parsing and controlled-swap expansion are compared with the exported source and remain outside the proof. This case contributes a source certificate, with no parallel-depth claim.
D An arithmetic source: the four-qubit adder
The QASMBench input adder_n4 is already expressed in Clifford+T T T . Declare Γ = ( q 0 , q 1 , q 2 , q 3 ) \Gamma=(q_0,q_1,q_2,q_3) Γ = ( q 0 , q 1 , q 2 , q 3 ) and Δ = ( r 0 , r 1 , r 2 , r 3 ) \Delta=(r_0,r_1,r_2,r_3) Δ = ( r 0 , r 1 , r 2 , r 3 ) . Figure 10 contains all 27 source instructions, including the two initial X gates and four final readouts.
Figure 10. The complete four-qubit adder source. Panel (b) continues panel (a). Orange boxes apply X, including the targets of CNOTs. Blue phase gates rotate about Z. All four public outputs are retained by the compiled QPPM program.
Step 1: count the component contracts. The source has two X gates, two H gates, ten CNOTs, one S gate, eight T or inverse-T gates, and four Z readouts. The X gates compile to corrections. Each H and CNOT uses six measurements, each S uses two, and each injection uses four. Therefore
A d d e r 4 → ε = 0 d a d d , 6 ⋅ 2 + 6 ⋅ 10 + 2 ⋅ 1 + 4 ⋅ 8 + 4 = 110. \boxed{\mathrm{Adder}_4}\xrightarrow{\varepsilon=0}\boxed{d_{\mathrm{add}}}, \qquad6\cdot2+6\cdot10+2\cdot1+4\cdot8+4=110. Adder 4 ε = 0 d add , 6 ⋅ 2 + 6 ⋅ 10 + 2 ⋅ 1 + 4 ⋅ 8 + 4 = 110.
The certificate checks this bound for the complete target. It supplies eight ideal magic inputs and two private classical locations u , v ∉ Δ u,v\notin\Delta u , v ∈ / Δ . Each basis ancilla has a local scope.
Step 2: compose assertions at gate boundaries. Write g 1 , … , g 27 g_1,\ldots,g_{27} g 1 , … , g 27 for the displayed instructions and let B B B be any public postcondition. Set A 27 = B A_{27}=B A 27 = B and A i − 1 = W g i ( A i ) A_{i-1}=W_{g_i}(A_i) A i − 1 = W g i ( A i ) . For example, the last readout, the final H, and the preceding CNOT give successive backward calculations
A 26 ( s ) = ∑ b Π b Z q 3 B ( s [ r 3 ↦ b ] ) Π b Z q 3 , A_{26}(s)=\sum_b\Pi_b^{Z_{q_3}}B(s[r_3\mapsto b])\Pi_b^{Z_{q_3}}, A 26 ( s ) = b ∑ Π b Z q 3 B ( s [ r 3 ↦ b ]) Π b Z q 3 ,
A 22 = H 3 † A 23 H 3 , A_{22}=H_3^\dagger A_{23}H_3, A 22 = H 3 † A 23 H 3 ,
A 21 = CNOT 3 , 0 † A 22 CNOT 3 , 0 . A_{21}=\operatorname{CNOT}_{3,0}^\dagger A_{22}\operatorname{CNOT}_{3,0}. A 21 = CNOT 3 , 0 † A 22 CNOT 3 , 0 .
The three intervening readouts define A 25 A_{25} A 25 , A 24 A_{24} A 24 , A 23 A_{23} A 23 by the same substitution rule. Every local lowering has exactly the corresponding public transformer. Sequencing joins these assertion boundaries from right to left. With the resource embedding V 8 V_{8} V 8 and assertion lift D 8 D_{8} D 8 , the complete result is
⊢ { Q } d a d d { D 8 ( B ) } , V 8 † Q ( σ ) V 8 = A 0 ( π ( σ ) ) . \vdash\{Q\}\ d_{\mathrm{add}}\ \{D_{8}(B)\}, \qquad V_{8}^{\dagger}Q(\sigma)V_{8}=A_{0}\bigl(\pi(\sigma)\bigr). ⊢ { Q } d add { D 8 ( B )} , V 8 † Q ( σ ) V 8 = A 0 ( π ( σ ) ) .
There is no approximation term: this source needs no angle synthesis. The theorem preserves every source postcondition for every data input. It is a compilation correctness result. A functional proof that the source implements addition would be a separate source-level specification.
Approximation through classical feedback
With inputs Γ = ( q 0 , q 1 , q 2 , q 3 ) \Gamma=(q_{0},q_{1},q_{2},q_{3}) Γ = ( q 0 , q 1 , q 2 , q 3 ) and Δ = ( r 0 , r 1 , r 2 , r 3 ) \Delta=(r_{0},r_{1},r_{2},r_{3}) Δ = ( r 0 , r 1 , r 2 , r 3 ) , the QASMBench source in Figure 11 combines phase synthesis with measurement-dependent control. Consider its guarded π / 8 \pi/8 π /8 phase R π / 8 = diag ( 1 , e i π / 8 ) R_{\pi/8}=\operatorname{diag}(1,e^{i\pi/8}) R π /8 = diag ( 1 , e iπ /8 ) on q 3 q_{3} q 3 . Let W W W be its synthesized word on the same wire, and let ε 8 \varepsilon_{8} ε 8 be its checked effect allowance. The conditional rule compares these paths:
Figure 11. The complete source named inverseqft_n4 in QASMBench. A green bit label means that the phase executes when that bit is one. The source’s π / 2 \pi/2 π /2 and π / 4 \pi/4 π /4 phases are displayed as S and T. The π / 8 \pi/8 π /8 phase is replaced by a certified word of 210 Clifford+T T T gates. All six guards and all four public readouts occur in the checked expansion.
Figure 21. r 0 r_{0} r 0 selects R π / 8 R_{\pi/8} R π /8 or skip, and the corresponding synthesized path selects W W W or skip; both paths are compared with allowance ε 8 \varepsilon_{8} ε 8 .
For s ( r 0 ) = 0 s(r_{0})=0 s ( r 0 ) = 0 , both weakest preconditions are B ( s ) B(s) B ( s ) , so their difference is zero. For s ( r 0 ) = 1 s(r_{0})=1 s ( r 0 ) = 1 , they are R π / 8 † B ( s ) R π / 8 R_{\pi/8}^{\dagger}B(s)R_{\pi/8} R π /8 † B ( s ) R π /8 and W † B ( s ) W W^{\dagger}B(s)W W † B ( s ) W . The local certificate bounds this difference by ε 8 I \varepsilon_{8}I ε 8 I in both directions. Thus the same allowance holds for every store, without assuming a probability for either branch.
No gate in the Clifford+T T T word changes a public bit. Testing the same guard before each gate therefore makes the same branch selection throughout the word.
The source has three π / 2 \pi/2 π /2 phases, two π / 4 \pi/4 π /4 phases, and one π / 8 \pi/8 π /8 phase. The first two kinds use S and T, respectively. The analytic checker assigns them conservative allowances ε S < 1.612 × 10 − 11 \varepsilon_{S}<1.612\times10^{-11} ε S < 1.612 × 1 0 − 11 and ε T < 1.601 × 10 − 11 \varepsilon_{T}<1.601\times10^{-11} ε T < 1.601 × 1 0 − 11 . The synthesized word has ε 8 < 1.263 × 10 − 7 \varepsilon_{8}<1.263\times10^{-7} ε 8 < 1.263 × 1 0 − 7 . The exact gates receive a tiny nonzero allowance because the checker encloses π \pi π by rationals and bounds a Taylor remainder of the phase, rather than recognizing S and T symbolically. Pulling the final effect back through the measurements and composing the six guarded replacements gives
ε i n v Q F T = 3 ε S + 2 ε T + ε 8 < 1.264 × 10 − 7 . \varepsilon_{\mathrm{invQFT}} = 3\varepsilon_{S} + 2\varepsilon_{T} + \varepsilon_{8} < 1.264 \times10^{-7}. ε invQFT = 3 ε S + 2 ε T + ε 8 < 1.264 × 1 0 − 7 .
All comparisons and the sum use exact rational allowances in the certificate. The source’s 19 steps emit 227 Clifford+T T T instructions. Their PPM target reserves 85 ideal magic-state inputs and has a bound of 988 primitive measurements. When a guard is false, the corresponding magic states stay idle. Marginalizing them leaves the data unchanged. The proof covers these skipped injections as well as the executed ones. Lowering adds no approximation error, and the ordinary Hoare precondition loses only ε i n v Q F T I \varepsilon_{\mathrm{invQFT}}I ε invQFT I . This case does not add a parallel-depth result.
A benchmark proof from source gates to measurements
We prove compilation correctness for the complete QASMBench input cat_state_n4 from Table 1. The proof first treats an arbitrary public postcondition. It then derives the benchmark’s cat-state readout property. Every source instruction and every compiled measurement scope appears below. The proof uses the weakest-precondition equations and the Hoare rules of § 4 .
Step 1: state the source and goal. The input contexts are Γ = ( q 0 , q 1 , q 2 , q 3 ) \Gamma= (q_0, q_1, q_2, q_3) Γ = ( q 0 , q 1 , q 2 , q 3 ) and Δ = ( r 0 , r 1 , r 2 , r 3 ) \Delta= (r_0, r_1, r_2, r_3) Δ = ( r 0 , r 1 , r 2 , r 3 ) . The source at the benchmark revision used in § 8.2 is
c = H 0 ▹ CNOT 01 ▹ CNOT 12 ▹ CNOT 23 ▹ c = H_0 \mathbin{\triangleright} \operatorname{CNOT}_{01} \mathbin{\triangleright} \operatorname{CNOT}_{12} \mathbin{\triangleright} \operatorname{CNOT}_{23} \mathbin{\triangleright} c = H 0 ▹ CNOT 01 ▹ CNOT 12 ▹ CNOT 23 ▹
M Z 0 ( r 0 ) ▹ M Z 1 ( r 1 ) ▹ M Z 2 ( r 2 ) ▹ M Z 3 ( r 3 ) . M_{Z_0}(r_0) \mathbin{\triangleright} M_{Z_1}(r_1) \mathbin{\triangleright} M_{Z_2}(r_2) \mathbin{\triangleright} M_{Z_3}(r_3). M Z 0 ( r 0 ) ▹ M Z 1 ( r 1 ) ▹ M Z 2 ( r 2 ) ▹ M Z 3 ( r 3 ) .
Subscripts name data wires. Each CNOT’s first index is its control. The four input qubits are supplied by the caller. We impose the usual all-zero input only when deriving the concrete output probabilities in Step 6. Figure 12 places an assertion at every instruction boundary.
Figure 12. The complete cat_state_n4 source with public results r 0 , r 1 , r 2 , r 3 r_0,r_1,r_2,r_3 r 0 , r 1 , r 2 , r 3 . Steps 1–4 apply H H H to q 0 q_0 q 0 , then CNOTs from q 0 q_0 q 0 to q 1 q_1 q 1 , from q 1 q_1 q 1 to q 2 q_2 q 2 , and from q 2 q_2 q 2 to q 3 q_3 q 3 . Steps 5–8 measure Z Z Z on q 0 q_0 q 0 , q 1 q_1 q 1 , q 2 q_2 q 2 , q 3 q_3 q 3 in that order. Each blue meter records its result in the displayed bit. The bottom strip places the full-register assertions A 0 , … , A 8 A_0,\ldots,A_8 A 0 , … , A 8 at the boundaries of these eight steps. The final assertion is A 8 = B A_8=B A 8 = B .
Let B B B be any Hermitian assertion on the four data qubits and public store. The target also has distinct private bits a a a , b b b , disjoint from Δ \Delta Δ . Let π \pi π forget these two bits. We will calculate A 0 = W c ( B ) A_0 = W_c(B) A 0 = W c ( B ) and derive
wp ( d , B ∘ π ) = A 0 ∘ π , ⊢ { A 0 ∘ π } d { B ∘ π } . (13) \operatorname{wp}(d, B \circ\pi) = A_0 \circ\pi,\qquad\vdash\{A_0 \circ\pi\}\ d\ \{B \circ\pi\}. \tag*{(13)} wp ( d , B ∘ π ) = A 0 ∘ π , ⊢ { A 0 ∘ π } d { B ∘ π } . (13)
The equality proves correctness for every public observation, including joint quantum and classical assertions. It holds for every initial value of a a a , b b b . There are no magic-state inputs or approximation allowances in this case.
Step 2: calculate all eight source boundaries. Write Q x ( j ) = Π x Z j Q_x^{(j)}=\Pi_x^{Z_j} Q x ( j ) = Π x Z j and C i j = C N O T i j C_{ij}=\mathrm{CNOT}_{ij} C ij = CNOT ij for the source matrix. All omitted tensor factors are identities. Starting from A 8 = B A_8=B A 8 = B , four uses of (W-Meas) give
A 7 ( s ) = ∑ w Q w ( 3 ) B ( s [ r 3 ↦ w ] ) Q w ( 3 ) . A_7(s)=\sum_w Q_w^{(3)}B(s[r_3\mapsto w])Q_w^{(3)}. A 7 ( s ) = w ∑ Q w ( 3 ) B ( s [ r 3 ↦ w ]) Q w ( 3 ) .
A 6 ( s ) = ∑ z , w Q z ( 2 ) Q w ( 3 ) B ( s [ r 2 ↦ z , r 3 ↦ w ] ) Q w ( 3 ) Q z ( 2 ) . A_6(s)=\sum_{z,w}Q_z^{(2)}Q_w^{(3)}B(s[r_2\mapsto z,r_3\mapsto w])Q_w^{(3)}Q_z^{(2)}. A 6 ( s ) = z , w ∑ Q z ( 2 ) Q w ( 3 ) B ( s [ r 2 ↦ z , r 3 ↦ w ]) Q w ( 3 ) Q z ( 2 ) .
A 5 ( s ) = ∑ y , z , w Q y ( 1 ) Q z ( 2 ) Q w ( 3 ) B ( s [ r 1 ↦ y , r 2 ↦ z , r 3 ↦ w ] ) Q w ( 3 ) Q z ( 2 ) Q y ( 1 ) . A_5(s)=\sum_{y,z,w}Q_y^{(1)}Q_z^{(2)}Q_w^{(3)}B(s[r_1\mapsto y,r_2\mapsto z,r_3\mapsto w])Q_w^{(3)}Q_z^{(2)}Q_y^{(1)}. A 5 ( s ) = y , z , w ∑ Q y ( 1 ) Q z ( 2 ) Q w ( 3 ) B ( s [ r 1 ↦ y , r 2 ↦ z , r 3 ↦ w ]) Q w ( 3 ) Q z ( 2 ) Q y ( 1 ) .
A 4 ( s ) = ∑ x , y , z , w Q x ( 0 ) Q y ( 1 ) Q z ( 2 ) Q w ( 3 ) B ( s [ r 0 ↦ x , r 1 ↦ y , r 2 ↦ z , r 3 ↦ w ] ) Q w ( 3 ) Q z ( 2 ) Q y ( 1 ) Q x ( 0 ) . A_4(s)=\sum_{x,y,z,w}Q_x^{(0)}Q_y^{(1)}Q_z^{(2)}Q_w^{(3)}B(s[r_0\mapsto x,r_1\mapsto y,r_2\mapsto z,r_3\mapsto w])Q_w^{(3)}Q_z^{(2)}Q_y^{(1)}Q_x^{(0)}. A 4 ( s ) = x , y , z , w ∑ Q x ( 0 ) Q y ( 1 ) Q z ( 2 ) Q w ( 3 ) B ( s [ r 0 ↦ x , r 1 ↦ y , r 2 ↦ z , r 3 ↦ w ]) Q w ( 3 ) Q z ( 2 ) Q y ( 1 ) Q x ( 0 ) .
Every summation variable ranges over { 0 , 1 } \{0,1\} { 0 , 1 } . In each line the measurement substitutes its own result before evaluating the suffix assertion. For example, A 6 ( s ) = ∑ z Q z ( 2 ) A 7 ( s [ r 2 ↦ z ] ) Q z ( 2 ) A_6(s)=\sum_z Q_z^{(2)}A_7(s[r_2\mapsto z])Q_z^{(2)} A 6 ( s ) = ∑ z Q z ( 2 ) A 7 ( s [ r 2 ↦ z ]) Q z ( 2 ) . The distinct result locations make the displayed substitutions commute. The four remaining source transformers are unitary conjugations:
A 3 = C 23 † A 4 C 23 , A 2 = C 12 † A 3 C 12 , A_3=C_{23}^{\dagger}A_4C_{23},\qquad A_2=C_{12}^{\dagger}A_3C_{12}, A 3 = C 23 † A 4 C 23 , A 2 = C 12 † A 3 C 12 ,
A 1 = C 01 † A 2 C 01 , A 0 = H 0 † A 1 H 0 . A_1=C_{01}^{\dagger}A_2C_{01},\qquad A_0=H_0^{\dagger}A_1H_0. A 1 = C 01 † A 2 C 01 , A 0 = H 0 † A 1 H 0 .
These equations specify every boundary in the source. We next derive the target triples that connect the same boundaries.
Step 3: write every compiled scope. Table 5 lists the target’s twelve scopes in execution order. For row j j j , the complete command d j d_j d j is
d j = let ν = ancilla ∣ 0 ⟩ in M X ν P j ( a ) ▹ M Y ν ( b ) ▹ if a ⊕ b then correct P j else skip . (14) d_j=\text{let }\nu=\text{ancilla }|0\rangle\text{ in }M_{X_\nu P_j}(a)\mathbin{\triangleright}M_{Y_\nu}(b)\mathbin{\triangleright}\text{if }a\oplus b\text{ then correct }P_j\text{ else skip}. \tag*{(14)} d j = let ν = ancilla ∣0 ⟩ in M X ν P j ( a ) ▹ M Y ν ( b ) ▹ if a ⊕ b then correct P j else skip . (14)
Inside the scope, P j P_j P j acts on the data and as identity on ν \nu ν . Thus X ν P j = X ⊗ P j X_\nu P_j=X\otimes P_j X ν P j = X ⊗ P j and Y ν = Y ⊗ I Y_\nu=Y\otimes I Y ν = Y ⊗ I . For a negative P j P_j P j , the joint measurement is signed. The sign of its Pauli correction cancels in conjugation, so the correction may use the unsigned product. Each row prepares and discards its own fresh qubit. The bits a , b a,b a , b are reused.
Table 5. Every scope of the compiled cat-state benchmark. Each d j d_j d j is the explicit program in Equation (14) with the displayed Pauli product. The assertions are calculated in Steps 4–5.
The full target is
d = d 1 ▹ d 2 ▹ ⋯ ▹ d 12 ▹ M Z 0 ( r 0 ) ▹ M Z 1 ( r 1 ) ▹ M Z 2 ( r 2 ) ▹ M Z 3 ( r 3 ) . d = d_1 \mathbin{\triangleright} d_2 \mathbin{\triangleright} \cdots\mathbin{\triangleright} d_{12} \mathbin{\triangleright} M_{Z_0}(r_0) \mathbin{\triangleright} M_{Z_1}(r_1) \mathbin{\triangleright} M_{Z_2}(r_2) \mathbin{\triangleright} M_{Z_3}(r_3). d = d 1 ▹ d 2 ▹ ⋯ ▹ d 12 ▹ M Z 0 ( r 0 ) ▹ M Z 1 ( r 1 ) ▹ M Z 2 ( r 2 ) ▹ M Z 3 ( r 3 ) .
The finite list contains 24 internal Pauli measurements and four public readouts. It uses one temporary qubit at a time. These 28 measurements match the original-source certificate’s measurement bound. This proof starts from the displayed typed source, as do the certificates. Parsing the benchmark file is outside the logic.
Figure 13 draws the complete compiled circuit. Its numbered scopes are the rows of Table 5. The boundary after scope j j j carries T j ∘ π T_j \circ\pi T j ∘ π . The displayed group boundaries connect these assertions to A 0 , … , A 4 A_0,\ldots,A_4 A 0 , … , A 4 . The four public meters then connect A 4 A_4 A 4 to A 8 = B A_8 = B A 8 = B . Step 4 proves each scope triple. Step 5 joins them in the displayed order.
Figure 13. The complete compiled QPPM circuit for cat_state_n4. Read left to right, then top to bottom, keeping the same data qubits. Each scope prepares a fresh zero ancilla. Its tall meter measures the displayed Pauli product into a a a . The purple meter measures Y ν Y_\nu Y ν into b b b . The ⊕ \oplus ⊕ node applies the unsigned correction product iff a ⊕ b = 1 a \oplus b = 1 a ⊕ b = 1 . Double bars discard the ancilla. The next scope reuses private bits a , b a, b a , b . Minus signs belong to the joint observables. All assertions are lifted by π \pi π . Steps 4–5 derive these boundaries. All 28 measurements are shown before fusion.
Step 4: derive a row using the primitive and structural rules. Fix a row, put P = P j P = P_j P = P j , and let F F F be its public suffix assertion. We calculate backwards through every command in that row. Write σ \sigma σ for a store containing a a a , b b b and the public bits. At the body exit, (W-Anc) requires the assertion D ( σ ) = I 2 ⊗ F ( π ( σ ) ) D(\sigma) = I_2 \otimes F(\pi(\sigma)) D ( σ ) = I 2 ⊗ F ( π ( σ )) . Set C x y = I 2 ⊗ P x ⊕ y C_{xy} = I_2 \otimes P^{x \oplus y} C x y = I 2 ⊗ P x ⊕ y . Let f f f denote the conditional displayed in Equation (14) . The four backward steps are
D 2 ( σ ) = C σ ( a ) , σ ( b ) D ( σ ) C σ ( a ) , σ ( b ) , (W-If), (W-Corr), (W-Skip), (15) D_2(\sigma) = C_{\sigma(a),\sigma(b)}D(\sigma)C_{\sigma(a),\sigma(b)},
\qquad\text{(W-If), (W-Corr), (W-Skip),} \tag*{(15)} D 2 ( σ ) = C σ ( a ) , σ ( b ) D ( σ ) C σ ( a ) , σ ( b ) , (W-If), (W-Corr), (W-Skip), (15)
D 1 ( σ ) = ∑ y Π y y C σ ( a ) , y D ( σ ) C σ ( a ) , y Π y y , (W-Meas), (16) D_1(\sigma) = \sum_y \Pi_y^y C_{\sigma(a),y}D(\sigma)C_{\sigma(a),y}\Pi_y^y,
\qquad\text{(W-Meas),} \tag*{(16)} D 1 ( σ ) = y ∑ Π y y C σ ( a ) , y D ( σ ) C σ ( a ) , y Π y y , (W-Meas), (16)
D 0 ( σ ) = ∑ x , y Π x x Π y y C x y D ( σ ) C x y Π y y Π x x , (W-Meas), (17) D_0(\sigma) = \sum_{x,y}\Pi_x^x\Pi_y^y C_{xy}D(\sigma)C_{xy}\Pi_y^y\Pi_x^x,
\qquad\text{(W-Meas),} \tag*{(17)} D 0 ( σ ) = x , y ∑ Π x x Π y y C x y D ( σ ) C x y Π y y Π x x , (W-Meas), (17)
wp ( d j , F ∘ π ) ( σ ) = E 0 † D 0 ( σ ) E 0 , (W-Seq), (W-Anc). (18) \operatorname{wp}(d_j,F \circ\pi)(\sigma) = E_0^\dagger D_0(\sigma)E_0,
\qquad\text{(W-Seq), (W-Anc).} \tag*{(18)} wp ( d j , F ∘ π ) ( σ ) = E 0 † D 0 ( σ ) E 0 , (W-Seq), (W-Anc). (18)
The substitution for b b b removes its old value in the second line. The substitution for a a a removes its old value in the third. Neither substitution changes D D D . This proves independence from the initial scratch values.
Rules H-Prim and H-Skip supply the leaves:
⊢ { ( I 2 ⊗ P ) D ( I 2 ⊗ P ) } correct P { D } , ⊢ { D } skip { D } . \vdash\{(I_2 \otimes P)D(I_2 \otimes P)\}\ \operatorname{correct}\ P\ \{D\},\qquad\vdash\ \{D\}\ \operatorname{skip}\ \{D\}. ⊢ {( I 2 ⊗ P ) D ( I 2 ⊗ P )} correct P { D } , ⊢ { D } skip { D } .
Rule H-If combines these leaves into { D 2 } f { D } \{D_2\}\ f\ \{D\} { D 2 } f { D } . The two measurement instances of H-Prim give
{ D 0 } → X ν P { D 1 } , { D 1 } → Y ν { D 2 } . \{D_0\}\xrightarrow{X_\nu P}\{D_1\},\qquad\{D_1\}\xrightarrow{Y_\nu}\{D_2\}. { D 0 } X ν P { D 1 } , { D 1 } Y ν { D 2 } .
Two applications of H-Seq join these triples to the conditional. Rule H-Anc then yields
⊢ { D 0 } → X ν P { D 1 } → Y ν { f } { D } \vdash\{D_0\}\xrightarrow{X_\nu P}\{D_1\}\xrightarrow{Y_\nu}\{f\}\{D\} ⊢ { D 0 } X ν P { D 1 } Y ν { f } { D }
⊢ { E 0 † D 0 E 0 } → d j { F ∘ π } . \vdash\{E_0^\dagger D_0E_0\}\xrightarrow{d_j}\{F\circ\pi\}. ⊢ { E 0 † D 0 E 0 } d j { F ∘ π } .
Thus the row triple is derived from the listed rules, with its precondition still given by an explicit matrix expression.
To simplify that expression, expand D = ∑ z = 0 1 E z F ( π ( σ ) ) E z † D=\sum_{z=0}^{1}E_zF(\pi(\sigma))E_z^\dagger D = ∑ z = 0 1 E z F ( π ( σ )) E z † and put K x y z = E z † C x y Π y P Π x P E 0 K_{xyz}=E_z^\dagger C_{xy}\Pi_y^P\Pi_x^P E_0 K x y z = E z † C x y Π y P Π x P E 0 . The Pauli-matrix calculation in Equation (9) gives
K x y 0 = 1 4 P x ⊕ y ( I − i ( − 1 ) x ⊕ y P ) = α x y 0 U ( P ) , K_{xy0}=\frac{1}{4}P^{x\oplus y}(I-i(-1)^{x\oplus y}P)=\alpha_{xy0}U(P), K x y 0 = 4 1 P x ⊕ y ( I − i ( − 1 ) x ⊕ y P ) = α x y 0 U ( P ) ,
K x y 1 = i ( − 1 ) y K x y 0 , α x y z = [ i ( − 1 ) y ] z 1 − i ( − 1 ) x ⊕ y 4 . K_{xy1}=i(-1)^yK_{xy0},\qquad\alpha_{xyz}=[i(-1)^y]^z\frac{1-i(-1)^{x\oplus y}}{4}. K x y 1 = i ( − 1 ) y K x y 0 , α x y z = [ i ( − 1 ) y ] z 4 1 − i ( − 1 ) x ⊕ y .
Here U ( P ) = Π 0 P + i Π 1 P U(P)=\Pi_0^P+i\Pi_1^P U ( P ) = Π 0 P + i Π 1 P is the matrix defined in § 5.1 . Each of the eight scalars has squared magnitude 2 / 16 = 1 / 8 2/16=1/8 2/16 = 1/8 . Therefore
E 0 † D 0 ( σ ) E 0 = ∑ x , y , z K x y z † F ( π ( σ ) ) K x y z = U ( P ) † F ( π ( σ ) ) U ( P ) . E_0^\dagger D_0(\sigma)E_0=\sum_{x,y,z}K_{xyz}^\dagger F(\pi(\sigma))K_{xyz}=U(P)^\dagger F(\pi(\sigma))U(P). E 0 † D 0 ( σ ) E 0 = x , y , z ∑ K x y z † F ( π ( σ )) K x y z = U ( P ) † F ( π ( σ )) U ( P ) .
This calculation applies to the whole four-qubit matrix F F F . It does not require a product state or a separable assertion.
Step 5: join all target triples and identify the source precondition. Set T 12 = A 4 T_{12}=A_4 T 12 = A 4 . Read the twelve rows of Table 5 backwards, using the calculated precondition
T j − 1 = U ( P j ) † T j U ( P j ) , j = 12 , 11 , … , 1. T_{j-1}=U(P_j)^\dagger T_jU(P_j),\qquad j=12,11,\ldots,1. T j − 1 = U ( P j ) † T j U ( P j ) , j = 12 , 11 , … , 1.
For example, the last three instances are
T 11 = U ( − Z 2 X 3 ) † A 4 U ( − Z 2 X 3 ) , T_{11}=U(-Z_2X_3)^\dagger A_4U(-Z_2X_3), T 11 = U ( − Z 2 X 3 ) † A 4 U ( − Z 2 X 3 ) ,
T 10 = U ( X 3 ) † T 11 U ( X 3 ) , T_{10}=U(X_3)^\dagger T_{11}U(X_3), T 10 = U ( X 3 ) † T 11 U ( X 3 ) ,
T 9 = U ( Z 2 ) † T 10 U ( Z 2 ) = C 23 † A 4 C 23 = A 3 . T_9=U(Z_2)^\dagger T_{10}U(Z_2)=C_{23}^\dagger A_4C_{23}=A_3. T 9 = U ( Z 2 ) † T 10 U ( Z 2 ) = C 23 † A 4 C 23 = A 3 .
The last equality uses U ( − Z 2 X 3 ) U ( X 3 ) U ( Z 2 ) = i C 23 U(-Z_2X_3)U(X_3)U(Z_2)=iC_{23} U ( − Z 2 X 3 ) U ( X 3 ) U ( Z 2 ) = i C 23 . Applying the same matrix identity to the two other specified pairs, followed by U ( Z 0 ) U ( X 0 ) U ( Z 0 ) = e i π / 4 H 0 U(Z_0)U(X_0)U(Z_0)=e^{i\pi/4}H_0 U ( Z 0 ) U ( X 0 ) U ( Z 0 ) = e iπ /4 H 0 , gives all gate boundaries:
Table 5 (PDF p. 35).
Matrices multiply from right to left. Their scalar phases cancel in every conjugation. Step 4 supplies the twelve row triples in the table. Step 2 and H-Prim supply the four readout triples
⊢ { A 4 + j ∘ π } → Z j { A 5 + j ∘ π } , j = 0 , 1 , 2 , 3. \vdash\{A_{4+j}\circ\pi\}\xrightarrow{Z_j}\{A_{5+j}\circ\pi\},\qquad j=0,1,2,3. ⊢ { A 4 + j ∘ π } Z j { A 5 + j ∘ π } , j = 0 , 1 , 2 , 3.
Their boundaries match because T 12 = A 4 T_{12}=A_4 T 12 = A 4 and A 8 = B A_8=B A 8 = B . Fifteen applications of H-Seq join the sixteen target triples into Equation (13) . Replacing each triple by its calculated weakest-precondition equality and applying (W-Seq) gives its equality statement as well. This proves the complete compilation contract.
Step 6: derive the benchmark’s concrete readout guarantee. Choose B = [ r 0 = r 1 = r 2 = r 3 ] B = [r_0 = r_1 = r_2 = r_3] B = [ r 0 = r 1 = r 2 = r 3 ] . In the following display a bracket is a scalar Boolean indicator, and every r j r_j r j in an assertion means s ( r j ) s(r_j) s ( r j ) . Substitution into Step 2 evaluates every boundary:
In particular, A 1 = I 2 ⊗ ∣ 000 ⟩ ⟨ 000 ∣ A_1 = I_2 \otimes\lvert000\rangle\langle000\rvert A 1 = I 2 ⊗ ∣ 000 ⟩ ⟨ 000 ∣ . For example, A 4 A_4 A 4 projects onto span { ∣ 0000 ⟩ , ∣ 1111 ⟩ } \operatorname{span}\{\lvert0000\rangle,\lvert1111\rangle\} span {∣ 0000 ⟩ , ∣ 1111 ⟩} . Conjugating by C 23 C_{23} C 23 changes this span to span { ∣ 0000 ⟩ , ∣ 1110 ⟩ } \operatorname{span}\{\lvert0000\rangle,\lvert1110\rangle\} span {∣ 0000 ⟩ , ∣ 1110 ⟩} , which is A 3 A_3 A 3 . The next two CNOTs similarly give the displayed A 2 A_2 A 2 and A 1 A_1 A 1 . Finally H 0 H_0 H 0 acts on the identity factor of A 1 A_1 A 1 , so it leaves the assertion unchanged.
Put Q 0000 = ∣ 0000 ⟩ ⟨ 0000 ∣ Q_{0000} = \lvert0000\rangle\langle0000\rvert Q 0000 = ∣ 0000 ⟩ ⟨ 0000 ∣ . The difference A 0 − Q 0000 = ∣ 1000 ⟩ ⟨ 1000 ∣ A_0 - Q_{0000} = \lvert1000\rangle\langle1000\rvert A 0 − Q 0000 = ∣ 1000 ⟩ ⟨ 1000 ∣ is positive. Applying H-Cons to the triple already derived in Step 5 gives
Q 0000 ⪯ A 0 ⊢ { A 0 } d { [ r 0 = r 1 = r 2 = r 3 ] } . ⊢ { Q 0000 } d { [ r 0 = r 1 = r 2 = r 3 ] } \begin{aligned}
Q_{0000} &\preceq A_0 \quad\vdash\{A_0\}\ d\ \{[r_0 = r_1 = r_2 = r_3]\}.\\
&\qquad\vdash\{Q_{0000}\}\ d\ \{[r_0 = r_1 = r_2 = r_3]\}
\end{aligned} Q 0000 ⪯ A 0 ⊢ { A 0 } d {[ r 0 = r 1 = r 2 = r 3 ]} . ⊢ { Q 0000 } d {[ r 0 = r 1 = r 2 = r 3 ]}
Here the displayed assertions are lifted by π \pi π implicitly. On input ρ = Q 0000 \rho= Q_{0000} ρ = Q 0000 , duality gives a lower bound of one for the event’s probability. Trace preservation gives the matching upper bound.
For the separate events E x ≡ ( r 0 = r 1 = r 2 = r 3 = x ) E_x \equiv(r_0 = r_1 = r_2 = r_3 = x) E x ≡ ( r 0 = r 1 = r 2 = r 3 = x ) , the same backward calculation retains just the x x x summand at A 4 A_4 A 4 and gives
wp ( d , [ E x ] ∘ π ) = Π x Q x ( 0 ) Q x ( 1 ) Q x ( 2 ) Q x ( 3 ) , Pr d [ E x ] = tr ( Q 0000 Π x Q x ( 0 ) Q x ( 1 ) Q x ( 2 ) Q x ( 3 ) ) = 1 2 . \operatorname{wp}(d,[E_x]\circ\pi)=\Pi_x Q_x^{(0)}Q_x^{(1)}Q_x^{(2)}Q_x^{(3)},\qquad
\Pr_d[E_x]=\operatorname{tr}\left(Q_{0000}\Pi_x Q_x^{(0)}Q_x^{(1)}Q_x^{(2)}Q_x^{(3)}\right)=\frac{1}{2}. wp ( d , [ E x ] ∘ π ) = Π x Q x ( 0 ) Q x ( 1 ) Q x ( 2 ) Q x ( 3 ) , d Pr [ E x ] = tr ( Q 0000 Π x Q x ( 0 ) Q x ( 1 ) Q x ( 2 ) Q x ( 3 ) ) = 2 1 .
Thus the compiled program returns 0000 or 1111, each with probability 1 / 2 1/2 1/2 . The probabilities follow from exact weakest preconditions on the specified input.
Step 7: reuse the derivation for the benchmark’s fusion. The certified fusion for this benchmark combines rows 3 and 4. Both have P j = Z 0 P_j = Z_0 P j = Z 0 . For every public suffix assertion F F F , Step 4 and (W-Seq) give
wp ( d 3 ▹ d 4 , F ∘ π ) = ( ( U ( Z 0 ) 2 ) † F U ( Z 0 ) 2 ) ∘ π = ( Z 0 F Z 0 ) ∘ π = wp ( correct Z 0 , F ∘ π ) . \begin{aligned}
\operatorname{wp}(d_3 \mathbin{\triangleright} d_4,F\circ\pi)
&=((U(Z_0)^2)^\dagger F U(Z_0)^2)\circ\pi\\
&=(Z_0FZ_0)\circ\pi=\operatorname{wp}(\operatorname{correct}\ Z_0,F\circ\pi).
\end{aligned} wp ( d 3 ▹ d 4 , F ∘ π ) = (( U ( Z 0 ) 2 ) † F U ( Z 0 ) 2 ) ∘ π = ( Z 0 F Z 0 ) ∘ π = wp ( correct Z 0 , F ∘ π ) .
The middle equality uses U ( Z 0 ) 2 = Z 0 U(Z_0)^2 = Z_0 U ( Z 0 ) 2 = Z 0 . Rule H-Prim supplies the replacement correction’s triple. Rule H-Seq joins it to the unchanged prefix and suffix. Every suffix precondition is public by Steps 2 and 4, so the private-bit values left by the two programs cannot affect this composition. The fused target therefore satisfies (13) and the same concrete readout guarantees. Replacing the two scopes removes four internal measurements, reducing the count from 28 to 24.
Grover search: a complete compilation proof
The QASMBench input grover_n2 implements Grover’s search algorithm on four items [16 , 23 ] . We prove that its compiled measurement program returns the marked item with probability one on the prescribed input. We also prove equality of source and target weakest preconditions for every public postcondition. The proof follows all 18 original source instructions.
Step 1: identify the search problem and source. The quantum inputs are Γ = ( q 0 , q 1 ) \Gamma=(q_0,q_1) Γ = ( q 0 , q 1 ) and the public bits are Δ = ( r 0 , r 1 ) \Delta=(r_0,r_1) Δ = ( r 0 , r 1 ) . Basis states are written ∣ q 0 q 1 ⟩ |q_0q_1\rangle ∣ q 0 q 1 ⟩ . Figure 14 shows the entire source. Writing C = CNOT 01 C=\operatorname{CNOT}_{01} C = CNOT 01 for the source matrix, its instruction list is
Figure 14. The complete 18-step grover_n2 source. Steps 1–2 prepare the search state. Steps 3–5 implement the oracle that marks ∣ 11 ⟩ |11\rangle ∣11 ⟩ in the ∣ q 0 q 1 ⟩ |q_0q_1\rangle ∣ q 0 q 1 ⟩ basis. Steps 6–16 perform diffusion. Steps 17–18 measure Z Z Z and record the public bits r 0 r_0 r 0 , r 1 r_1 r 1 . The adjacent H H H gates on q 1 q_1 q 1 are retained in source order. The bottom strip places full-register assertions before preparation and after each algorithm stage. The final assertion is A 18 = B A_{18}=B A 18 = B .
c = H 0 ▹ H 1 ▹ H 1 ▹ C ▹ H 1 c=H_0 \mathbin{\triangleright} H_1 \mathbin{\triangleright} H_1 \mathbin{\triangleright} C \mathbin{\triangleright} H_1 c = H 0 ▹ H 1 ▹ H 1 ▹ C ▹ H 1
preparation
▹ H 0 ▹ H 1 ▹ X 0 ▹ X 1 ▹ H 1 ▹ C ▹ H 1 ▹ X 0 ▹ X 1 ▹ H 0 ▹ H 1 \mathbin{\triangleright} H_0 \mathbin{\triangleright} H_1 \mathbin{\triangleright} X_0 \mathbin{\triangleright} X_1 \mathbin{\triangleright} H_1 \mathbin{\triangleright} C \mathbin{\triangleright} H_1 \mathbin{\triangleright} X_0 \mathbin{\triangleright} X_1 \mathbin{\triangleright} H_0 \mathbin{\triangleright} H_1 ▹ H 0 ▹ H 1 ▹ X 0 ▹ X 1 ▹ H 1 ▹ C ▹ H 1 ▹ X 0 ▹ X 1 ▹ H 0 ▹ H 1
diffusion
▹ M Z 0 ( r 0 ) ▹ M Z 1 ( r 1 ) . \mathbin{\triangleright} M_{Z_0}(r_0) \mathbin{\triangleright} M_{Z_1}(r_1). ▹ M Z 0 ( r 0 ) ▹ M Z 1 ( r 1 ) .
The adjacent H 1 H_1 H 1 instructions at positions 2 and 3 are retained. Let g i g_i g i be source instruction i i i , and let A i A_i A i be the assertion after it. The initial assertion is A 0 A_0 A 0 .
Put ∣ s ⟩ = ∣ + + ⟩ = ( ∣ 00 ⟩ + ∣ 01 ⟩ + ∣ 10 ⟩ + ∣ 11 ⟩ ) / 2 |s\rangle=|++\rangle=(|00\rangle+|01\rangle+|10\rangle+|11\rangle)/2 ∣ s ⟩ = ∣ + + ⟩ = ( ∣00 ⟩ + ∣01 ⟩ + ∣10 ⟩ + ∣11 ⟩) /2 . The source’s oracle matrix is
O = H 1 C H 1 = diag ( 1 , 1 , 1 , − 1 ) = I − 2 ∣ 11 ⟩ ⟨ 11 ∣ . O=H_1CH_1=\operatorname{diag}(1,1,1,-1)=I-2|11\rangle\langle11|. O = H 1 C H 1 = diag ( 1 , 1 , 1 , − 1 ) = I − 2∣11 ⟩ ⟨ 11∣.
It marks item 11. The diffusion block has matrix
D = ( H ⊗ H ) ( X ⊗ X ) O ( X ⊗ X ) ( H ⊗ H ) = I − 2 ∣ s ⟩ ⟨ s ∣ . D=(H\otimes H)(X\otimes X)O(X\otimes X)(H\otimes H)=I-2|s\rangle\langle s|. D = ( H ⊗ H ) ( X ⊗ X ) O ( X ⊗ X ) ( H ⊗ H ) = I − 2∣ s ⟩ ⟨ s ∣.
This is the usual diffusion matrix up to a global sign. In particular, O ∣ s ⟩ = ∣ s ⟩ − ∣ 11 ⟩ O|s\rangle=|s\rangle-|11\rangle O ∣ s ⟩ = ∣ s ⟩ − ∣11 ⟩ and ⟨ s ∣ O ∣ s ⟩ = 1 / 2 \langle s|O|s\rangle=1/2 ⟨ s ∣ O ∣ s ⟩ = 1/2 , so D O ∣ s ⟩ = − ∣ 11 ⟩ DO|s\rangle=-|11\rangle D O ∣ s ⟩ = − ∣11 ⟩ . The Hoare derivation below establishes this search guarantee for the compiled Pauli-measurement program.
Step 2: pull back an arbitrary postcondition. Let B B B be any Hermitian assertion on the two data qubits and public store. Put A 18 = B A_{18}=B A 18 = B and Q x ( j ) = Π x Z j Q_x^{(j)}=\Pi_{x}^{Z_j} Q x ( j ) = Π x Z j . The two readout instances of (W-Meas) give
A 17 ( s ) = ∑ y Q y ( 1 ) B ( s [ r 1 ↦ y ] ) Q y ( 1 ) A_{17}(s)=\sum_y Q_y^{(1)}B(s[r_1\mapsto y])Q_y^{(1)} A 17 ( s ) = y ∑ Q y ( 1 ) B ( s [ r 1 ↦ y ]) Q y ( 1 )
A 16 ( s ) = ∑ x , y Q x ( 0 ) Q y ( 1 ) B ( s [ r 0 ↦ x , r 1 ↦ y ] ) Q y ( 1 ) Q x ( 0 ) . A_{16}(s)=\sum_{x,y}Q_x^{(0)}Q_y^{(1)}B(s[r_0\mapsto x,r_1\mapsto y])Q_y^{(1)}Q_x^{(0)}. A 16 ( s ) = x , y ∑ Q x ( 0 ) Q y ( 1 ) B ( s [ r 0 ↦ x , r 1 ↦ y ]) Q y ( 1 ) Q x ( 0 ) .
Here x , y ∈ { 0 , 1 } x,y \in\{0,1\} x , y ∈ { 0 , 1 } . Each measurement substitutes the bit it records before evaluating the postcondition. For all sixteen preceding gates, calculate
A i − 1 = g i † A i g i , i = 16 , 15 , … , 1. (19) A_{i-1}=g_i^\dagger A_i g_i,\qquad i=16,15,\ldots,1. \tag*{(19)} A i − 1 = g i † A i g i , i = 16 , 15 , … , 1. (19)
Table 6 lists every g i g_i g i in this recursion. Thus A 0 = W c ( B ) A_0=W_c(B) A 0 = W c ( B ) . We now derive a target triple at each of these boundaries.
Table 6. Complete lowering of the original Grover benchmark. Each listed d j d_j d j is the explicit Pauli-measurement scope in Equation (20) . The four direct corrections retain their positions among the scopes.
Step 3: expand the target into Pauli measurements. The target uses distinct private bits a , b a,b a , b , disjoint from Δ \Delta Δ . Let π \pi π forget them. Its 36 ancilla scopes are the following finite commands, with the products P j P_j P j specified in Table 6 :
d j = let ν = ancilla ∣ 0 ⟩ in M X ν P j ( a ) ▹ M Y ν ( b ) ▹ if a ⊕ b then correct P j else skip . (20) d_j=\text{let }\nu=\text{ancilla }|0\rangle\text{ in }M_{X_\nu P_j}(a)\mathbin{\triangleright}M_{Y_\nu}(b)\mathbin{\triangleright}\text{ if }a\oplus b\text{ then correct }P_j\text{ else skip}. \tag*{(20)} d j = let ν = ancilla ∣0 ⟩ in M X ν P j ( a ) ▹ M Y ν ( b ) ▹ if a ⊕ b then correct P j else skip . (20)
The body context is ( ν , q 0 , q 1 ) (\nu,q_0,q_1) ( ν , q 0 , q 1 ) . Each scope prepares and discards a fresh zero qubit. Products P j P_j P j act as identity on ν \nu ν . For P j = − Z 0 X 1 P_j=-Z_0X_1 P j = − Z 0 X 1 , the first measurement is of − X ν Z 0 X 1 -X_\nu Z_0X_1 − X ν Z 0 X 1 . The sign of its conditional Pauli correction cancels in conjugation.
The target is d = c 1 ▹ c 2 ▹ ⋯ ▹ c 18 d=c_1 \mathbin{\triangleright} c_2 \mathbin{\triangleright}\cdots\mathbin{\triangleright}c_{18} d = c 1 ▹ c 2 ▹ ⋯ ▹ c 18 . There are ten Hadamards, two CNOTs, four direct corrections, and two readouts. The twelve non-Pauli gates expand into 36 scopes, giving 36 ⋅ 2 + 2 = 74 36\cdot2+2=74 36 ⋅ 2 + 2 = 74 measurements. This agrees with the original-source certificate. The target needs one temporary ancilla at a time and no magic states. The depth experiment in Table 1 starts from the shorter Qiskit output. Here we follow the original typed source, whose parsing remains outside the Hoare logic.
Figure 15 –Figure 17 draw the full compiled circuit in source order. Each source step i i i connects A i − 1 ∘ π A_{i-1}\circ\pi A i − 1 ∘ π to A i ∘ π A_i\circ\pi A i ∘ π . The two internal boundaries of each three-scope row carry F 1 ∘ π F_1\circ\pi F 1 ∘ π and F 2 ∘ π F_2\circ\pi F 2 ∘ π from Step 4. The four direct corrections and the two public readouts retain their original positions. The diagrams therefore display the same eighteen target triples that Step 4 composes.
Figure 15. The compiled Grover circuit, part 1 of 3: preparation and oracle. Read rows from left to right and top to bottom. The two data qubits persist between rows. Every numbered scope prepares a fresh ∣ 0 ⟩ ν |0\rangle_{\nu} ∣0 ⟩ ν , measures the displayed joint Pauli product into a a a , measures Y ν Y_{\nu} Y ν into b b b , and applies the unsigned correction product exactly when a ⊕ b = 1 a \mathbin{\oplus} b = 1 a ⊕ b = 1 . Double end bars discard the ancilla. Each following scope reuses the private locations a , b a, b a , b . The minus sign in scope 12 is part of the measured observable. The row assertions are lifted by π \pi π . They are the boundaries proved in Step 4. The labels F 1 , F 2 F_1, F_2 F 1 , F 2 are local to each row. Continue at A 5 A_5 A 5 in Figure 16 .
Figure 16. The compiled Grover circuit, part 2 of 3: the first diffusion steps. Continue from Figure 15 at A 5 A_5 A 5 . The first direct X 0 X_0 X 0 and X 1 X_1 X 1 corrections occur after scope 21 and before scope 22. These two boxes have no classical control. Their intermediate assertion is A 8 ∘ π A_8 \circ\pi A 8 ∘ π . All other correction columns retain their local parity controls. The signed joint meter in scope 27 measures − X ν Z 0 X 1 -X_\nu Z_0 X_1 − X ν Z 0 X 1 . Continue at A 12 A_{12} A 12 in Figure 17 .
Figure 17. The compiled Grover circuit, part 3 of 3: final diffusion steps and readout. Continue from Figure 16 at A 12 A_{12} A 12 . The remaining two direct corrections occur before scope 31. Their intermediate assertion is A 13 ∘ π A_{13} \circ\pi A 13 ∘ π . The final meters record Z 0 Z_0 Z 0 in r 0 r_0 r 0 , then Z 1 Z_1 Z 1 in r 1 r_1 r 1 . Their intermediate assertion is A 17 ∘ π A_{17} \circ\pi A 17 ∘ π . The three figures contain all 36 scopes, four direct corrections, and two public readouts. Step 4 joins their triples to prove compilation correctness. Step 5 instantiates B = [ r 0 = r 1 = 1 ] B = [r_0 = r_1 = 1] B = [ r 0 = r 1 = 1 ] and derives the input assertion ∣ 00 ⟩ ⟨ 00 ∣ \lvert00\rangle\langle00\rvert ∣ 00 ⟩ ⟨ 00 ∣ .
Step 4: derive each target boundary by the Hoare rules. The scope calculation in Appendix § 19 , Step 4, uses P 2 = I P^2 = I P 2 = I and the Pauli projector laws. It applies to this two-qubit data register. For a public suffix assertion F F F , the conditional is proved by H-Prim, H-Skip, and H-If. Two measurement instances of H-Prim and two uses of H-Seq prove the scope body. Rule H-Anc compresses its precondition by the zero-ancilla inclusion E 0 E_0 E 0 . The resulting weakest-precondition calculation is
wp ( d j , F ∘ π ) ( σ ) = ∑ x , y , z K x y z † F ( π ( σ ) ) K x y z = U ( P j ) † F ( π ( σ ) ) U ( P j ) , \begin{aligned}
\operatorname{wp}(d_j,F \circ\pi)(\sigma)=\sum_{x,y,z}K_{xyz}^{\dagger}F(\pi(\sigma))K_{xyz} \\
&=U(P_j)^{\dagger}F(\pi(\sigma))U(P_j),
\end{aligned} wp ( d j , F ∘ π ) ( σ ) = x , y , z ∑ K x y z † F ( π ( σ )) K x y z = U ( P j ) † F ( π ( σ )) U ( P j ) ,
K x y z = E z † ( I 2 ⊗ P j x ⊕ y ) Π y y Π x x ⊕ b E 0 . K_{xyz}=E_z^{\dagger}(I_2\otimes P_j^{x\oplus y})\Pi_y^y\Pi_x^{x\oplus b}E_0. K x y z = E z † ( I 2 ⊗ P j x ⊕ y ) Π y y Π x x ⊕ b E 0 .
As calculated there, K x y z = α x y z U ( P j ) K_{xyz}=\alpha_{xyz}U(P_j) K x y z = α x y z U ( P j ) and all eight ∣ α x y z ∣ 2 |\alpha_{xyz}|^2 ∣ α x y z ∣ 2 equal 1 / 8 1/8 1/8 . The two measurements overwrite a , b a,b a , b before feedback reads them. Therefore this derived scope triple holds for every initial value of the private bits.
For a row containing three scopes, write their products as P , Q , R P,Q,R P , Q , R in execution order and calculate the three intermediate assertions
F 3 = A i , F 2 = U ( R ) † F 3 U ( R ) , F 1 = U ( Q ) † F 2 U ( Q ) , F 0 = U ( P ) † F 1 U ( P ) . F_3=A_i,\qquad F_2=U(R)^{\dagger}F_3U(R),\qquad F_1=U(Q)^{\dagger}F_2U(Q),\qquad F_0=U(P)^{\dagger}F_1U(P). F 3 = A i , F 2 = U ( R ) † F 3 U ( R ) , F 1 = U ( Q ) † F 2 U ( Q ) , F 0 = U ( P ) † F 1 U ( P ) .
The scope rule derivation gives the three triples with matching boundaries F 0 , F 1 , F 2 , F 3 F_0,F_1,F_2,F_3 F 0 , F 1 , F 2 , F 3 , all lifted by π \pi π . Two uses of H-Seq join them. Their precondition is F 0 = ( U ( R ) U ( Q ) U ( P ) ) † A i ( U ( R ) U ( Q ) U ( P ) ) F_0=(U(R)U(Q)U(P))^{\dagger}A_i(U(R)U(Q)U(P)) F 0 = ( U ( R ) U ( Q ) U ( P ) ) † A i ( U ( R ) U ( Q ) U ( P )) . For every Hadamard row and both CNOT rows in the table, respectively,
U ( Z j ) U ( X j ) U ( Z j ) = e i π / 4 H j , j = 0 , 1 , U(Z_j)U(X_j)U(Z_j)=e^{i\pi/4}H_j,\qquad j=0,1, U ( Z j ) U ( X j ) U ( Z j ) = e iπ /4 H j , j = 0 , 1 ,
U ( − Z 0 X 1 ) U ( X 1 ) U ( Z 0 ) = i C . U(-Z_0X_1)U(X_1)U(Z_0)=iC. U ( − Z 0 X 1 ) U ( X 1 ) U ( Z 0 ) = i C .
The phases cancel, so F 0 = A i − 1 F_0=A_{i-1} F 0 = A i − 1 from Equation (19) . For the four direct corrections, (W-Corr) and H-Prim give the same equality and triple without an ancilla. For the last two rows, Step 2 and H-Prim give
⊢ { A 16 ∘ π } Z 0 { A 17 ∘ π } , ⊢ { A 17 ∘ π } Z 1 { B ∘ π } . \vdash\{A_{16}\circ\pi\}\,Z_0\,\{A_{17}\circ\pi\},\qquad\vdash\{A_{17}\circ\pi\}\,Z_1\,\{B\circ\pi\}. ⊢ { A 16 ∘ π } Z 0 { A 17 ∘ π } , ⊢ { A 17 ∘ π } Z 1 { B ∘ π } .
We have now derived ⊢ { A i − 1 ∘ π } c i { A i ∘ π } \vdash\{A_{i-1}\circ\pi\}\,c_i\,\{A_i\circ\pi\} ⊢ { A i − 1 ∘ π } c i { A i ∘ π } for every row i = 1 , … , 18 i=1,\ldots,18 i = 1 , … , 18 . Seventeen uses of H-Seq join these row triples. The corresponding uses of (W-Seq) compose their exact equalities. Thus
wp ( d , B ∘ π ) = W c ( B ) ∘ π , ⊢ { W c ( B ) ∘ π } d { B ∘ π } . (21) \operatorname{wp}(d,B\circ\pi)=W_c(B)\circ\pi,\qquad\vdash\{W_c(B)\circ\pi\}\,d\,\{B\circ\pi\}. \tag*{(21)} wp ( d , B ∘ π ) = W c ( B ) ∘ π , ⊢ { W c ( B ) ∘ π } d { B ∘ π } . (21)
This proves preservation of every public postcondition, including assertions that relate the measured bits to the quantum output.
Step 5: evaluate every precondition for successful search. Let E ( s ) E(s) E ( s ) mean s ( r 0 ) = s ( r 1 ) = 1 s(r_0)=s(r_1)=1 s ( r 0 ) = s ( r 1 ) = 1 , and take B = [ E ] B=[E] B = [ E ] . The last two steps become
A 18 = [ E ] , A 17 ( s ) = [ s ( r 0 ) = 1 ] Q 1 ( 1 ) , A 16 = Q 1 ( 0 ) Q 1 ( 1 ) = ∣ 11 ⟩ ⟨ 11 ∣ . A_{18}=[E],\qquad A_{17}(s)=[s(r_0)=1]Q_1^{(1)},\qquad A_{16}=Q_1^{(0)}Q_1^{(1)}=|11\rangle\langle11|. A 18 = [ E ] , A 17 ( s ) = [ s ( r 0 ) = 1 ] Q 1 ( 1 ) , A 16 = Q 1 ( 0 ) Q 1 ( 1 ) = ∣11 ⟩ ⟨ 11∣.
The first equality for a measurement follows by selecting y = 1 y=1 y = 1 in the A 17 A_{17} A 17 sum. The next selects x = 1 x=1 x = 1 . These are the two (W-Meas) steps, including their classical substitutions.
Every earlier assertion is a rank-one projector. Define ∣ ± ⟩ = ( ∣ 0 ⟩ ± ∣ 1 ⟩ ) / 2 |\pm\rangle=(|0\rangle\pm|1\rangle)/\sqrt{2} ∣ ± ⟩ = ( ∣0 ⟩ ± ∣1 ⟩) / 2 and
∣ Φ + ⟩ = ( ∣ 00 ⟩ + ∣ 11 ⟩ ) / 2 , ∣ Ψ − ⟩ = ( ∣ 01 ⟩ − ∣ 10 ⟩ ) / 2 , |\Phi^+\rangle=(|00\rangle+|11\rangle)/\sqrt{2},\qquad|\Psi^-\rangle=(|01\rangle-|10\rangle)/\sqrt{2}, ∣ Φ + ⟩ = ( ∣00 ⟩ + ∣11 ⟩) / 2 , ∣ Ψ − ⟩ = ( ∣01 ⟩ − ∣10 ⟩) / 2 ,
∣ ϕ ⟩ = ( ∣ 00 ⟩ + ∣ 01 ⟩ + ∣ 10 ⟩ − ∣ 11 ⟩ ) / 2 , |\phi\rangle=(|00\rangle+|01\rangle+|10\rangle-|11\rangle)/2, ∣ ϕ ⟩ = ( ∣00 ⟩ + ∣01 ⟩ + ∣10 ⟩ − ∣11 ⟩) /2 ,
∣ ψ ⟩ = ( ∣ 00 ⟩ − ∣ 01 ⟩ + ∣ 10 ⟩ + ∣ 11 ⟩ ) / 2 , |\psi\rangle=(|00\rangle-|01\rangle+|10\rangle+|11\rangle)/2, ∣ ψ ⟩ = ( ∣00 ⟩ − ∣01 ⟩ + ∣10 ⟩ + ∣11 ⟩) /2 ,
∣ χ ⟩ = ( ∣ 00 ⟩ − ∣ 01 ⟩ − ∣ 10 ⟩ − ∣ 11 ⟩ ) / 2. |\chi\rangle=(|00\rangle-|01\rangle-|10\rangle-|11\rangle)/2. ∣ χ ⟩ = ( ∣00 ⟩ − ∣01 ⟩ − ∣10 ⟩ − ∣11 ⟩) /2.
Table 7 evaluates all sixteen conjugations explicitly. An entry ∣ v i ⟩ |v_i\rangle ∣ v i ⟩ denotes A i = ∣ v i ⟩ ⟨ v i ∣ A_i = |v_i\rangle\langle v_i| A i = ∣ v i ⟩ ⟨ v i ∣ . Each row is checked by g i † ∣ v i ⟩ ⟨ v i ∣ g i = ∣ v i − 1 ⟩ ⟨ v i − 1 ∣ g_i^\dagger|v_i\rangle\langle v_i|g_i = |v_{i-1}\rangle\langle v_{i-1}| g i † ∣ v i ⟩ ⟨ v i ∣ g i = ∣ v i − 1 ⟩ ⟨ v i − 1 ∣ . Vector phases may differ between rows because they cancel in these projectors.
Table 7. The complete backward proof of Grover’s success event. Read from top to bottom. Every entry is a normalized vector specifying the displayed boundary’s projector. Step 4 supplies the corresponding target Hoare triple for each source gate.
For example, pulling ∣ ϕ ⟩ |\phi\rangle ∣ ϕ ⟩ back through gate 5 uses H 1 ∣ ϕ ⟩ = ∣ Φ + ⟩ H_1|\phi\rangle= |\Phi^+\rangle H 1 ∣ ϕ ⟩ = ∣ Φ + ⟩ . Pulling that projector through gate 4 uses C ∣ Φ + ⟩ = ∣ + 0 ⟩ C|\Phi^+\rangle= |+0\rangle C ∣ Φ + ⟩ = ∣ + 0 ⟩ . For gate 9, X 1 ∣ χ ⟩ = − ∣ ψ ⟩ X_1|\chi\rangle= -|\psi\rangle X 1 ∣ χ ⟩ = − ∣ ψ ⟩ , so the negative sign cancels. These calculations illustrate the Hadamard, CNOT, and direct-correction rows.
The final precondition is exactly A 0 = ∣ 00 ⟩ ⟨ 00 ∣ A_0 = |00\rangle\langle00| A 0 = ∣00 ⟩ ⟨ 00∣ . Instantiating Equation (21) gives the derived judgment
⊢ { ∣ 00 ⟩ ⟨ 00 ∣ } d { [ r 0 = r 1 = 1 ] } . \vdash\{|00\rangle\langle00|\}\ d\ \{[r_0=r_1=1]\}. ⊢ { ∣00 ⟩ ⟨ 00∣ } d {[ r 0 = r 1 = 1 ]} .
The constant precondition and the event are lifted to the full store implicitly. For the caller-supplied input ρ = ∣ 00 ⟩ ⟨ 00 ∣ \rho= |00\rangle\langle00| ρ = ∣00 ⟩ ⟨ 00∣ , forward/backward duality gives
Pr d [ r 0 = r 1 = 1 ] = tr ( ρ wp ( d , [ E ] ∘ π ) ) = tr ( ρ 2 ) = 1. \Pr_d[r_0=r_1=1] = \operatorname{tr}(\rho\ \operatorname{wp}(d,[E]\circ\pi)) = \operatorname{tr}(\rho^2) = 1. d Pr [ r 0 = r 1 = 1 ] = tr ( ρ wp ( d , [ E ] ∘ π )) = tr ( ρ 2 ) = 1.
Thus the complete measurement implementation finds the marked item with certainty. Equation (21) additionally preserves every public observation for arbitrary input states and stores.
A ten-qubit Ising circuit: a complete derivation
The QASMBench input ising_n10 has 490 instructions: 110 Hadamards, 90 CNOTs, 280 rotations, and ten final measurements. We use it to derive a guarantee for a concrete observation: whether the first two output bits agree. This example uses the same measurement, sequencing, approximation, and resource rules as the small examples. Its size changes the number of compositions.
Step 1: identify the program and its interface. The data inputs are Γ = ( q 0 , … , q 9 ) \Gamma= (q_0,\ldots,q_9) Γ = ( q 0 , … , q 9 ) and the public locations are Δ = ( r 0 , … , r 9 ) \Delta= (r_0,\ldots,r_9) Δ = ( r 0 , … , r 9 ) . Figure 18 groups the finite source into five consecutive blocks L 1 , … , L 5 L_1,\ldots,L_5 L 1 , … , L 5 . Each contains nine two-qubit interactions and ten one-qubit updates. The notation R θ = diag ( 1 , e i θ ) R_{\theta} = \operatorname{diag}(1,e^{i\theta}) R θ = diag ( 1 , e i θ ) represents the source’s R z ( θ ) R_z(\theta) R z ( θ ) under conjugation. Their global phase has no observable effect. All angles are exact rational radians.
Figure 18. The ten-qubit Ising case study. Each L ℓ L_{\ell} L ℓ contains nine interactions and ten local updates. The lower circuit expands the first interaction. All omitted qubits are idle during it. Blue gates rotate about Z Z Z , and orange targets mark X X X . Green annotations record the four synthesis allowances and two exact CNOT steps.
In each L ℓ L_{\ell} L ℓ , the interactions visit pairs ( 0 , 1 ) (0,1) ( 0 , 1 ) , ( 2 , 3 ) (2,3) ( 2 , 3 ) , ( 4 , 5 ) (4,5) ( 4 , 5 ) , ( 6 , 7 ) (6,7) ( 6 , 7 ) , ( 8 , 9 ) (8,9) ( 8 , 9 ) , then ( 1 , 2 ) (1,2) ( 1 , 2 ) , ( 3 , 4 ) (3,4) ( 3 , 4 ) , ( 5 , 6 ) (5,6) ( 5 , 6 ) , ( 7 , 8 ) (7,8) ( 7 , 8 ) . An interaction on ( i , j ) (i,j) ( i , j ) with angle θ \theta θ is
J i j ( θ ) = R θ ( q i ) ▹ R − θ ( q j ) ▹ R − θ ( q j ) ▹ CNOT i j ▹ R θ ( q j ) ▹ CNOT i j . J_{ij}(\theta)=R_{\theta}(q_i)\mathbin{\triangleright}R_{-\theta}(q_j)\mathbin{\triangleright}R_{-\theta}(q_j)\mathbin{\triangleright}\operatorname{CNOT}_{ij}\mathbin{\triangleright}R_{\theta}(q_j)\mathbin{\triangleright}\operatorname{CNOT}_{ij}. J ij ( θ ) = R θ ( q i ) ▹ R − θ ( q j ) ▹ R − θ ( q j ) ▹ CNOT ij ▹ R θ ( q j ) ▹ CNOT ij .
The subsequent update of q j q_j q j is H j ▹ R β ℓ ( q j ) ▹ H j ▹ R γ ℓ j ( q j ) H_j\mathbin{\triangleright}R_{\beta_{\ell}}(q_j)\mathbin{\triangleright}H_j\mathbin{\triangleright}R_{\gamma_{\ell j}}(q_j) H j ▹ R β ℓ ( q j ) ▹ H j ▹ R γ ℓ j ( q j ) , with parameters from the source. Thus a block has 9 ⋅ 6 + 10 ⋅ 4 = 94 9\cdot6+10\cdot4=94 9 ⋅ 6 + 10 ⋅ 4 = 94 instructions, and the whole circuit has 10 + 5 ⋅ 94 + 10 = 490 10+5\cdot94+10=490 10 + 5 ⋅ 94 + 10 = 490 . These are abbreviations for finite instruction lists, not loops added to QPPM.
Step 2: pull back a concrete output event. Let E ( s ) ≡ s ( r 0 ) = s ( r 1 ) E(s)\equiv s(r_0)=s(r_1) E ( s ) ≡ s ( r 0 ) = s ( r 1 ) , and put B = [ E ] B=[E] B = [ E ] . This is an effect: it is either I I I or zero. Write Q b ( j ) = Π b q j Q_b^{(j)}=\Pi_b^{q_j} Q b ( j ) = Π b q j . Backward calculation first crosses measurements into r 9 , … , r 2 r_9,\ldots,r_2 r 9 , … , r 2 . None changes E E E , so each leaves B B B unchanged:
wp ( M Z q j ( r j ) , B ) ( s ) = B ( s ) ∑ b = 0 1 Q b ( j ) = B ( s ) , 2 ≤ j ≤ 9. \operatorname{wp}(M_{Zq_j}(r_j),B)(s)=B(s)\sum_{b=0}^{1}Q_b^{(j)}=B(s),\qquad2\leq j\leq9. wp ( M Z q j ( r j ) , B ) ( s ) = B ( s ) b = 0 ∑ 1 Q b ( j ) = B ( s ) , 2 ≤ j ≤ 9.
The remaining two measurements expose the quantum condition for agreement:
B 1 ( s ) = ∑ b [ s ( r 0 ) = b ] Q b ( 1 ) , B_1(s)=\sum_b [s(r_0)=b]Q_b^{(1)}, B 1 ( s ) = b ∑ [ s ( r 0 ) = b ] Q b ( 1 ) ,
B 0 = ∑ b Q b ( 0 ) Q b ( 1 ) Q b ( 0 ) . B_0=\sum_b Q_b^{(0)}Q_b^{(1)}Q_b^{(0)}. B 0 = b ∑ Q b ( 0 ) Q b ( 1 ) Q b ( 0 ) .
Here each bracket is a Boolean indicator multiplying the matrix to its right. For example, the b = 0 b=0 b = 0 term in the second line selects the branch in which both measurements record zero. The two terms account for all successful branches. Pulling B 0 B_0 B 0 backwards through L 5 , … , L 1 L_5,\ldots,L_1 L 5 , … , L 1 and the initial Hadamards defines A = W c ( B ) A=W_c(B) A = W c ( B ) . This is an exact precondition for the chosen event in the source c c c .
Step 3: replace one interaction, with its allowance. The first interaction is J 01 ( − 3 / 10 ) J_{01}(-3/10) J 01 ( − 3/10 ) , shown in the figure. Its four phase occurrences use only two checked words, W − 3 / 10 W_{-3/10} W − 3/10 and W 3 / 10 W_{3/10} W 3/10 . The two CNOTs are exact. For either sign and either wire, the local proof establishes, for every effect F F F on all ten qubits,
− η I ⪯ R ± 3 / 10 † F R ± 3 / 10 − W ± 3 / 10 † F W ± 3 / 10 ⪯ η I , η = 210000000001 6250000000000000000 . (22) -\eta I\preceq R_{\pm3/10}^{\dagger}FR_{\pm3/10}-W_{\pm3/10}^{\dagger}FW_{\pm3/10}\preceq\eta I,\qquad\eta=\frac{210000000001}{6250000000000000000}. \tag*{(22)} − η I ⪯ R ± 3/10 † F R ± 3/10 − W ± 3/10 † F W ± 3/10 ⪯ η I , η = 6250000000000000000 210000000001 . (22)
Other tensor factors are implicit identities. In particular, F F F need not separate q 0 q_0 q 0 , q 1 q_1 q 1 from the other eight qubits. Write g 1 , … , g 6 g_1,\ldots,g_6 g 1 , … , g 6 for this interaction’s six instructions, g ^ i \widehat{g}_i g i for their replacements, and set F 6 = F F_6=F F 6 = F , F i − 1 = W g i ( F i ) F_{i-1}=W_{g_i}(F_i) F i − 1 = W g i ( F i ) . The backward assertions and allowance increments are
Table 1 (PDF p. 45).
Define F ^ 6 = F \widehat{F}_6=F F 6 = F and F ^ i − 1 = W g ^ i ( F ^ i ) \widehat{F}_{i-1}=W_{\widehat{g}_i}(\widehat{F}_i) F i − 1 = W g i ( F i ) . The sequencing argument is
W g i ( F i ) − W g ^ i ( F ^ i ) = ( W g i ( F i ) − W g ^ i ( F i ) ) + W g ^ i ( F i − F ^ i ) . W_{g_i}(F_i)-W_{\widehat{g}_i}(\widehat{F}_i)=\left(W_{g_i}(F_i)-W_{\widehat{g}_i}(F_i)\right)+W_{\widehat{g}_i}(F_i-\widehat{F}_i). W g i ( F i ) − W g i ( F i ) = ( W g i ( F i ) − W g i ( F i ) ) + W g i ( F i − F i ) .
The first term is bounded by ϵ i I \epsilon_i I ϵ i I . Positivity and preservation of I I I carry the suffix allowance through the second. Reading the row backwards gives 0 0 0 , η \eta η , η \eta η , 2 η 2\eta 2 η , 3 η 3\eta 3 η , 4 η 4\eta 4 η . Therefore
J ^ 01 ( − 3 / 10 ) → 4 η J ^ 01 , 4 η = 210000000001 1562500000000000000 < 1.345 × 10 − 7 . \widehat{J}_{01}(-3/10)\mathrel{\xrightarrow{4\eta}}\widehat{J}_{01},\qquad4\eta=\frac{210000000001}{1562500000000000000}<1.345\times10^{-7}. J 01 ( − 3/10 ) 4 η J 01 , 4 η = 1562500000000000000 210000000001 < 1.345 × 1 0 − 7 .
Reusing a local proof does not erase an occurrence from this sum.
Step 4: compose all source instructions and lower to measurements. The 280 rotations use 101 distinct local angle certificates. Each occurrence contributes its allowance. The Hadamards, CNOTs, and readouts contribute zero. The complete sum is
ϵ I s i n g = ∑ j = 1 280 ϵ j = 78280510032873 3125000000000000000 < 2.505 × 10 − 5 . \epsilon_{\mathrm{Ising}}=\sum_{j=1}^{280}\epsilon_j=\frac{78280510032873}{3125000000000000000}<2.505\times10^{-5}. ϵ Ising = j = 1 ∑ 280 ϵ j = 3125000000000000000 78280510032873 < 2.505 × 1 0 − 5 .
The resulting Clifford+T T T circuit has 55,027 instructions. Its QPPM target d d d uses k = 21 , 548 k=21,548 k = 21 , 548 supplied ideal magic states and two private classical locations u u u , v v v , disjoint from Δ \Delta Δ . Gadget ancillas are scoped. Let V k V_k V k insert those resources and let D k D_k D k lift public assertions, as in § 5 . Exact lowering preserves the composed allowance. Instantiating the existing Hoare transfer theorem with the effect B = [ E ] B=[E] B = [ E ] and A = W c ( B ) A=W_c(B) A = W c ( B ) gives
⊢ { Q } d { D k ( [ E ] ) } , V k † Q ( σ ) V k = A ( π ( σ ) ) − ϵ I s i n g I . \vdash\{Q\}\ d\ \{D_k([E])\},\qquad V_k^\dagger Q(\sigma)V_k=A(\pi(\sigma))-\epsilon_{\mathrm{Ising}}I. ⊢ { Q } d { D k ([ E ])} , V k † Q ( σ ) V k = A ( π ( σ )) − ϵ Ising I .
This is the ordinary Hoare judgment, with the magic-state premise stated separately.
Step 5: read the guarantee as a probability bound. For any positive trace-one input ρ \rho ρ and initial public store s s s , let p c p_c p c be the source probability of E E E , and p d p_d p d the target probability, with input V k ρ V k † V_k\rho V_k^\dagger V k ρ V k † and two zero private bits. Forward/backward duality and the two matrix inequalities of the certificate give
∣ p d − p c ∣ ≤ ϵ I s i n g < 2.505 × 10 − 5 . \lvert p_d-p_c\rvert\le\epsilon_{\mathrm{Ising}}<2.505\times10^{-5}. ∣ p d − p c ∣ ≤ ϵ Ising < 2.505 × 1 0 − 5 .
For the measured nearest-neighbor spin correlation, equal bits contribute +1 and unequal bits contribute −1, so its expectation is 2 p − 1 2p-1 2 p − 1 . Consequently
∣ ( 2 p d − 1 ) − ( 2 p c − 1 ) ∣ ≤ 2 ϵ I s i n g < 5.010 × 10 − 5 . \left|(2p_d-1)-(2p_c-1)\right|\le2\epsilon_{\mathrm{Ising}}<5.010\times10^{-5}. ∣ ( 2 p d − 1 ) − ( 2 p c − 1 ) ∣ ≤ 2 ϵ Ising < 5.010 × 1 0 − 5 .
This bounds the compilation error in a concrete observable of the complete simulation. It makes no assumption about the observable’s ideal value and introduces no new command or Hoare rule.
Kraus paths and the reset example
The instrument is constructed from a finite list of pairs ( t , K ) (t,K) ( t , K ) , where t t t is a final store and K K K is the matrix obtained by composing the operations along one execution path. Such a matrix is called a Kraus operator. Call this list B ( c , s ) \mathcal{B}(c,s) B ( c , s ) . For skip and assignment it contains one pair, with matrix I I I and the appropriate unchanged or updated store. For a measurement it contains
B ( M P ( r ) , s ) = [ ( s [ r ↦ 0 ] , Π 0 P ) , ( s [ r ↦ 1 ] , Π 1 P ) ] . \mathcal{B}(M_P(r),s)=[(s[r\mapsto0],\Pi_0^P),(s[r\mapsto1],\Pi_1^P)]. B ( M P ( r ) , s ) = [( s [ r ↦ 0 ] , Π 0 P ) , ( s [ r ↦ 1 ] , Π 1 P )] .
Correction gives the single pair ( s , P ) (s,P) ( s , P ) . A conditional chooses its branch using the initial store for that command. Sequencing composes paths in execution order:
B ( c ▹ d , s ) = [ ( t , L K ) ∣ ( u , K ) ∈ B ( c , s ) , ( t , L ) ∈ B ( d , u ) ] . \mathcal{B}(c\mathbin{\triangleright}d,s)=[(t,LK)\mid(u,K)\in\mathcal{B}(c,s),\ (t,L)\in\mathcal{B}(d,u)]. B ( c ▹ d , s ) = [( t , L K ) ∣ ( u , K ) ∈ B ( c , s ) , ( t , L ) ∈ B ( d , u )] .
The intermediate store u u u is passed to the continuation, which is where a recorded measurement result influences a later guard. When a program overwrites a bit, distinct paths can finish with the same store.
For a scope initialized to b b b , each body path ( t , K ) (t,K) ( t , K ) contributes two paths ( t , E 0 † K E b ) (t,E_0^\dagger K E_b) ( t , E 0 † K E b ) and ( t , E 1 † K E b ) (t,E_1^\dagger K E_b) ( t , E 1 † K E b ) . These account for discarding the first qubit. The final instrument groups paths by their retained classical store:
I c ( s , ρ , t ) = ∑ ( u , K ) ∈ B ( c , s ) [ u = t ] K ρ K † . (23) \mathcal{I}_c(s,\rho,t)=\sum_{(u,K)\in\mathcal{B}(c,s)}[u=t]K\rho K^\dagger. \tag*{(23)} I c ( s , ρ , t ) = ( u , K ) ∈ B ( c , s ) ∑ [ u = t ] K ρ K † . (23)
The bracket here is a scalar indicator. Paths that finish with the same store contribute to the same sum. An impossible path contributes the zero matrix.
To connect this construction to the logic, structural induction first establishes
wp ( c , A ) ( s ) = ∑ ( t , K ) ∈ B ( c , s ) K † A ( t ) K . \operatorname{wp}(c,A)(s)=\sum_{(t,K)\in\mathcal{B}(c,s)}K^\dagger A(t)K. wp ( c , A ) ( s ) = ( t , K ) ∈ B ( c , s ) ∑ K † A ( t ) K .
The sequence case distributes matrix multiplication over the finite path lists. The scope case sums the two ancilla blocks. Cyclicity of trace then gives Equation (2) . Positivity follows because every term in Equation (23) has the form K ρ K † K\rho K^\dagger K ρ K † with ρ ⪰ 0 \rho\succeq0 ρ ⪰ 0 . Taking the constant identity assertion in the duality equation and using wp ( c , I ) = I \operatorname{wp}(c,I)=I wp ( c , I ) = I proves preservation of total trace. The same path construction therefore supplies both the output matrices and the weakest preconditions used by the logic.
The two reset paths. Use the reset inputs Γ = ( q ) \Gamma=(q) Γ = ( q ) , Δ = ( r , u ) \Delta=(r,u) Δ = ( r , u ) and let s b = s [ r ↦ b ] [ u ↦ b ] s_b=s[r\mapsto b][u\mapsto b] s b = s [ r ↦ b ] [ u ↦ b ] . Following the two rows of the forward reset diagram gives
Figure 22 (PDF p. 46).
Assignment contributes an identity matrix, so B ( c r e s e t , s ) = [ ( s 0 , Q 0 ) , ( s 1 , X Q 1 ) ] \mathcal{B}(c_{\mathrm{reset}},s)=[(s_0,Q_0),(s_1,XQ_1)] B ( c reset , s ) = [( s 0 , Q 0 ) , ( s 1 , X Q 1 )] . For an arbitrary assertion A A A , the path formula reads
wp ( c r e s e t , A ) ( s ) = Q 0 A ( s 0 ) Q 0 + Q 1 X A ( s 1 ) X Q 1 . \operatorname{wp}(c_{\mathrm{reset}},A)(s)=Q_0A(s_0)Q_0+Q_1XA(s_1)XQ_1. wp ( c reset , A ) ( s ) = Q 0 A ( s 0 ) Q 0 + Q 1 X A ( s 1 ) X Q 1 .
For A = B r e s e t A=B_{\mathrm{reset}} A = B reset , both A ( s b ) = Q 0 A(s_b)=Q_0 A ( s b ) = Q 0 . The second term is Q 1 ( X Q 0 X ) Q 1 = Q 1 Q_1(XQ_0X)Q_1=Q_1 Q 1 ( X Q 0 X ) Q 1 = Q 1 , and the first is Q 0 Q_0 Q 0 . This recovers the precondition I I I calculated from the syntax.
Four paths, two records. With inputs Γ = ( ) , Δ = ( r ) \Gamma= (), \Delta= (r) Γ = ( ) , Δ = ( r ) , take f = let ν = ancilla ∣ 0 ⟩ in M X ν ( r ) f = \text{let } \nu= \text{ancilla } |0\rangle\text{ in } M_{X\nu}(r) f = let ν = ancilla ∣0 ⟩ in M X ν ( r ) . The scope construction gives K b j = E j † Π b X E 0 K_{bj} = E_j^\dagger\Pi_b^X E_0 K bj = E j † Π b X E 0 . Multiplying the matrices in Appendix § 14 yields
j = 0 j = 1 b = 0 1 / 2 1 / 2 b = 1 1 / 2 − 1 / 2 E 0 Π b X E j † ⏟ K b j \begin{array}{c|cc}
& j=0 & j=1 \\
b=0 & 1/2 & 1/2 \\
b=1 & 1/2 & -1/2
\end{array}
\qquad
\underbrace{E_0 \boxed{\Pi_b^X} E_j^\dagger}_{K_{bj}} b = 0 b = 1 j = 0 1/2 1/2 j = 1 1/2 − 1/2 K bj E 0 Π b X E j †
Each path contributes K b j 1 K b j † = 1 / 4 K_{bj}1K_{bj}^\dagger= 1/4 K bj 1 K bj † = 1/4 . Grouping the two paths with record b b b gives 1 / 2 1/2 1/2 . The index j j j belongs to the discard operation and is not a classical result available to the program.
Repeated measurement and a classical copy
We first specify the state produced by a measurement and then use that specification to reason about a second measurement of the same product. Fix input contexts Γ \Gamma Γ , Δ \Delta Δ , a signed product P P P on Γ \Gamma Γ , and a destination r ∈ Δ r \in\Delta r ∈ Δ . Write A P ( s ) = Π s ( r ) P A_P(s) = \Pi_{s(r)}^P A P ( s ) = Π s ( r ) P .
Steps 1–2: substitute the record and simplify. On outcome b b b , the updated store reads r = b r=b r = b , so A P ( s [ r ↦ b ] ) = Π b P A_P(s[r \mapsto b]) = \Pi_b^P A P ( s [ r ↦ b ]) = Π b P . Equation (W-Meas), idempotence, and H-Prim give the derivation over the measurement diagram:
wp ( M P ( r ) , A P ) ( s ) = ∑ b Π b P A P ( s [ r ↦ b ] ) Π b P = ∑ b Π b P = I (24) \operatorname{wp}(M_P(r), A_P)(s)
= \sum_b \Pi_b^P A_P(s[r \mapsto b]) \Pi_b^P
= \sum_b \Pi_b^P
= I \tag*{(24)} wp ( M P ( r ) , A P ) ( s ) = b ∑ Π b P A P ( s [ r ↦ b ]) Π b P = b ∑ Π b P = I (24)
For every initial state, the output lies in the eigenspace indexed by the recorded bit. A continuation can therefore refer to that eigenspace by reading r r r .
Step 3: read the established eigenspace again. Let u ∈ Δ u \in\Delta u ∈ Δ , u ≠ r u \ne r u = r , and define
B P ( s ) = { Π s ( r ) P s ( u ) = s ( r ) , 0 otherwise . B_P(s) =
\begin{cases}
\Pi_{s(r)}^P & s(u) = s(r),\\
0 & \text{otherwise}.
\end{cases} B P ( s ) = { Π s ( r ) P 0 s ( u ) = s ( r ) , otherwise .
Writing a = s ( r ) a=s(r) a = s ( r ) , Equation (W-Meas) for the second measurement gives
wp ( u : = measure P , B P ) ( s ) = ∑ b Π b P ( if b = a then Π a P else 0 ) Π b P = Π a P Π a P Π a P = Π a P = A P ( s ) . \operatorname{wp}(u := \operatorname{measure} P, B_P)(s)
= \sum_b \Pi_b^P(\text{if } b=a \text{ then } \Pi_a^P \text{ else } 0)\Pi_b^P
= \Pi_a^P\Pi_a^P\Pi_a^P
= \Pi_a^P
= A_P(s). wp ( u := measure P , B P ) ( s ) = b ∑ Π b P ( if b = a then Π a P else 0 ) Π b P = Π a P Π a P Π a P = Π a P = A P ( s ) .
The condition u ≠ r u \ne r u = r ensures that updating u u u leaves the read of r r r unchanged. Rule H-Seq joins the matching assertion boundaries:
{ I } P r { A P } P u { B P } . \{I\}\ \boxed{P}_{r}\ \{A_P\}\ \boxed{P}_{u}\ \{B_P\}. { I } P r { A P } P u { B P } .
Step 4: replace the second measurement by an assignment. By (W-Asgn), substituting r r r for u u u makes the agreement test true. The same assertion therefore supports a classical copy:
{ I } P r { A P } u : = r { B P } . \{I\}\ \boxed{P}_{r}\ \{A_P\}\ u := r\ \{B_P\}. { I } P r { A P } u := r { B P } .
The optimizer proves the stronger assertion-independent equivalence. For any postcondition Q Q Q , expanding both measurements produces terms
Π a P Π b P Q ( s [ r ↦ a ] [ u ↦ b ] ) Π b P Π a P . \Pi_a^P \Pi_b^P Q(s[r \mapsto a][u \mapsto b]) \Pi_b^P \Pi_a^P. Π a P Π b P Q ( s [ r ↦ a ] [ u ↦ b ]) Π b P Π a P .
Every term with a ≠ b a \ne b a = b is zero. The remaining terms are precisely those obtained by measuring once and copying the result. When u = r u=r u = r , two successive updates to the same destination collapse to the last update, and the surviving outcomes agree. Hence the rewrite also applies when u = r u=r u = r , although the earlier two-record specification used distinct destinations.
For a concrete instance, take Γ = ( q ) \Gamma=(q) Γ = ( q ) , Δ = ( r , u ) \Delta=(r,u) Δ = ( r , u ) , put P = Z P=Z P = Z , and start in ρ + \rho_+ ρ + . The first measurement gives Q b / 2 Q_b/2 Q b /2 with record r = b r=b r = b . Orthogonality makes the second measurement deterministic within each branch:
Q 0 2 → Z u Q 0 2 Q 1 2 → Z u Q 1 2 \frac{Q_0}{2}\quad\xrightarrow{\ Z_u\ }\quad\frac{Q_0}{2}
\qquad
\frac{Q_1}{2}\quad\xrightarrow{\ Z_u\ }\quad\frac{Q_1}{2} 2 Q 0 Z u 2 Q 0 2 Q 1 Z u 2 Q 1
with r = 0 r=0 r = 0 , r = u = 0 r=u=0 r = u = 0 , r = 1 r=1 r = 1 , and r = u = 1 r=u=1 r = u = 1 , respectively.
Indeed, Q b ( Q b / 2 ) Q b = Q b / 2 Q_b(Q_b/2)Q_b=Q_b/2 Q b ( Q b /2 ) Q b = Q b /2 , while Q 1 − b ( Q b / 2 ) Q 1 − b = 0 Q_{1-b}(Q_b/2)Q_{1-b}=0 Q 1 − b ( Q b /2 ) Q 1 − b = 0 . Replacing either displayed meter by the assignment u : = r u:=r u := r therefore preserves its store and output matrix. The assertion-independent proof above extends this calculation from ρ + \rho_+ ρ + to every input.
Measurement elimination: the scanner
Fix input contexts Γ \Gamma Γ , Δ \Delta Δ , products P , Q P,Q P , Q on Γ \Gamma Γ , locations r , u ∈ Δ r,u\in\Delta r , u ∈ Δ , and a command d d d on these registers. The scanner takes P P P , its saved destination r r r , and the remaining command d d d . Its invariant is
scan ( P , r , d ) ≡ P r ▹ d . (25) \operatorname{scan}(P,r,d)\ \equiv\ P_r \triangleright d. \tag*{(25)} scan ( P , r , d ) ≡ P r ▹ d . (25)
For a measurement prefix, define
scan ( P , r , M Q ( u ) ▹ d ) = { M P ( r ) ▹ u : = r ▹ d P = Q , M Q ( u ) ▹ scan ( P , r , d ) P ≠ Q , P Q = Q P , r ≠ u , M P ( r ) ▹ M Q ( u ) ▹ d otherwise. \operatorname{scan}(P,r,M_Q(u)\triangleright d)=
\begin{cases}
M_P(r)\triangleright u:=r\triangleright d & P=Q,\\
M_Q(u)\triangleright\operatorname{scan}(P,r,d) & P\ne Q,\ PQ=QP,\ r\ne u,\\
M_P(r)\triangleright M_Q(u)\triangleright d & \text{otherwise.}
\end{cases} scan ( P , r , M Q ( u ) ▹ d ) = ⎩ ⎨ ⎧ M P ( r ) ▹ u := r ▹ d M Q ( u ) ▹ scan ( P , r , d ) M P ( r ) ▹ M Q ( u ) ▹ d P = Q , P = Q , P Q = QP , r = u , otherwise.
For every other command d d d , put scan ( P , r , d ) = M P ( r ) ▹ d \operatorname{scan}(P,r,d)=M_P(r)\triangleright d scan ( P , r , d ) = M P ( r ) ▹ d . A terminal measurement is treated as a prefix with continuation skip. Product equality includes the sign. Immediate repetition may copy into its own destination. An intervening write to that destination blocks motion. Induction follows the scanner’s cases, using projector orthogonality, the swap theorem, and the unchanged barrier case. Sequence joining reassociates the command tree and invokes the scanner at leading measurements. Its correctness and count inequalities compose with the scanner’s local proof.
Follow the recursive calls. In Figure 6 , take P = Z ⊗ I P=Z\otimes I P = Z ⊗ I , Q = I ⊗ X Q=I\otimes X Q = I ⊗ X , R = I ⊗ Z R=I\otimes Z R = I ⊗ Z , with distinct destinations r 0 , r 1 , r 2 , r 3 r_0,r_1,r_2,r_3 r 0 , r 1 , r 2 , r 3 . Writing the continuation after the last measurement as skip, the calls are
scan ( P , r 0 , M Q ( r 1 ) ▹ M R ( r 2 ) ▹ M P ( r 3 ) ) = M Q ( r 1 ) ▹ scan ( P , r 0 , M R ( r 2 ) ▹ M P ( r 3 ) ) = M Q ( r 1 ) ▹ M R ( r 2 ) ▹ scan ( P , r 0 , M P ( r 3 ) ) = M Q ( r 1 ) ▹ M R ( r 2 ) ▹ M P ( r 0 ) ▹ r 3 : = r 0 . \begin{aligned}
\operatorname{scan}(P,r_0,M_Q(r_1)\triangleright M_R(r_2)\triangleright M_P(r_3)) \\
&= M_Q(r_1)\triangleright\operatorname{scan}(P,r_0,M_R(r_2)\triangleright M_P(r_3)) \\
&= M_Q(r_1)\triangleright M_R(r_2)\triangleright\operatorname{scan}(P,r_0,M_P(r_3)) \\
&= M_Q(r_1)\triangleright M_R(r_2)\triangleright M_P(r_0)\triangleright r_3:=r_0.
\end{aligned} scan ( P , r 0 , M Q ( r 1 ) ▹ M R ( r 2 ) ▹ M P ( r 3 )) = M Q ( r 1 ) ▹ scan ( P , r 0 , M R ( r 2 ) ▹ M P ( r 3 )) = M Q ( r 1 ) ▹ M R ( r 2 ) ▹ scan ( P , r 0 , M P ( r 3 )) = M Q ( r 1 ) ▹ M R ( r 2 ) ▹ M P ( r 0 ) ▹ r 3 := r 0 .
The first two lines use the commuting case. The last uses product equality. They are the two motions and final copy drawn in the figure. For a noncommuting prefix on Γ = ( q ) \Gamma=(q) Γ = ( q ) , Δ = ( r 0 , r 1 ) \Delta=(r_0,r_1) Δ = ( r 0 , r 1 ) , take P = Z P=Z P = Z , Q = X Q=X Q = X , and any continuation d d d on these registers. The scanner returns Z r 0 ▹ X r 1 ▹ d Z_{r_0}\triangleright X_{r_1}\triangleright d Z r 0 ▹ X r 1 ▹ d unchanged.
Elimination across commuting measurements
Write P = Z ⊗ I P = Z \otimes I P = Z ⊗ I , Q = I ⊗ X Q = I \otimes X Q = I ⊗ X , and R = I ⊗ Z R = I \otimes Z R = I ⊗ Z for the four-measurement example. Moving a measurement requires both commuting quantum operations and independent classical updates. Tensor factors show that P P P commutes with both Q Q Q and R R R . In contrast, Q R = − R Q QR = -RQ QR = − R Q . The compiler needs only the first two commutation facts.
Step 1: move the pending measurement past Q Q Q . The destinations r 0 r_0 r 0 and r 1 r_1 r 1 differ, so their store updates commute. Quantum projectors also commute because their measured products do. For outcomes a , b a,b a , b and an arbitrary postcondition matrix A A A , the relevant equality is
Π a P ( Π b Q A Π b Q ) Π a P = Π b Q ( Π a P A Π a P ) Π b Q . \Pi^{P}_{a}(\Pi^{Q}_{b}A\Pi^{Q}_{b})\Pi^{P}_{a}=\Pi^{Q}_{b}(\Pi^{P}_{a}A\Pi^{P}_{a})\Pi^{Q}_{b}. Π a P ( Π b Q A Π b Q ) Π a P = Π b Q ( Π a P A Π a P ) Π b Q .
Combining these equalities with (W-Meas) and (W-Seq) proves M P ( r 0 ) ▹ M Q ( r 1 ) ≡ M Q ( r 1 ) ▹ M P ( r 0 ) M_P(r_0) \mathrel{\triangleright} M_Q(r_1) \equiv M_Q(r_1) \mathrel{\triangleright} M_P(r_0) M P ( r 0 ) ▹ M Q ( r 1 ) ≡ M Q ( r 1 ) ▹ M P ( r 0 ) , including every final-store block.
Steps 2–3: move past R R R and eliminate repetition. Applying the swap theorem to R R R , r 2 r_2 r 2 gives the middle circuit of Figure 6 . The order of the noncommuting pair Q Q Q , R R R is unchanged. Projector idempotence then replaces the final measurement by a copy, giving the rightmost circuit. It has three measurements and preserves all four records on every input matrix. Both associations of the input sequence reduce to this result.
Step 4: lift the rewrite through the program. The equation holds for all postconditions. Substituting a continuation’s weakest precondition lifts it through sequencing by (W-Seq). Equations (W-If) and (W-Anc) lift it through conditionals and ancilla scopes. Thus the rewrite preserves an enclosing program’s weakest precondition.
The recursive calls above perform these two swaps and the final copy.
A single magic-state T T T gate
Take data input Γ = ( d ) \Gamma= (d) Γ = ( d ) , private locations Δ = ( a , b ) \Delta= (a,b) Δ = ( a , b ) , P = Z P = Z P = Z , and c = [ T ] c = [T] c = [ T ] in the magic-state contract of § 5.2 . The compiled program has quantum inputs ( μ , d ) (\mu,d) ( μ , d ) , with ∣ M ⟩ |M\rangle ∣ M ⟩ supplied on μ \mu μ . There is one supplied magic state: k = 1 k = 1 k = 1 , T = diag ( 1 , ω ) T = \operatorname{diag}(1,\omega) T = diag ( 1 , ω ) , and
V 1 ψ = ∣ M ⟩ ⊗ ψ , D 1 ( B ) ( s ) = I 2 ⊗ B ( π ( s ) ) . V_1\psi= |M\rangle\otimes\psi,\qquad D_1(B)(s) = I_2 \otimes B(\pi(s)). V 1 ψ = ∣ M ⟩ ⊗ ψ , D 1 ( B ) ( s ) = I 2 ⊗ B ( π ( s )) .
The map π \pi π forgets the two private outcome bits and retains every public bit.
Step 1: choose an assertion that observes the phase. Use constant assertions
A = ∣ + ⟩ ⟨ + ∣ = 1 2 ( 1 1 1 1 ) , B = ∣ M ⟩ ⟨ M ∣ = 1 2 ( 1 ω ‾ ω 1 ) . A = |+\rangle\langle+| = \frac{1}{2}\begin{pmatrix}1 & 1\\1 & 1\end{pmatrix},\qquad B = |M\rangle\langle M| = \frac{1}{2}\begin{pmatrix}1 & \overline{\omega}\\\omega& 1\end{pmatrix}. A = ∣ + ⟩ ⟨ + ∣ = 2 1 ( 1 1 1 1 ) , B = ∣ M ⟩ ⟨ M ∣ = 2 1 ( 1 ω ω 1 ) .
Both are effects. Pulling B B B backwards through the source gate gives
T † B T = 1 2 ( 1 0 0 ω ‾ ) ( 1 ω ‾ ω 1 ) ( 1 0 0 ω ) = A , ∣ ω ∣ 2 = 1. T^\dagger B T = \frac{1}{2}\begin{pmatrix}1 & 0\\0 & \overline{\omega}\end{pmatrix}\begin{pmatrix}1 & \overline{\omega}\\\omega& 1\end{pmatrix}\begin{pmatrix}1 & 0\\0 & \omega\end{pmatrix}=A,\qquad|\omega|^2=1. T † B T = 2 1 ( 1 0 0 ω ) ( 1 ω ω 1 ) ( 1 0 0 ω ) = A , ∣ ω ∣ 2 = 1.
Step 2: derive the compiled triple. Put Q = wp ( L ( [ T ] ) , D 1 ( B ) ) Q = \operatorname{wp}(\mathcal{L}([T]),D_1(B)) Q = wp ( L ([ T ]) , D 1 ( B )) . The weakest-precondition derivation and the injection contract give
{ Q } L ( [ T ] ) { D 1 ( B ) } , V 1 † Q ( s ) V 1 = T † B T = A . \{Q\}\ \mathcal{L}([T])\ \{D_1(B)\},\qquad V_1^\dagger Q(s)V_1=T^\dagger BT=A. { Q } L ([ T ]) { D 1 ( B )} , V 1 † Q ( s ) V 1 = T † B T = A .
Thus Q Q Q witnesses the circuit judgment for A , B A,B A , B . The postcondition ignores the consumed magic state and private outcomes. Compression supplies the input assumption.
Step 3: check the magic-state premise. For data input A A A , the expected value of B B B is one. Replacing the supplied magic state by ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ instead gives E 0 † Q ( s ) E 0 = Q 0 B Q 0 + Q 1 B Q 1 = I / 2 E_0^{\dagger} Q(s) E_0 = Q_0 B Q_0 + Q_1 B Q_1 = I/2 E 0 † Q ( s ) E 0 = Q 0 B Q 0 + Q 1 B Q 1 = I /2 . Duality calculates the expected value of B B B from these preconditions:
∣ M ⟩ ⊗ ∣ + ⟩ ⟶ L ( [ T ] ) ⟶ tr ( A 2 ) = 1 \lvert M\rangle\otimes\lvert+\rangle\longrightarrow\mathcal{L}([T]) \longrightarrow\operatorname{tr}(A^2) = 1 ∣ M ⟩ ⊗ ∣ + ⟩ ⟶ L ([ T ]) ⟶ tr ( A 2 ) = 1
∣ 0 ⟩ ⊗ ∣ + ⟩ ⟶ L ( [ T ] ) ⟶ tr ( A I / 2 ) = 1 / 2. \lvert0\rangle\otimes\lvert+\rangle\longrightarrow\mathcal{L}([T]) \longrightarrow\operatorname{tr}(AI/2) = 1/2. ∣ 0 ⟩ ⊗ ∣ + ⟩ ⟶ L ([ T ]) ⟶ tr ( A I /2 ) = 1/2.
The same compiled program therefore fails the certainty guarantee with the wrong magic state.
Ancilla discard and an idle entangled qubit
Preparing a fresh qubit and immediately discarding it is the identity on the original register. Discarding an existing qubit and preparing a replacement is a different operation. For the input context ( d , e ) (d,e) ( d , e ) , Bell state ∣ Φ ⟩ = ( ∣ 00 ⟩ + ∣ 11 ⟩ ) / 2 \lvert\Phi\rangle= (\lvert00\rangle+ \lvert11\rangle)/\sqrt{2} ∣ Φ ⟩ = (∣ 00 ⟩ + ∣ 11 ⟩) / 2 , and ρ Φ = ∣ Φ ⟩ ⟨ Φ ∣ \rho_{\Phi} = \lvert\Phi\rangle\langle\Phi\rvert ρ Φ = ∣ Φ ⟩ ⟨ Φ ∣ , we prove positivity and unit trace. The two orders of preparation and discard have different results:
ρ → prep 0 → drop ρ \rho\xrightarrow{\operatorname{prep}_0} \xrightarrow{\operatorname{drop}} \rho ρ prep 0 drop ρ
ρ Φ → drop I / 2 → prep 0 ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I / 2 ≠ ρ Φ . \rho_{\Phi} \xrightarrow{\operatorname{drop}} I/2 \xrightarrow{\operatorname{prep}_0} \lvert0\rangle\langle0\rvert\otimes I/2 \ne\rho_{\Phi}. ρ Φ drop I /2 prep 0 ∣ 0 ⟩ ⟨ 0 ∣ ⊗ I /2 = ρ Φ .
Partial trace removes the correlations with the discarded qubit. Preparing a new qubit does not restore them.
For a command c c c on Γ , Δ \Gamma,\Delta Γ , Δ and a fresh name e ∉ Γ e \notin\Gamma e ∈ / Γ , we derive the idle-qubit rule
{ A } c { B } { A ⊗ I } c { B ⊗ I } idle qubit (26) \frac{\{A\}\ \boxed{c}\ \{B\}}{\{A\otimes I\}\ \boxed{c}\ \{B\otimes I\}}
\quad\text{idle qubit} \tag*{(26)} { A ⊗ I } c { B ⊗ I } { A } c { B } idle qubit (26)
Here c ↑ c^{\uparrow} c ↑ has inputs ( Γ , e ) , Δ (\Gamma,e),\Delta ( Γ , e ) , Δ and leaves e e e unchanged. The proof retains the off-diagonal blocks of joint assertions, so it applies to entangled inputs. Exact equivalence and unitary component specifications extend as well. Applying the compiled phase component to the first half of this Bell state, with the last qubit idle, gives the lifted unitary action ( S ⊗ I ) ρ Φ ( S † ⊗ I ) (S\otimes I)\rho_{\Phi}(S^{\dagger}\otimes I) ( S ⊗ I ) ρ Φ ( S † ⊗ I ) . Its ( 00 , 11 ) (00,11) ( 00 , 11 ) entry is − i / 2 -i/2 − i /2 . This entry records the phase coherence between ∣ 00 ⟩ \lvert00\rangle ∣ 00 ⟩ and ∣ 11 ⟩ \lvert11\rangle ∣ 11 ⟩ . The extension theorem transports the application Hoare proof as well, so its outcome agreement remains certain for the joint Bell input. Instantiating the rule with the application triple from Equation (5) , with inputs ( d , e ) (d,e) ( d , e ) and ( a , b , r , t ) (a,b,r,t) ( a , b , r , t ) , gives
{ I } c a p p { B } { I ⊗ I } c a p p ↑ { B ⊗ I } \frac{\{I\}\ \boxed{c_{\mathrm{app}}}\ \{B\}}{\{I\otimes I\}\ \boxed{c_{\mathrm{app}}^{\uparrow}}\ \{B\otimes I\}} { I ⊗ I } c app ↑ { B ⊗ I } { I } c app { B }
Here ( B ⊗ I ) ( s ) = [ s ( t ) = s ( r ) ] ( Π s ( r ) ⊗ I ) (B\otimes I)(s) = [s(t)=s(r)](\Pi_{s(r)}\otimes I) ( B ⊗ I ) ( s ) = [ s ( t ) = s ( r )] ( Π s ( r ) ⊗ I ) ignores the last qubit while still checking the public records and the first qubit’s eigenspace. This exact rule does not by itself extend approximation allowances to a larger register.
Numerical instances of the approximation rules
With inputs Γ = ( ) , Δ = ( r ) \Gamma=(),\Delta=(r) Γ = ( ) , Δ = ( r ) , the commands f f f and z z z in Figure 20 satisfy f ≈ 1 / 2 z f\approx_{1/2}z f ≈ 1/2 z . For G ( s ) ≡ s ( r ) = 0 G(s)\equiv s(r)=0 G ( s ) ≡ s ( r ) = 0 , H-Prim and (W-Asgn) prove { 1 } z { [ G ] } \{1\}\ z\ \{[G]\} { 1 } z {[ G ]} . Symmetry and Theorem 4 give
Figure 20. Inputs: Γ = ( ) \Gamma=() Γ = ( ) , Δ = ( r ) \Delta=(r) Δ = ( r ) . The measurement circuit generates a fair bit. The assignment produces zero. Their quantum outputs are both empty, but the result distributions differ by 1/2 in trace distance.
{ 1 } r : = 0 { [ G ] } { 1 / 2 } ∣ 0 ⟩ X r drop { [ G ] } z ≈ 1 / 2 f \frac{\{1\}\ \boxed{r:=0}\ \{[G]\}}{\{1/2\}\ \boxed{\lvert0\rangle\ \boxed{X}_{r}\ \boxed{\operatorname{drop}}}\ \{[G]\}}
\qquad z\approx_{1/2}f { 1/2 } ∣ 0 ⟩ X r drop {[ G ]} { 1 } r := 0 {[ G ]} z ≈ 1/2 f
The exact forward calculation gives Pr f [ G ] = 1 / 2 \Pr_f[G] = 1/2 Pr f [ G ] = 1/2 , so the transferred guarantee is attained. For F ( s ) ≡ s ( r ) = 1 F(s) \equiv s(r) = 1 F ( s ) ≡ s ( r ) = 1 , the exact precondition of z z z is zero. The same theorem yields { − 1 / 2 } f { [ F ] } \{-1/2\}_f\{[F]\} { − 1/2 } f {[ F ]} . This valid but weak bound illustrates why the assertion language allows preconditions outside the interval [ 0 , I ] [0,I] [ 0 , I ] . The exact precondition of f f f is 1 / 2 1/2 1/2 .
A scope instance. Keep external inputs Γ = ( ) , Δ = ( r ) \Gamma= (), \Delta= (r) Γ = ( ) , Δ = ( r ) . Inside each scope, the body context is ( ν ) (\nu) ( ν ) . Take d 0 = ( r : = 0 ) d_0 = (r := 0) d 0 = ( r := 0 ) and d 1 = ( r : = 1 ) d_1 = (r := 1) d 1 = ( r := 1 ) on that qubit and location r r r . For any effect A A A , their preconditions are A ( s [ r ↦ 0 ] ) A(s[r \mapsto0]) A ( s [ r ↦ 0 ]) and A ( s [ r ↦ 1 ] ) A(s[r \mapsto1]) A ( s [ r ↦ 1 ]) . Both lie between 0 and I I I , so d 0 ≈ 1 d 1 d_0 \approx_1 d_1 d 0 ≈ 1 d 1 . The scope case of Theorem 4 , using (W-Anc), keeps allowance one:
∣ 0 ⟩ r : = 0 d r o p ⏟ let ν = ancilla ∣ 0 ⟩ in d 0 ≈ 1 ∣ 0 ⟩ r : = 1 d r o p ⏟ let ν = ancilla ∣ 0 ⟩ in d 1 \underbrace{|0\rangle\ r := 0\ \mathrm{drop}}_{\text{let }\nu=\text{ancilla }|0\rangle\text{ in }d_0}
\mathrel{\approx_1}
\underbrace{|0\rangle\ r := 1\ \mathrm{drop}}_{\text{let }\nu=\text{ancilla }|0\rangle\text{ in }d_1} let ν = ancilla ∣0 ⟩ in d 0 ∣0 ⟩ r := 0 drop ≈ 1 let ν = ancilla ∣0 ⟩ in d 1 ∣0 ⟩ r := 1 drop
The event [ r = 1 ] [r = 1] [ r = 1 ] has probability zero on the left and one on the right, so a smaller allowance is impossible. This uses the same preparation on both sides, as required.
Positive and negative output blocks. For f f f minus z z z on their normalized scalar input, the two blocks are Δ ( 0 ) = − 1 / 2 \Delta^{(0)} = -1/2 Δ ( 0 ) = − 1/2 and Δ ( 1 ) = 1 / 2 \Delta^{(1)} = 1/2 Δ ( 1 ) = 1/2 . Their spectral decompositions and positive-eigenspace projectors are
∑ t tr ( Π t + Δ ( t ) ) = 0 ( − 1 / 2 ) + 1 ( 1 / 2 ) = 1 2 . \sum_t \operatorname{tr}(\Pi_t^+\Delta^{(t)}) = 0(-1/2) + 1(1/2) = \frac{1}{2}. t ∑ tr ( Π t + Δ ( t ) ) = 0 ( − 1/2 ) + 1 ( 1/2 ) = 2 1 .
The maximizing assertion is therefore the event [ r = 1 ] [r = 1] [ r = 1 ] already used above. In this example the trace norm is absolute value, giving 1 2 ∑ t ∥ Δ ( t ) ∥ 1 = 1 2 ( ∣ − 1 / 2 ∣ + ∣ 1 / 2 ∣ ) = 1 / 2 \frac{1}{2}\sum_t \lVert\Delta^{(t)}\rVert_1 = \frac{1}{2}(|-1/2| + |1/2|) = 1/2 2 1 ∑ t ∥ Δ ( t ) ∥ 1 = 2 1 ( ∣ − 1/2∣ + ∣1/2∣ ) = 1/2 . The total trace difference is zero, although neither individual block has trace zero.
O The phase measurement sequence: normalization and scope
Section 5.3 computes the eight Kraus operators K x y j = α x y j U ( P ) K_{xyj} = \alpha_{xyj}U(P) K x y j = α x y j U ( P ) of the phase measurement sequence from Equation (9) . There E j ψ = ∣ j ⟩ ⊗ ψ E_j\psi= |j\rangle\otimes\psi E j ψ = ∣ j ⟩ ⊗ ψ includes the data register under ancilla basis value j j j , and E j † E_j^\dagger E j † takes that ancilla block. The feedback acts after both outcomes are available. For example, the path with x = y = j = 0 x = y = j = 0 x = y = j = 0 reduces to K 000 = ( I − i P ) / 4 K_{000} = (I - iP)/4 K 000 = ( I − i P ) /4 . The calculation includes negative products and identity factors. For P = Z P = Z P = Z , we have U ( P ) = S U(P) = S U ( P ) = S and K 000 = ( 1 − i ) S / 4 K_{000} = (1-i)S/4 K 000 = ( 1 − i ) S /4 .
Step 2: prove normalization. The displayed coefficients satisfy α x y j α ‾ x y j = 1 / 8 \alpha_{xyj}\overline{\alpha}_{xyj} = 1/8 α x y j α x y j = 1/8 for every x , y , j x,y,j x , y , j . It follows that
K x y j ρ K x y j † = 1 8 U ( P ) ρ U ( P ) † . K_{xyj}\rho K_{xyj}^{\dagger} = \frac{1}{8}U(P)\rho U(P)^{\dagger}. K x y j ρ K x y j † = 8 1 U ( P ) ρ U ( P ) † .
For a fixed recorded pair ( x , y ) (x,y) ( x , y ) , discarding the ancilla sums the two j j j terms and yields U ( P ) ρ U ( P ) † / 4 U(P)\rho U(P)^{\dagger}/4 U ( P ) ρ U ( P ) † /4 . Summing the four outcome pairs yields U ( P ) ρ U ( P ) † U(P)\rho U(P)^{\dagger} U ( P ) ρ U ( P ) † . Every measurement outcome contributes to this sum. The calculation holds for every input matrix.
Step 3: derive the component specification. For a public assertion A A A , the corresponding calculation pulls back each outcome pair to U ( P ) † A U ( P ) / 4 U(P)^{\dagger}AU(P)/4 U ( P ) † A U ( P ) /4 . Since only the private bits change, the public store is preserved. With π \pi π forgetting the two private bits, the contract is
wp ( let ν = ancilla ∣ 0 ⟩ in ( M X ⊗ P ( a ) ▹ M Y ⊗ I ( b ) ▹ \operatorname{wp}\bigl(\text{let }\nu=\text{ancilla }|0\rangle\text{ in }(M_{X\otimes P}(a) \mathbin{\triangleright} M_{Y\otimes I}(b) \mathbin{\triangleright} wp ( let ν = ancilla ∣0 ⟩ in ( M X ⊗ P ( a ) ▹ M Y ⊗ I ( b ) ▹
if a ⊕ b then correct ( I ⊗ P ) else skip ) , A ∘ π ) ( s ) = U ( P ) † A ( π ( s ) ) U ( P ) . \text{if }a\oplus b\text{ then correct }(I\otimes P)\text{ else skip}), A\circ\pi\bigr)(s)
= U(P)^{\dagger}A(\pi(s))U(P). if a ⊕ b then correct ( I ⊗ P ) else skip ) , A ∘ π ) ( s ) = U ( P ) † A ( π ( s )) U ( P ) .
Here X ν P = X ⊗ P X_{\nu}P = X\otimes P X ν P = X ⊗ P and Y ν = Y ⊗ I Y_{\nu} = Y\otimes I Y ν = Y ⊗ I in the body context. The private bits are overwritten by the measurements before feedback reads them. Consequently, the specification holds for every initial value of those bits. Their locations must be distinct: if they alias, the second measurement overwrites the first outcome and the exclusive-or guard is always false. Taking P = Z P = Z P = Z gives the application transformer S ~ † A S ~ \tilde{S}^{\dagger} A \tilde{S} S ~ † A S ~ , which maps the Y Y Y projector back to the corresponding X X X projector.
Certificate for the two-qubit circuit
This appendix supplies the numerical and rewriting steps for § 6.2 . The example uses the existing syntax, gadget contracts, approximation rule, and scheduling checker.
The phase allowance. For θ = π / 2 + δ \theta= \pi/2 + \delta θ = π /2 + δ and δ = π / 2 26 \delta= \pi/2^{26} δ = π / 2 26 , the phase function is Lipschitz with constant one:
∣ e i θ − i ∣ = ∣ e i θ − e i π / 2 ∣ ≤ ∣ θ − π / 2 ∣ = π 2 26 < 4 2 26 = 2 − 24 . \left|e^{i\theta} - i\right| = \left|e^{i\theta} - e^{i\pi/2}\right| \le\left|\theta- \pi/2\right| = \frac{\pi}{2^{26}} < \frac{4}{2^{26}} = 2^{-24}. e i θ − i = e i θ − e iπ /2 ≤ ∣ θ − π /2 ∣ = 2 26 π < 2 26 4 = 2 − 24 .
Thus the diagram’s replacement R θ ⇝ S R_\theta\rightsquigarrow S R θ ⇝ S has a checked scalar certificate. To convert it into the effect allowance used by the logic, set V = R θ V = R_\theta V = R θ , V ~ = V ⊗ I \widetilde{V} = V \otimes I V = V ⊗ I , and S ~ = S ⊗ I \widetilde{S} = S \otimes I S = S ⊗ I . Let E i j = ∣ i ⟩ ⟨ j ∣ ⊗ I E_{ij} = |i\rangle\langle j| \otimes I E ij = ∣ i ⟩ ⟨ j ∣ ⊗ I , for i , j ∈ { 0 , 1 } i,j \in\{0,1\} i , j ∈ { 0 , 1 } . Expanding conjugation in these matrix units gives
S ~ † B S ~ − V ~ † B V ~ = ∑ i , j , k , l = 0 1 ( S ‾ k i S ‾ l j − V ‾ k i V ‾ l j ) E i k B E l j . \widetilde{S}^{\dagger} B \widetilde{S} - \widetilde{V}^{\dagger} B \widetilde{V}
= \sum_{i,j,k,l=0}^{1} \left(\overline{S}_{ki}\overline{S}_{lj} - \overline{V}_{ki}\overline{V}_{lj}\right) E_{ik} B E_{lj}. S † B S − V † B V = i , j , k , l = 0 ∑ 1 ( S k i S l j − V k i V l j ) E ik B E l j .
The only possibly nonzero coefficient differences are i − e i θ i - e^{i\theta} i − e i θ and − i − e − i θ -i - e^{-i\theta} − i − e − i θ . Their absolute values agree and are at most 2 − 24 2^{-24} 2 − 24 . For 0 ⪯ B ⪯ I 0 \preceq B \preceq I 0 ⪯ B ⪯ I , the operator norms of B B B and all E i j E_{ij} E ij are at most one. Applying the uniform bound to the sixteen terms, as in the synthesis checker, gives
∥ S ~ † B S ~ − V ~ † B V ~ ∥ o p ≤ 16 ⋅ 2 − 24 = 2 − 20 . \left\|\widetilde{S}^{\dagger} B \widetilde{S} - \widetilde{V}^{\dagger} B \widetilde{V}\right\|_{\mathrm{op}} \le16 \cdot2^{-24} = 2^{-20}. S † B S − V † B V op ≤ 16 ⋅ 2 − 24 = 2 − 20 .
The matrix difference is Hermitian, so it lies between − 2 − 20 I -2^{-20}I − 2 − 20 I and 2 − 20 I 2^{-20}I 2 − 20 I . This calculation acts on the full two-qubit assertion B B B and makes no separability assumption. Exact gates before and after this replacement preserve the allowance: the suffix pulls back an effect, and the prefix preserves the two matrix inequalities. The five source blocks therefore contribute allowances 0 , 0 , 0 , 2 − 20 , 0 0, 0, 0, 2^{-20}, 0 0 , 0 , 0 , 2 − 20 , 0 .
Each exact rewrite. Use P = Z ⊗ I P = Z \otimes I P = Z ⊗ I , Q = I ⊗ Z Q = I \otimes Z Q = I ⊗ Z , R = I ⊗ X R = I \otimes X R = I ⊗ X as in the main text. For the purpose of fusion, write the final correction as U ( R ) 2 = R U(R)^2 = R U ( R ) 2 = R . The checked sequence of edits is
input U ( P ) ▹ U ( Q ) ▹ U ( P ) ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( P ) ▹ U ( R ) 2 swap U ( Q ) ▹ U ( P ) ▹ U ( P ) ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( P ) ▹ U ( R ) 2 fuse U ( Q ) ▹ U ( P ) 2 ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( P ) ▹ U ( R ) 2 swap U ( Q ) ▹ U ( P ) 2 ▹ U ( R ) ▹ U ( P ) ▹ U ( P R ) 3 ▹ U ( R ) 2 swap U ( Q ) ▹ U ( P ) 2 ▹ U ( P ) ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( R ) 2 fuse U ( Q ) ▹ U ( P ) 3 ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( R ) 2 swap U ( Q ) ▹ U ( P ) 3 ▹ U ( R ) ▹ U ( R ) 2 ▹ U ( P R ) 3 fuse U ( Q ) ▹ U ( P ) 3 ▹ U ( R ) 3 ▹ U ( P R ) 3 . \begin{aligned}
\text{input}\quad&U(P) \triangleright U(Q) \triangleright U(P) \triangleright U(R) \triangleright U(PR)^3 \triangleright U(P) \triangleright U(R)^2\\
\text{swap}\quad&U(Q) \triangleright U(P) \triangleright U(P) \triangleright U(R) \triangleright U(PR)^3 \triangleright U(P) \triangleright U(R)^2\\
\text{fuse}\quad&U(Q) \triangleright U(P)^2 \triangleright U(R) \triangleright U(PR)^3 \triangleright U(P) \triangleright U(R)^2\\
\text{swap}\quad&U(Q) \triangleright U(P)^2 \triangleright U(R) \triangleright U(P) \triangleright U(PR)^3 \triangleright U(R)^2\\
\text{swap}\quad&U(Q) \triangleright U(P)^2 \triangleright U(P) \triangleright U(R) \triangleright U(PR)^3 \triangleright U(R)^2\\
\text{fuse}\quad&U(Q) \triangleright U(P)^3 \triangleright U(R) \triangleright U(PR)^3 \triangleright U(R)^2\\
\text{swap}\quad&U(Q) \triangleright U(P)^3 \triangleright U(R) \triangleright U(R)^2 \triangleright U(PR)^3\\
\text{fuse}\quad&U(Q) \triangleright U(P)^3 \triangleright U(R)^3 \triangleright U(PR)^3.
\end{aligned} input swap fuse swap swap fuse swap fuse U ( P ) ▹ U ( Q ) ▹ U ( P ) ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( P ) ▹ U ( R ) 2 U ( Q ) ▹ U ( P ) ▹ U ( P ) ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( P ) ▹ U ( R ) 2 U ( Q ) ▹ U ( P ) 2 ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( P ) ▹ U ( R ) 2 U ( Q ) ▹ U ( P ) 2 ▹ U ( R ) ▹ U ( P ) ▹ U ( P R ) 3 ▹ U ( R ) 2 U ( Q ) ▹ U ( P ) 2 ▹ U ( P ) ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( R ) 2 U ( Q ) ▹ U ( P ) 3 ▹ U ( R ) ▹ U ( P R ) 3 ▹ U ( R ) 2 U ( Q ) ▹ U ( P ) 3 ▹ U ( R ) ▹ U ( R ) 2 ▹ U ( P R ) 3 U ( Q ) ▹ U ( P ) 3 ▹ U ( R ) 3 ▹ U ( P R ) 3 .
The swaps use P Q = Q P PQ = QP P Q = QP , P ( P R ) = ( P R ) P P(PR) = (PR)P P ( P R ) = ( P R ) P , P R = R P PR = RP P R = R P , and R ( P R ) = ( P R ) R R(PR) = (PR)R R ( P R ) = ( P R ) R , respectively. Each follows by multiplying the displayed Pauli factors. The fusions add the two exponents modulo four. No swap crosses the noncommuting pair Q Q Q , R R R , and no approximation is used in these edits.
From macro layers to logical rounds. The first optimized layer uses distinct private bits ( r Q , s Q ) (r_Q, s_Q) ( r Q , s Q ) and ( r P , s P ) (r_P, s_P) ( r P , s P ) . Its serial primitive sequence is J Q ▹ Y Q ▹ F Q ▹ J P ▹ Y P ▹ F P J_Q \triangleright Y_Q \triangleright F_Q \triangleright J_P \triangleright Y_P \triangleright F_P J Q ▹ Y Q ▹ F Q ▹ J P ▹ Y P ▹ F P , where J J J denotes the joint measurement, Y Y Y the ancilla readout, and F F F the parity-controlled correction. These are the following two paths through the first part of Figure 8 :
J Q Y Q F Q J P Y P F P ⟹ J Q J P ⏟ round 1 Y Q Y P ⏟ round 2 F Q F P J_Q\quad Y_Q\quad F_Q\quad J_P\quad Y_P\quad F_P
\;\Longrightarrow\;
\underbrace{J_Q\quad J_P}_{\text{round 1}}\quad
\underbrace{Y_Q\quad Y_P}_{\text{round 2}}\quad
F_Q\quad F_P J Q Y Q F Q J P Y P F P ⟹ round 1 J Q J P round 2 Y Q Y P F Q F P
Move J P J_P J P past F Q F_Q F Q and Y Q Y_Q Y Q , then move Y P Y_P Y P past F Q F_Q F Q . The allocated quantum supports are disjoint and the private bits differ, so all three primitive exchanges are checked. The remaining two layers use one ancilla each, with separate preparation and discard, and reuse ( r Q , s Q ) (r_Q,s_Q) ( r Q , s Q ) . The parallel baseline uses the same checks on its first two layers. Its four pairs of logical rounds become three, while the peak ancilla count remains two. Both concrete QPPM programs have the rounded circuit’s public weakest precondition, so the synthesized allowance survives allocation and scheduling.
Q The error-limit experiment: cost and selection
The proposal algorithm for fusion and parallel scheduling. The proposal algorithm for § 6.1 expands gates into signed Pauli turns, scans backwards from each turn until a readout or a noncommuting turn, and moves an equal axis across the intervening commuting turns, adding exponents modulo four and erasing zero turns. It then builds precedence edges for pairs that cannot be exchanged (the baseline also orders overlapping supports) and repeatedly takes ready operations in source order, draining zero-cost corrections first, into layers of disjoint supports until the ancilla budget is full, recording the adjacent swaps that realize the chosen order. The checker replays those swaps and fusions, verifies the layer supports and private resources, and checks the primitive schedule and its public weakest precondition.
Serial depth. The targets in Table 2 contain conditional T T T injections. For their serial schedule, let sd ( c ) \operatorname{sd}(c) sd ( c ) count logical rounds along the longest syntactic branch. Measurement costs one. Skip, assignment, and correction cost zero. The remaining cases are
Table 2. Selection under a requested error limit for the same QASMBench QFT circuit. Each row selects the smallest certified serial-depth bound among the feasible candidates. These are upper bounds for serial execution, not the parallel depths of Table 1.
sd ( c ▹ d ) = sd ( c ) + sd ( d ) , sd ( if e then c else d ) = max ( sd ( c ) , sd ( d ) ) , sd ( let ν = ancilla ∣ b ⟩ in c ) = sd ( c ) . (27) \begin{aligned}
\operatorname{sd}(c \mathbin{\triangleright} d) &= \operatorname{sd}(c)+\operatorname{sd}(d),\\
\operatorname{sd}(\text{if }e\text{ then }c\text{ else }d) &= \max(\operatorname{sd}(c),\operatorname{sd}(d)),\\
\operatorname{sd}(\text{let }\nu=\text{ancilla }|b\rangle\text{ in }c) &= \operatorname{sd}(c). \tag*{(27)}
\end{aligned} sd ( c ▹ d ) sd ( if e then c else d ) sd ( let ν = ancilla ∣ b ⟩ in c ) = sd ( c ) + sd ( d ) , = max ( sd ( c ) , sd ( d )) , = sd ( c ) . (27)
This cost ignores preparation latency and Pauli feedback. Induction shows that sd ( c ) \operatorname{sd}(c) sd ( c ) is at most the syntactic measurement count. The sequence case adds the induction hypotheses, and the conditional uses max ( a , b ) ≤ a + b \max(a,b)\leq a+b max ( a , b ) ≤ a + b . The existing lowering bound therefore also bounds D D D after exact measurement cleanup.
For example, the injection diagram in § 5 has one joint measurement, a conditional two-measurement phase gadget, and one magic-state readout:
Z ⊗ P ⏟ 1 U ( P ) skip ⏟ max ( 2 , 0 ) X ⏟ 1 Pauli feedback ⏟ 0 \underbrace{Z\otimes P}_{1}
\qquad
\underbrace{\begin{array}{c}U(P)\\ \text{skip}\end{array}}_{\max(2,0)}
\qquad
\underbrace{X}_{1}
\qquad
\underbrace{\text{Pauli feedback}}_{0} 1 Z ⊗ P m a x ( 2 , 0 ) U ( P ) skip 1 X 0 Pauli feedback
Equation (D-Serial) gives a bound of four. Each H or CNOT expands to three two-measurement gadgets, S or its inverse to one, and a public readout to one measurement. Thus, with gate counts
n H , n C X , n S , n T , n M , n_H, n_{\mathrm{CX}}, n_S, n_T, n_M, n H , n CX , n S , n T , n M ,
sd ( d ) ≤ sd ‾ = 6 n H + 6 n C X + 2 n S + 4 n T + n M . \operatorname{sd}(d) \le\overline{\operatorname{sd}} = 6n_H + 6n_{\mathrm{CX}} + 2n_S + 4n_T + n_M. sd ( d ) ≤ sd = 6 n H + 6 n CX + 2 n S + 4 n T + n M .
For the 10 − 2 10^{-2} 1 0 − 2 row, the emitted circuit has 472 H gates, 12 CNOTs, 222 S-class gates, 471 T-class gates, and four readouts. Substitution gives
sd ‾ = 6 ( 472 ) + 6 ( 12 ) + 2 ( 222 ) + 4 ( 471 ) + 4 = 5,236. \overline{\operatorname{sd}} = 6(472) + 6(12) + 2(222) + 4(471) + 4 = 5{,}236. sd = 6 ( 472 ) + 6 ( 12 ) + 2 ( 222 ) + 4 ( 471 ) + 4 = 5 , 236.
The counts include inverse S and T gates. Pauli corrections add zero. Each whole-circuit certificate checks this sum for the emitted instruction list and instantiates the depth bound for its concrete compiled program. It also proves the source-effect allowance for the row’s requested error limit. The quantum semantics still includes all ideal supplied magic inputs, even though their preparation is outside this cost model.
Checking a selection. For a requested limit of 10 − 3 10^{-3} 1 0 − 3 , the coarsest candidate’s certified allowance is too large. The other two allowances meet the request, and 7,540 < 9,184 selects the middle candidate (Figure 19 ). Thus selection minimizes the certified depth bound among feasible proposals. It need not minimize their error allowances. A complete circuit certificate checks the selected target against this requested limit.
Figure 19. Selection for a requested limit between the limits of Table 2 . Comparisons use the exact rational certified allowances. The smallest allowance belongs to the finest candidate. The smallest feasible serial-depth bound belongs to the middle candidate.
The boundary tests accept a requested limit equal to the certificate’s exact rational allowance and reject a limit just below it. They also reject unchecked candidates and return no result when the feasible set is empty. Three deliberately understated allowance claims are rejected by the kernel. Source and target instruction lists are compared with the exported certificate records and the emitted QASM. The reported limits, the 10 − 3 10^{-3} 1 0 − 3 example, and the limits at and just below each candidate’s allowance have checked finite selection certificates. Each checks feasibility and the least depth bound, or verifies that every candidate exceeds the request. An infeasible choice, a feasible choice with a larger bound, and an incorrect empty result are rejected. Nine further mutations alter the stored evidence, including error and depth claims, output gates, and the candidate collection. All nine mutations are rejected.
Reading the selected allowance. Let c c c be the typed QFT source, with inputs ( q 0 , q 1 , q 2 , q 3 ) (q_0,q_1,q_2,q_3) ( q 0 , q 1 , q 2 , q 3 ) and ( r 0 , r 1 , r 2 , r 3 ) (r_0,r_1,r_2,r_3) ( r 0 , r 1 , r 2 , r 3 ) , and d d d the selected middle target. Its classical inputs prepend private locations a , b a,b a , b . Its certificate uses k = 672 k=672 k = 672 ideal magic inputs and the allowance ε ^ = 18308100000009 3125000000000000000 \widehat{\varepsilon}=\frac{18308100000009}{3125000000000000000} ε = 3125000000000000000 18308100000009 . We derive a bound for the event E ( t ) ≡ t ( r 0 ) = ⋯ = t ( r 3 ) = 0 E(t)\equiv t(r_0)=\cdots=t(r_3)=0 E ( t ) ≡ t ( r 0 ) = ⋯ = t ( r 3 ) = 0 .
First choose the effect [ E ] [E] [ E ] , which is identity on that public record and zero on the others. For a positive trace-one data state ρ \rho ρ and initial store s s s , extend s s s by two zero private bits to obtain s ~ \widetilde{s} s . The two executions are
( s , ρ ) → c p c = Pr c [ E ] , (s,\rho)\xrightarrow{c}p_c=\Pr_c[E], ( s , ρ ) c p c = c Pr [ E ] ,
( s ~ , V k ρ V k † ) → d p d = Pr d [ E ∘ π ] . (\widetilde{s},V_k\rho V_k^\dagger)\xrightarrow{d}p_d=\Pr_d[E\circ\pi]. ( s , V k ρ V k † ) d p d = d Pr [ E ∘ π ] .
Second, pull the event back through each program. Duality gives p c = Re tr ( ρ W c ( [ E ] ) ( s ) ) p_c=\operatorname{Re}\operatorname{tr}(\rho W_c([E])(s)) p c = Re tr ( ρ W c ([ E ]) ( s )) and p d = Re tr ( ρ C E ( s ) ) p_d=\operatorname{Re}\operatorname{tr}(\rho C_E(s)) p d = Re tr ( ρ C E ( s )) , where C E ( s ) = V k † wp ( d , D k ( [ E ] ) ) ( s ~ ) V k C_E(s)=V_k^\dagger\operatorname{wp}(d,D_k([E]))(\widetilde{s})V_k C E ( s ) = V k † wp ( d , D k ([ E ])) ( s ) V k . The latter probability sums over all private outcomes.
Finally, pair the certificate’s two matrix inequalities with ρ \rho ρ :
∣ p c − p d ∣ = ∣ Re tr ( ρ ( W c ( [ E ] ) ( s ) − C E ( s ) ) ) ∣ ≤ ε ^ tr ( ρ ) = ε ^ < 5.859 × 10 − 6 . \begin{aligned}
\lvert p_c-p_d\rvert
&=\left\lvert\operatorname{Re}\operatorname{tr}\left(\rho\left(W_c([E])(s)-C_E(s)\right)\right)\right\rvert\\
&\le\widehat{\varepsilon}\operatorname{tr}(\rho)=\widehat{\varepsilon}<5.859\times10^{-6}.
\end{aligned} ∣ p c − p d ∣ = ∣ Re tr ( ρ ( W c ([ E ]) ( s ) − C E ( s ) ) ) ∣ ≤ ε tr ( ρ ) = ε < 5.859 × 1 0 − 6 .
Changing E E E gives the same bound for any event on the four public output bits.
R A tight effect allowance
A tight approximation allowance
With inputs Γ = ( ) \Gamma=() Γ = ( ) , Δ = ( r ) \Delta=(r) Δ = ( r ) , let f f f prepare ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ , measure X X X into r r r , and discard the qubit. Let z z z assign zero to r r r . Both have zero surviving quantum wires and one classical bit. A zero-qubit operator is a 1 × 1 1\times1 1 × 1 matrix, so an effect can be identified with a scalar between zero and one for each final store. Figure 20 places the circuit beside its syntax and output probabilities.
Step 1: compute the branch weights. The projectors applied to the prepared state are
Π 0 X ∣ 0 ⟩ = 1 2 ( ∣ 0 ⟩ + ∣ 1 ⟩ ) , Π 1 X ∣ 0 ⟩ = 1 2 ( ∣ 0 ⟩ − ∣ 1 ⟩ ) . \Pi^X_0\lvert0\rangle=\frac{1}{2}(\lvert0\rangle+\lvert1\rangle),\qquad\Pi^X_1\lvert0\rangle=\frac{1}{2}(\lvert0\rangle-\lvert1\rangle). Π 0 X ∣ 0 ⟩ = 2 1 (∣ 0 ⟩ + ∣ 1 ⟩) , Π 1 X ∣ 0 ⟩ = 2 1 (∣ 0 ⟩ − ∣ 1 ⟩) .
Each branch has squared norm 1 / 2 1/2 1/2 . After discarding the qubit, the output consists of two scalar blocks of weight 1 / 2 1/2 1/2 , one for each value of r r r . For any assertion A A A , write A b ( s ) = A ( s [ r ↦ b ] ) A_b(s)=A(s[r\mapsto b]) A b ( s ) = A ( s [ r ↦ b ]) . The backward calculation is
{ 1 2 ( A 0 + A 1 ) } f { A } , { A 0 } z { A } . (28) \left\{\frac{1}{2}(A_0+A_1)\right\}\ f\ \{A\},\qquad\{A_0\}\ z\ \{A\}. \tag*{(28)} { 2 1 ( A 0 + A 1 ) } f { A } , { A 0 } z { A } . (28)
The preconditions in these judgments are exactly wp ( f , A ) \operatorname{wp}(f,A) wp ( f , A ) and wp ( z , A ) \operatorname{wp}(z,A) wp ( z , A ) , respectively. Equations (W-Anc), (W-Meas), and (W-Asgn) calculate them for arbitrary assertions before imposing the inequalities required of effects. Step 2: prove a bound for every effect. Subtracting the two expressions in Equation (28) gives ( A 1 − A 0 ) / 2 (A_1-A_0)/2 ( A 1 − A 0 ) /2 . For an effect, 0 ⪯ A b ⪯ I 0 \preceq A_b \preceq I 0 ⪯ A b ⪯ I , so
1 2 I − 1 2 ( A 1 − A 0 ) = 1 2 ( ( I − A 1 ) + A 0 ) ⪰ 0 , \frac{1}{2}I-\frac{1}{2}(A_1-A_0)=\frac{1}{2}\left((I-A_1)+A_0\right)\succeq0, 2 1 I − 2 1 ( A 1 − A 0 ) = 2 1 ( ( I − A 1 ) + A 0 ) ⪰ 0 ,
and the same calculation with 0 and 1 exchanged bounds the opposite difference. Both approximation inequalities hold with ε = 1 / 2 \varepsilon=1/2 ε = 1/2 . This proof uses only positivity, closure under addition, and multiplication by a nonnegative scalar. It applies to every effect.
Step 3: exhibit a matching lower bound. Choose the event E ( s ) = s ( r ) E(s)=s(r) E ( s ) = s ( r ) , whose effect has A 0 = 0 A_0=0 A 0 = 0 and A 1 = I A_1=I A 1 = I . Its probability is 1 / 2 1/2 1/2 under f f f and zero under z z z . Any uniform allowance must bound this event difference, so it must be at least 1 / 2 1/2 1/2 . The upper and lower theorems together establish sharpness.
Step 4: retain the classical blocks in the distance. The false and true blocks differ by − 1 / 2 -1/2 − 1/2 and 1 / 2 1/2 1/2 , giving the distance shown in Figure 20 . Summing over the records first would cancel these differences, although a continuation can distinguish the programs by reading r r r .
Composition of approximation allowances
The same local certificate can be used in two different program contexts. Sequentially performing two fair-bit commands and replacing both by assignments gives
f ∥ f ≈ 1 / 2 + 1 / 2 z ∥ z . f \mathbin{\mathbin{\|}} f \mathrel{\approx_{1/2+1/2}} z \mathbin{\mathbin{\|}} z. f ∥ f ≈ 1/2 + 1/2 z ∥ z .
Theorem 4 gives allowance 1 without requiring distinct destinations. Here the exact allowance is smaller because the second command overwrites the first result. For any assertion A A A , let F = wp ( f , A ) = 1 2 ( A 0 + A 1 ) F=\operatorname{wp}(f,A)=\frac{1}{2}(A_0+A_1) F = wp ( f , A ) = 2 1 ( A 0 + A 1 ) . Substituting either value for the initial r r r leaves F F F unchanged, so (W-Seq) gives
wp ( f ▹ f , A ) ( s ) = 1 2 ( F ( s [ r ↦ 0 ] ) + F ( s [ r ↦ 1 ] ) ) = F ( s ) . \operatorname{wp}(f \mathbin{\triangleright} f,A)(s)=\frac{1}{2}\left(F(s[r\mapsto0])+F(s[r\mapsto1])\right)=F(s). wp ( f ▹ f , A ) ( s ) = 2 1 ( F ( s [ r ↦ 0 ]) + F ( s [ r ↦ 1 ]) ) = F ( s ) .
Thus f ▹ f ≡ f f\mathbin{\triangleright}f\equiv f f ▹ f ≡ f . Likewise, wp ( z ▹ z , A ) = wp ( z , A ) \operatorname{wp}(z\mathbin{\triangleright}z,A)=\operatorname{wp}(z,A) wp ( z ▹ z , A ) = wp ( z , A ) , so z ▹ z ≡ z z\mathbin{\triangleright}z\equiv z z ▹ z ≡ z . The two sequences therefore satisfy f ▹ f ≈ 1 / 2 z ▹ z f\mathbin{\triangleright}f\mathrel{\approx_{1/2}}z\mathbin{\triangleright}z f ▹ f ≈ 1/2 z ▹ z . The event [ r = 1 ] [r=1] [ r = 1 ] again witnesses a difference of 1 / 2 1/2 1/2 . The additive rule supplies a valid bound, while these equalities establish the tight one.
Step 1: select the branch before overwriting its guard. Consider c c c , which runs f f f if r = 1 r=1 r = 1 and z z z otherwise. Replace only its true arm to obtain d d d . Theorem 4 gives the maximum allowance, max ( 1 / 2 , 0 ) = 1 / 2 \max(1/2,0)=1/2 max ( 1/2 , 0 ) = 1/2 :
f ≈ 1 / 2 z z ≈ 0 z f\mathrel{\approx_{1/2}}z \qquad z\mathrel{\approx_0}z f ≈ 1/2 z z ≈ 0 z
Both arms overwrite r r r , but the fork reads its initial value only once. The two runs therefore select corresponding arms.
Step 2: calculate the weakest preconditions. Using (W-If) and Equation (28) , for any assertion A A A ,
wp ( c , A ) ( s ) = { 1 2 ( A 0 ( s ) + A 1 ( s ) ) s ( r ) = 1 , A 0 ( s ) s ( r ) = 0 , wp ( d , A ) ( s ) = A 0 ( s ) . \operatorname{wp}(c,A)(s)=
\begin{cases}
\frac{1}{2}\left(A_0(s)+A_1(s)\right) & s(r)=1,\\
A_0(s) & s(r)=0,
\end{cases}
\qquad
\operatorname{wp}(d,A)(s)=A_0(s). wp ( c , A ) ( s ) = { 2 1 ( A 0 ( s ) + A 1 ( s ) ) A 0 ( s ) s ( r ) = 1 , s ( r ) = 0 , wp ( d , A ) ( s ) = A 0 ( s ) .
For an effect, the difference lies between − 1 2 I -\frac{1}{2}I − 2 1 I and 1 2 I \frac{1}{2}I 2 1 I in the first case and is zero in the second. The maximum covers both initial stores. Taking A = [ r = 1 ] A=[r=1] A = [ r = 1 ] and s ( r ) = 1 s(r)=1 s ( r ) = 1 gives probabilities 1 / 2 1/2 1/2 and zero, so no smaller uniform allowance suffices.
Step 3: check why the guard must agree. Negating only the guard gives a different program:
c ¬ : = ¬ r c_{\neg}:=\neg r c ¬ := ¬ r
s ( r ) = 0 s(r)=0 s ( r ) = 0 : Pr c [ r = 1 ] = 0 \Pr_{c}[r=1]=0 Pr c [ r = 1 ] = 0 , Pr c ¬ [ r = 1 ] = 1 2 \Pr_{c_{\neg}}[r=1]=\frac{1}{2} Pr c ¬ [ r = 1 ] = 2 1 .
The premises f ≈ 0 f f\approx_{0}f f ≈ 0 f and z ≈ 0 z z\approx_{0}z z ≈ 0 z still hold, but c ̸ ≈ 0 c ¬ c\not\approx_{0}c_{\neg} c ≈ 0 c ¬ : the displayed event forces an allowance of at least 1 / 2 1/2 1/2 . Thus branchwise equivalence alone cannot justify changing a guard.
The general composition argument. Let c , d , c ′ , d ′ c,d,c',d' c , d , c ′ , d ′ share input contexts, with c ≈ ε c ′ c\approx_{\varepsilon}c' c ≈ ε c ′ and d ≈ δ d ′ d\approx_{\delta}d' d ≈ δ d ′ , and let B B B be an effect. The sequential transformer uses (W-Seq). Each vertical link below is a local approximation premise. Effect preservation makes wp ( d , B ) \operatorname{wp}(d,B) wp ( d , B ) an admissible observation for the first link, which contributes ε I \varepsilon I ε I . Monotonicity of wp ( c ′ , ⋅ ) \operatorname{wp}(c',\mathord{\cdot}) wp ( c ′ , ⋅ ) applies to the second link. Linearity and identity preservation pull its δ I \delta I δ I slack through unchanged.
c ▹ d ≈ ε + δ c ′ ▹ d ′ c\mathbin{\triangleright}d\approx_{\varepsilon+\delta}c'\mathbin{\triangleright}d' c ▹ d ≈ ε + δ c ′ ▹ d ′
wp ( c , wp ( d , B ) ) ⊑ wp ( c ′ , wp ( d ′ , B ) ) + ( ε + δ ) I (29) \operatorname{wp}(c,\operatorname{wp}(d,B))
\sqsubseteq\operatorname{wp}(c',\operatorname{wp}(d',B))+(\varepsilon+\delta)I \tag*{(29)} wp ( c , wp ( d , B )) ⊑ wp ( c ′ , wp ( d ′ , B )) + ( ε + δ ) I (29)
Transitivity adds the slacks. Reversing the inequalities gives the second half of the approximation relation. By (W-Anc), we lift the effect by I 2 ⊗ B I_{2}\otimes B I 2 ⊗ B , apply the body certificate, and compress by the fixed preparation E b E_b E b . Because E b † I E b = I E_b^{\dagger}I E_b=I E b † I E b = I , the slack remains ε I \varepsilon I ε I .
Trace-distance characterization
The distance theorem connects these local reasoning steps to an operational observation on all final records. For a fixed positive input, form the Hermitian differences Δ ( t ) = I c ( s , ρ , t ) − I d ( s , ρ , t ) \Delta^{(t)}=\mathcal{I}_{c}(s,\rho,t)-\mathcal{I}_{d}(s,\rho,t) Δ ( t ) = I c ( s , ρ , t ) − I d ( s , ρ , t ) . Total trace preservation gives ∑ t tr ( Δ ( t ) ) = 0 \sum_t\operatorname{tr}(\Delta^{(t)})=0 ∑ t tr ( Δ ( t ) ) = 0 . It does not give tr ( Δ ( t ) ) = 0 \operatorname{tr}(\Delta^{(t)})=0 tr ( Δ ( t ) ) = 0 for each t t t . The fair-bit example is an explicit counterexample to that stronger premise. Appendix N gives its two numerical blocks, their spectral projectors, and concrete instances of specification transfer and scope congruence.
The spectral proof chooses the assertion that projects each block onto its positive eigenspaces. With Δ ( t ) = Δ ( t ) + − Δ ( t ) − \Delta^{(t)}=\Delta^{(t)+}-\Delta^{(t)-} Δ ( t ) = Δ ( t ) + − Δ ( t ) − its positive/negative decomposition, the observation diagram is
Δ ( t ) ⟶ tr ( Π t + Δ ( t ) ) = tr ( Δ ( t ) + ) , ∑ t tr ( Δ ( t ) + ) = 1 2 ∑ t ∥ Δ ( t ) ∥ 1 . \Delta^{(t)}\longrightarrow\operatorname{tr}(\Pi_t^{+}\Delta^{(t)})=\operatorname{tr}(\Delta^{(t)+}),\qquad
\sum_t\operatorname{tr}(\Delta^{(t)+})=\frac{1}{2}\sum_t\lVert\Delta^{(t)}\rVert_1. Δ ( t ) ⟶ tr ( Π t + Δ ( t ) ) = tr ( Δ ( t ) + ) , t ∑ tr ( Δ ( t ) + ) = 2 1 t ∑ ∥ Δ ( t ) ∥ 1 .
The last equality uses equality of the total positive and negative masses. Every other effect lies between zero and identity and cannot yield a larger pairing. Applying the same argument to − Δ ( t ) -\Delta^{(t)} − Δ ( t ) controls the absolute difference. Thus the half-sum is characterized by the largest difference over store-indexed effects. The artifact proves this characterization, then applies the two approximation inequalities and the trace-pairing order lemma to obtain the normalized output-distance bound.
The local effect allowances therefore determine both the output trace-distance bound and the weakening of a Hoare precondition.
A local logical-fault contract
Take input registers Γ = ( q ) , Δ = ( r ) \Gamma=(q),\Delta=(r) Γ = ( q ) , Δ = ( r ) , with r r r reserved for the final observation. The qubit suffers an X X X fault with probability p p p , where 0 ≤ p ≤ 1 0\leq p\leq1 0 ≤ p ≤ 1 . Its ideal transformer is the identity. The noisy transformer is N p ( B ) = ( 1 − p ) B + p X B X N_p(B) = (1-p)B + pXBX N p ( B ) = ( 1 − p ) B + pX B X . For an arbitrary effect, the two required positive differences are
N p ( B ) + p I − B = p ( ( I − B ) + X B X ) ⪰ 0 , N_p(B) + pI - B = p\left((I-B) + XBX\right) \succeq0, N p ( B ) + p I − B = p ( ( I − B ) + X B X ) ⪰ 0 ,
B + p I − N p ( B ) = p ( B + ( I − X B X ) ) ⪰ 0. B + pI - N_p(B) = p\left(B + (I-XBX)\right) \succeq0. B + p I − N p ( B ) = p ( B + ( I − X B X ) ) ⪰ 0.
Here conjugation preserves effects. The same calculation works for the weakest-precondition transformer of any QPPM command in place of X B X XBX X B X . For B = ∣ 0 ⟩ ⟨ 0 ∣ B = |0\rangle\langle0| B = ∣0 ⟩ ⟨ 0∣ , this contract has a directly observable instance:
∣ 0 ⟩ ⟨ 0 ∣ → N p ( 1 − p ) ∣ 0 ⟩ ⟨ 0 ∣ + p ∣ 1 ⟩ ⟨ 1 ∣ , |0\rangle\langle0| \xrightarrow{N_p} (1-p)|0\rangle\langle0| + p|1\rangle\langle1|, ∣0 ⟩ ⟨ 0∣ N p ( 1 − p ) ∣0 ⟩ ⟨ 0∣ + p ∣1 ⟩ ⟨ 1∣ ,
Pr [ Z r = 0 ] = 1 − p . \Pr\left[ Z_{r=0} \right] = 1-p. Pr [ Z r = 0 ] = 1 − p .
This is an example of a local contract, not an assumption that all logical noise is a stochastic Pauli fault.
The theorem sums local effect bounds. When the same bound is expressed as trace norm on trace-one states, its allowance is twice as large:
2 ε + 2 ( p L N L + p T N T + p I N I ) . 2\varepsilon+ 2(p_LN_L + p_TN_T + p_IN_I). 2 ε + 2 ( p L N L + p T N T + p I N I ) .
A trace-norm synthesis allowance E s y n t h E_{\mathrm{synth}} E synth therefore appears as E s y n t h + 2 ( p L N L + p T N T + p I N I ) E_{\mathrm{synth}} + 2(p_LN_L + p_TN_T + p_IN_I) E synth + 2 ( p L N L + p T N T + p I N I ) , while a probability bound uses half that quantity. Converting units does not supply a missing noise contract.
For surface-code or lifted-product surgery, the implementation must additionally specify the encoding, extraction circuit, decoder, record interpretation, and schedule. After encoding inputs and interpreting outputs, each implemented logical operation must satisfy the stated local contract. Logical equivalence of two QPPM programs then preserves their synthesis allowance. Their noise allowances must be recalculated from their respective implementations. In particular, disjoint logical supports need not yield disjoint routing regions or independent decoder resources.
Additional verified benchmark results
The large-suite corpus comprises all 56 canonical QASMBench inputs at the pinned revision, of which 55 parse successfully. The valid inputs span 28–433 data qubits. This appendix reports completed source-error certificates for 23 of those 55 inputs and depth certificates for all eleven selected static Clifford inputs. These are the certified subsets of the fixed corpus. The tables below list only completed results.
Table 8 gives fifteen complete exact-source certificates.
Table 8. Verified exact-source compilations. Instructions count the Clifford+T T T source after macro expansion and barrier erasure. The PPM bound counts logical measurements, not parallel depth. The complete 433-qubit adder and 280-qubit Bernstein–Vazirani certificates are described below.
The checked adders and multipliers contain T T T gates. Their expansion equalities are checked in blocks of 128 source steps and composed over the complete list. Each certificate proves the typed expansion, PPM lowering, public Hoare specification, and zero approximation error, assuming ideal magic states for T T T instructions. Exported input records match the independently parsed source expansion. Parsing and macro inlining remain outside the proof. A direct cost calculation is proved equal to the measurement bound, avoiding construction of every gadget.
Register-controlled sources. The four cc inputs compare a public n n n -bit register with zero or 2 n − 1 2^{n-1} 2 n − 1 . Both tests constrain every register bit. They expand into nested core conditionals as in Appendix § 16 , for every initial store. Shared predicates avoid repeating the tests. Validity and measurement bounds are checked in blocks of 32 steps.
Decimal phases. The inputs i s i n g _ n 34 ising\_n34 i s in g _ n 34 and i s i n g _ n 42 ising\_n42 i s in g _ n 42 contain 67 and 83 distinct angles, including zero. Each nonzero angle occurs twice. Decimal literals denote exact rational radians. For example, 1.6751132 = 4187783 / 2500000 1.6751132 = 4187783/2500000 1.6751132 = 4187783/2500000 , without a factor of π \pi π . Ross–Selinger synthesis proposes each gate sequence at tolerance 10 − 8 10^{-8} 1 0 − 8 . Exact coefficient calculations and Taylor remainders establish its allowance. For n ∈ { 34 , 42 } n \in\{34, 42\} n ∈ { 34 , 42 } , the complete compilation satisfies
Table 9. Every large-suite input whose only missing frontend feature was classical control. Source steps include barriers. Each successful check preserves every register condition and proves a bound on primitive measurements. These are not parallel-depth results.
I s i n g n → ε n = ∑ i , j ε i C l i f f o r d + T → 0 Q P P M . \mathrm{Ising}_n \xrightarrow{\varepsilon_n=\sum_{i,j}\varepsilon_i} \mathrm{Clifford}+T \xrightarrow{0} \mathrm{QPPM}. Ising n ε n = ∑ i , j ε i Clifford + T 0 QPPM .
The sum includes every source rotation occurrence. The table reports source steps, rotations, emitted Clifford+T T T instructions, ideal magic inputs, and the proved effect-error allowance.
Table 10.
Each proof retains the 2 n 2n 2 n -bit public interface, including the unused register, and exports every source step and output instruction for comparison with the parsed circuits. Each angle certificate has a 120-second checking limit. Complete composition and export have a separate 600-second limit. Checks use two workers and a 6,000 MB allocation limit, with at most two running concurrently. These are source-error allowances. The parallel-depth experiment remains separate. The fifteen exact-source rows, four register-controlled sources, two Ising sources, 433-qubit adder, and 280-qubit Bernstein–Vazirani circuit give the 23 distinct source-error certificates reported above.
Parallel measurement schedules. The depth experiment includes all eleven static Clifford inputs selected before scheduling. Each typed input retains every gate and readout. Parsing and removal of identity barriers are external to the proof. The support-disjoint baseline and commutation/fusion optimizer each use four scoped ancillas and eight private bits. Replay checks every commutation and classical-store guard. Composition proves resource validity, primitive counts, logical depth, and public weakest-precondition equality for the complete program.
Table 10 (PDF p. 60). Complete depth certificates for all eleven selected large Clifford inputs. D 0 D_0 D 0 schedules disjoint supports. D 1 D_1 D 1 adds commutation and fusion. Both use four ancillas and eight private bits. Every row certifies the allocated programs, the displayed depths, preservation of public specifications, and zero source error under ideal logical operations. Direct and modular checking establish the same contracts.
Composing larger certificates. Modular checking splits rewrite replay and readout proofs into separately checked parts. Their composition establishes the complete source correspondence and public weakest-precondition equality. The five modular depth results in Table 10 use this construction without changing the circuits or resource budgets. For the 280-qubit Bernstein–Vazirani circuit, fusion and scheduling reduce logical rounds from 1,069 to 715 and measurements from 4,545 to 3,125.
The same method checks the complete 433-qubit adder source: 7,203 typed steps, including one identity barrier, emit 7,202 Clifford+T T T instructions and require 2,688 ideal magic inputs. Its PPM target has a proved bound of 34,513 measurements and zero approximation error. This is a source-compilation result. It does not assert a parallel schedule for the adder.
These counts describe ideal logical operations. Physical placement, routing, and decoding require a separate implementation satisfying Theorem 5 . The artifact records the checking procedures and resource limits.