Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 324 / 3

Store a tensor-product element of the Pauli group asThe phases of the original single-qubit factors can all be accumulated into $i^s$. This binary phase representation of a Pauli string uses $2n+2$ bits. It retains phases, which must not be dropped when computing probabilities later.

For the conjugation convention $U^{†}PU$ in the question, direct multiplication of the two-by-two matrices givesandThese backward Pauli updates for Hadamard and phase gates use $S^{†}PS$, not $SP{S}^{†}$. On the affected line $j$, the updates areAll phases are reduced modulo four and the updates use the old bits.

For a Controlled-Z gate on lines $j,k$, its diagonal action givesFor the controlled-Z update in the binary phase representation, conjugation respects products, so these determine the rule for every Pauli operator on those lines. In the chosen ordered $XZ$ convention it isThe phase arises when a newly introduced $Z_k$ is moved past $X_k$. For instance $X_j{X}_k$ becomes $-X_j{Z}_j{X}_k{Z}_k$, so this sign matters.

The untouched factors are unchanged. Each Clifford operation therefore needs only a fixed number of local bit updates; reconstructing the requested full list takes $O(n)$ time. Put the final phase into the first factor, which is permitted because the single-qubit Pauli group includes all multiples by $\pm 1,\pm i$. The classical cost is polynomial, despite the exponentially large matrix of the operation on the full state space.

The computational-basis projectors on the first qubit areThe Pauli Z gate acts as $+1$ on the first subspace and $-1$ on the second, so $Z_1={\Pi }_0-{\Pi }_1$. By the Born rule, $p_b=⟨\psi |{\Pi }_b|\psi ⟩$. Therefore the expectation determines the output probabilities:The normalization supplies $p_0+p_1=1$; no product-state assumption is needed for this identity.

Write $|a⟩={⨂}_j|a_j⟩$. Instead of storing the output vector, use Heisenberg propagation of a Pauli observable through a Clifford circuit:Initialize the compact Pauli group representation at $Z_1$ and conjugate successively by $U_N,U_{N-1},\dots ,U_1$, in that order, using $P\mapsto U_j^{†}P{U}_j$. This giveswith $O(N+n)$ local-update work and $O(n)$ storage. The resulting Pauli operator is Hermitian, so we can express it as $P=\eta {⨂}_j{\sigma }_j$, where $\eta \in \{+1,-1\}$ and each ${\sigma }_j$ is $I,X,Y$ or $Z$. Any factors $XZ$ in the representation from part (i) are converted using $XZ=-iY$, with their phases absorbed into $\eta$.

The product state input now makes the expectation factorize:Each factor is a two-by-two matrix calculation. More explicitly, for $|a_j⟩={\alpha }_j|0⟩+{\beta }_j|1⟩$, the three nontrivial expectations are $2\mathrm{Re}({\overline{\alpha }}_j{\beta }_j)$, $2\mathrm{Im}({\overline{\alpha }}_j{\beta }_j)$, and $|{\alpha }_j{|}^2-|{\beta }_j{|}^2$ for $X,Y,Z$, respectively.

Thus this single-output process has a strong classical simulation in polynomial time, even when the individual input states are not stabilizer states. As usual, the given state identities must provide efficiently computable amplitudes. With finite-precision inputs, each factor can be evaluated to error $\delta /n$ and its approximation clipped to $[-1,1]$ to obtain the final expectation to error at most $\delta$, because all factors lie in $[-1,1]$. The required extra precision is only $O(\log (n/\delta ))$ bits. Exact evaluation applies when the input descriptions support exact arithmetic. This avoids silently assigning a finite exact-computation cost to arbitrary unspecified real numbers.

Once the probabilities are known, a classical randomized computation can reproduce this measured bit. The argument concerns the specified one-qubit output; it does not assert that every joint measurement distribution for arbitrary product inputs can be simulated by this same single-observable calculation.

Use GHZ preparation with Hadamard and controlled-Z gates for $n\ge 2$. Apply a Hadamard gate to the first qubit, then a controlled-NOT gate from that qubit to each of the other $n-1$ qubits. Every controlled-NOT can be written in the allowed gate set asIndeed conjugating the target $Z$ by $H$ makes the controlled phase into a controlled $X$. The rightmost gate acts first. Consequently the Clifford circuit uses $1+3(n-1)$ allowed gates and givesFor every chosen qubit $j$, tracing out the other qubits yields ${\rho }_j=\frac{1}{2}(|0⟩⟨0|+|1⟩⟨1|)=I/2$. Equivalently, across that qubit versus the rest, the displayed state is a Schmidt decomposition with two nonzero coefficients $1/\sqrt{2}$. It is therefore entangled across every such bipartition.

Entanglement does not prevent the polynomial single-output simulation from part (iii). The simulation follows the measured observable rather than claiming that the intermediate states remain product states. When $n=1$, there is no remaining subsystem and the requested entanglement is impossible; the construction and claim require $n\ge 2$.