Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 324 / 1

A $Z$ measurement is a quantum measurement in the computational basis. To measure $X$, apply a Hadamard gate, measure $Z$, and apply another Hadamard gate to the measured qubit. Since $HXH=Z$, this gives the $X$ outcome and leaves the qubit in the corresponding $X$ eigenstate.

Prepare an ancilla qubit in $|0⟩$. To measure $X\otimes X$, apply a Hadamard gate to each data qubit, apply a controlled-NOT gate from each data qubit to the ancilla, measure the ancilla in the computational basis, and apply a Hadamard gate to each data qubit again. The ancilla records the parity of the two rotated computational-basis bits, so outcome $0$ corresponds to eigenvalue $+1$ and outcome $1$ to eigenvalue $-1$. The data register is projected by $[I+(-1{)}^{s}X\otimes X]/2$, so its complete post-measurement state is retained. For $Z\otimes X$, perform the same ancilla-assisted Pauli measurement but apply the basis-changing Hadamard gates only to the second data qubit.

Since $P|\psi ⟩={\lambda }_P|\psi ⟩$, $P^2=I$, and $P$ anticommutes with $Q$,so the expectation value of $Q$ is zero. The two spectral projectors of the Hermitian Pauli operator $Q$ are $(I\pm Q)/2$, and hence the Born rule gives

Put $a={\lambda }_P$ and $b={\lambda }_Q$. The Pauli operators are Hermitian and satisfy $P^2=Q^2=I$ and $PQ+QP=0$, soThus $V$ is a unitary operator. For every Pauli operator $R$, according as $R$ commutes or anticommutes with $P$ and $Q$, expansion of $VRV$ gives one of $\pm R$ or $\pm RPQ$, up to the phase that makes it Hermitian. It is therefore another Pauli operator, so $V$ normalizes the Pauli group and is a Clifford operation. Finally,which is the normalized projection onto the eigenvalue-$b$ eigenspace of $Q$. Hence $V$ maps the eigenvalue-${\lambda }_P$ eigenspace of $P$ onto the eigenvalue-${\lambda }_Q$ eigenspace of $Q$.

A Pauli-based computation starts with the supplied nonstabilizer resource state $|\alpha ⟩$ 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({\lambda }_P,{\lambda }_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.

Propagate each output observable backwards through the Clifford circuit and writeThe $Q_i$ are mutually commuting Pauli operators, and measuring them on $|0{⟩}^{\otimes n}\otimes |\varphi ⟩$ has exactly the required joint output distribution. Initially the first $n$ qubits are constrained by the stabilizer generators $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 $|\varphi ⟩$. 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\le 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 $Z_1,\dots ,Z_n$ outputs, is therefore a weak classical simulation of a quantum circuit with the same joint distribution.