Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 324 (Quantum Computation)

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.

An $n$-qubit stabilizer state is the unique simultaneous $+1$ eigenstate of an abelian group $G$ of Pauli operators having $2^n$ elements and not containing $-I$. The group $G$ is the state's stabilizer group; equivalently, it is generated by $n$ independent commuting Hermitian Pauli operators.

The state $|001⟩$ has independent stabilizer generators $ZII$, $IZI$, and $-IIZ$. Its complete stabilizer group isFor $|{\Phi }^{+}⟩\otimes |+⟩$, take the generators $XXI$, $ZZI$, and $IIX$. Their products giveIn particular $(XX)(ZZ)=-YY$, which accounts for the two minus signs.

The Gottesman--Knill theorem states that stabilizer-state preparation, Clifford circuits, and adaptive measurements of Pauli observables can be simulated in classical polynomial time. For $|{\Psi }_{\mathrm{in}}⟩=|+{⟩}^{\otimes 3}$, choose generators $XII$, $IXI$, and $IIX$. With each row written as $[x_1{x}_2{x}_3\mid z_1{z}_2{z}_3]$, its sign-free stabilizer tableau isConjugating these generators successively by ${\mathrm{CNOT}}_{21}$, $H_2\otimes H_3$, and ${\mathrm{CNOT}}_{13}$ gives $XIX$, $XZX$, and $ZIZ$. Hence the output tableau, again ignoring signs, is

At each qubit, two matrices from $\{I,X,Y,Z\}$ either commute or anticommute. Moving every $Q_i$ past the corresponding $P_i$ therefore giveswhere $r$ is the number of positions containing distinct nonidentity Pauli matrices. Thus two Pauli strings always commute or anticommute. If they anticommute and a vector $|\psi ⟩$ were stabilized by both, then $PQ|\psi ⟩=|\psi ⟩$ and $QP|\psi ⟩=|\psi ⟩$, contradicting $PQ=-QP$. Their common stabilizer subspace is consequently the zero subspace $\{0\}$.

The group averageis Hermitian. In its square, every $R\in G$ occurs exactly $|G|$ times among products $PQ$, and therefore ${\Pi }_G^2={\Pi }_G$. Moreover $g{\Pi }_G={\Pi }_G$ for every $g\in G$, so its image lies in the stabilizer subspace $V_G$, while ${\Pi }_G|\psi ⟩=|\psi ⟩$ for every $|\psi ⟩\in V_G$. Thus ${\Pi }_G$ is the orthogonal projector onto $V_G$. If $g_1,\dots ,g_l$ are independent generators, expanding the product chooses each element of $G$ exactly once and gives the stabilizer-projector formula

Write the local Hamiltonian as $H={\sum }_{j=1}^m{h}_j$. Since its terms commute, their matrix exponentials factor exactly:Each factor acts on at most two qubits and can be compiled over a fixed universal quantum gate set to operator norm error at most $\epsilon /m$. The telescoping bound for products of operators then bounds the total error by the sum of the factor errors, at most $\epsilon$. Because $m$ is polynomial in $n$ and the Solovay--Kitaev theorem gives gate count polynomial in $\log (m/\epsilon )$ for each fixed-dimensional factor, this is an efficient commuting local Hamiltonian simulation. Finally, the eigenvalue equation $H|\Psi ⟩=\lambda |\Psi ⟩$ impliesso $|\Psi ⟩$ remains an eigenstate and its eigenvalue is $e^{-i\lambda t}$.

Apply exact quantum phase estimation to $U(t)$ with the supplied eigenstate $|\Psi ⟩$. Sincethe promise that the phase has an $N$-bit representation makes an $N$-qubit control register recover $\varphi$ exactly. Multiplying by $-2\pi$ modulo $2\pi$ gives $\lambda t\mathrm{mod}2\pi$. Equivalently, phase estimation may be run on $U(t{)}^{†}$, whose eigenphase is $\lambda t/(2\pi )$ modulo one.

Let $A=X\otimes X\otimes I$ and $B=Z\otimes I\otimes Z$. The two Pauli operators anticommute because their local factors anticommute at exactly one qubit. Since $A^2=B^2=I$, the mixed terms cancel andThis is a scalar, or $0$-local, Hamiltonian, so the smallest value is $\boxed{k=0}$.

The vertices $v_2,v_3,v_5$ form a triangle in a graph, so every cut of a graph leaves at least one of their three edges uncut. Hence the cut size is at most four. TakeThe crossing edges are $(1,5),(2,3),(3,5),(4,5)$, so $C=4$. The upper bound is attained and this is a maximum cut.

Since ${\hat{x}}_i=P_{1,i}$ and $I-{\hat{x}}_i=P_{0,i}$, the diagonal Hamiltonian iswith the identity on every unlisted qubit. Each computational-basis state is an eigenstate, and its eigenvalue is minus the cost of the corresponding cut. Part i supplies cost four, while the assumed bound $|{\lambda }_{\min }|\le 4$ rules out a lower energy. Thus the ground-state energy is $-4$. For the assignment $(x_1,x_2,x_3,x_4,x_5)=(0,1,0,0,1)$, one ground state isIts bitwise complement $|10110⟩$ is another ground state, as are the basis states corresponding to the other maximum cuts.

For a finite abelian group $G$ and its character group of a finite abelian group $\hat{G}$, the quantum Fourier transform over a finite abelian group isReplacing $\chi (g)$ by its complex conjugate gives the equally common inverse-transform convention.

The relation $z^{2^n}=1$ makes $z$ a root of unity, so $|z|=1$ and normalization gives $T=2^{n/2}$. Write the binary expansion $y={\sum }_{j=0}^{n-1}{2}^j{y}_j$. Then $z^y={\prod }_j(z^{2^j}{)}^{y_j}$, and henceup to the convention for ordering the binary digits. This explicit tensor product of one-qubit states proves that $|\varphi ⟩$ is a product state.

In the hidden subgroup problem, an oracle gives a function $f:G\to X$ that is constant on every left coset of an unknown subgroup $H\le G$ and takes distinct values on distinct cosets. The task is to determine $H$.

Regard bit strings as the elementary abelian group $G=({\mathbb{Z}}_2{)}^n$ under bitwise exclusive or. The promise saysThus $f$ is constant exactly on the cosets of $H$ and distinct between them. Determining the hidden subgroup determines its nonzero element $p$, so this is Simon's problem as an instance of the hidden subgroup problem.

Prepare $2^{-n/2}{\sum }_x|x⟩|0^n⟩$, query the oracle, and measure or discard the output register. For $p\ne 0$, the input register becomes the coset stateApply $H^{\otimes n}$, the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$. The two amplitudes interfere destructively unless the binary inner product satisfiesand every vector in this orthogonal subspace is sampled uniformly. Repeat until $n-1$ independent equations have been collected, then use Gaussian elimination over ${\mathbb{F}}_2$ to find their one-dimensional null space; its nonzero vector is $p$. This is Simon's algorithm. It uses $O(n)$ oracle queries with high probability and polynomial classical work. When $p=0^n$, the function is injective and the samples eventually span all of $({\mathbb{F}}_2{)}^n$, which distinguishes that case with arbitrarily high probability.