A Pauli-based computation starts with the supplied nonstabilizer resource state

∣ α ⟩

and performs an adaptive sequence of mutually commuting measurements of Pauli observables. Each outcome is recorded classically and may determine the next Pauli observable and the final classical output. When a proposed observable anticommutes with a previously fixed Pauli constraint, its outcome is uniformly random by part b(i); one samples that outcome and uses the Clifford operation

V (λ_{P}, λ_{Q})

from part b(ii) to update the Clifford frame. This replaces the old constraint by the newly measured one while preserving the distribution and the post-measurement state represented by the computation.

ii

Solution

Propagate each output observable backwards through the Clifford circuit and write

Q_{i} = C^{†} Z_{i} C .

The

Q_{i}

are mutually commuting Pauli operators, and measuring them on

∣0 ⟩^{\otimes n} \otimes ∣ ϕ ⟩

has exactly the required joint output distribution. Initially the first

n

Z_{1}, \dots, Z_{n}

. Process the

Q_{i}

in order. If

Q_{i}

anticommutes with a current generator, part b gives a uniform outcome and a Clifford operation that replaces that generator by

Q_{i}

; this step needs no measurement on

∣ ϕ ⟩

. If

Q_{i}

commutes with every current generator, multiply it by known generators to remove its action on the first register. What remains is a Pauli observable

P_{j}

on the

t

resource qubits and is measured there. The nontrivial

P_{j}

are independent and mutually commuting. An independent commuting family of Pauli operators on

t

qubits has at most

t

members, so

s \leq t

. All effective observables are fixed by the original commuting family; the sampled outcomes merely update the classical Clifford frame. The resulting nonadaptive Pauli-based computation, followed by the stated