Past exam of the introduction to quantum information course of the University of Oxford / 2015 (A14687W1)

Source: released examination PDF, bundle pages 110–113.

Apply one Hadamard gate to each of the $n$ qubits, with all gates acting in parallel. This quantum circuit implements the tensor product $H^{\otimes n}$; it needs $n$ single-qubit gates and one layer. For one qubit,Taking the tensor product of these expressions multiplies the probability amplitudes and adds their exponents, givingHere the dot product is evaluated using modular arithmetic modulo two.

In particular, an initially zero quantum register becomes the uniform quantum superpositionThis is useful at the start of a quantum algorithm because a subsequent quantum oracle acts on all these components coherently. Later quantum interference can reveal a global property of the function. Measuring immediately would merely produce a uniformly random binary string; the useful resource is the preserved quantum coherence, rather than the ability to read every function value in one run.

Write $\oplus$ for bitwise exclusive or. Both quantum registers begin in $|0^n⟩$. After the first Hadamard transform their joint quantum state isThe quantum oracle $U_f$ maps each component $|x⟩|0^n⟩$ to $|x⟩|f(x)⟩$. By linearity, the required quantum state is thereforeThe different first-register computational-basis states are orthogonal, so there are $2^n$ orthogonal joint components of squared probability amplitude $2^{-n}$, even though some second-register values coincide. Thus the displayed quantum state is normalized.

An observed value $k$ must lie in the image of $f$. Choose either preimage $x_k$. The two-to-one function promise and $s\ne 0^n$ imply that its preimages are exactly $x_k$ and $x_k\oplus s$. A computational-basis measurement of the second quantum register projects the joint quantum state onto the unnormalized vectorBy the Born rule, $\mathrm{Pr}(k)=2^{1-n}$. Dividing by its square root gives the conditional first-register pure stateChoosing the other preimage merely interchanges the two summands. The result is a Simon coset state, retaining quantum coherence between the two inputs that share the measured function value. Outcomes outside the image have probability zero and hence no conditional state to normalize.

Apply the Hadamard transform to the conditional quantum state from c. Since $(x_k\oplus s)\cdot z=x_k\cdot z+s\cdot z$ modulo two, its output isIf $s\cdot z=1$, the two probability amplitudes cancel by destructive quantum interference. If $s\cdot z=0$, they add, givingThus every observed string obeys $\boxed{z\cdot s=0}$. This Simon Fourier sampling is uniform on the $(n-1)$-dimensional vector subspace $s^{\perp }$ over the two-element field. Indeed, the nonzero linear functional $z\mapsto z\cdot s$ has a kernel of dimension $n-1$ by the rank-nullity theorem. The distribution does not depend on $k$, so measuring or discarding the second quantum register gives the same statistics for the first.

Each run of Simon's algorithm uses one oracle call and returns one uniform sample from $s^{\perp }$. Collect samples as rows of a matrix $Z$ and solve $Zs=0$ over the two-element field using Gaussian elimination. Once the rows have matrix rank $n-1$, the kernel is $\{0,s\}$, so the promised nonzero vector is uniquely determined. Dependent samples, including $z=0$, must be allowed for; exactly $n-1$ runs need not suffice.

For a rough quantitative estimate, put $d=n-1$. When the existing samples span an $r$-dimensional vector subspace of $s^{\perp }$, the next sample increases the matrix rank with probability $1-2^{r-d}$. The random spanning of a binary vector space estimate givesAlternatively, $m=d+t$ samples fail to span with probability less than $2^{-t}$: failure means some nonzero linear functional on the $d$-dimensional space vanishes on every sample, and a union bound gives $(2^d-1)2^{-m}$. ConsequentlyThe Gaussian elimination requires only a polynomial amount of classical work, for example $O(n^3)$ bit operations for $O(n)$ samples. The degenerate case $n=1$ needs no calls because the promise already specifies $s=1$.

Classically, distinct inputs with equal function values reveal $s=x\oplus x^{\prime }$. Uniformly sampling distinct inputs finds such a function collision after roughly $\sqrt{2^n}$ calls, by the birthday square-root scale. For $q$ sampled inputs, the expected number of colliding pairs is $\left(\genfrac{}{}{0ex}{}{q}{2}\right)/(2^n-1)$. The usual randomized classical query complexity of Simon's problem is therefore exponential in $n$, on the scaleA straightforward exhaustive classical search instead uses $O(2^n)$ calls. The square-root collision estimate is the sharper classical comparison; the quantum advantage concerns access to the promised quantum oracle, rather than an explicit table of all function values.

For any normalized vector $|u⟩$, the Born rule assigns the probability $⟨u|\rho |u⟩$ to the corresponding rank-one orthogonal projection. This must be nonnegative for every $u$, which is exactly positive semidefiniteness. For any complete orthonormal basis $\{|j⟩\}$, the outcome probabilities must sum to one:Thus a Hermitian matrix represents a physical density matrix only ifThese conditions are also sufficient in finite dimension. The spectral theorem writes $\rho ={\sum }_j{p}_j|u_j⟩⟨u_j|$ with $p_j\ge 0$ and ${\sum }_j{p}_j=1$, describing a quantum state ensemble of pure states with valid mixing probabilities. A Hermitian matrix alone could have negative eigenvalues, hence negative measurement probabilities.

Expand the given pure state in the ordered computational basis $00,01,10,11$:The coefficients have squared magnitudes $1/3,1/6,1/3,1/6$, summing to one. The density matrix is the outer product $v{v}^{†}$, not the diagonal matrix of these four probabilities: its off-diagonal entries retain quantum coherence. ThereforeThe outer product is a Hermitian matrix and is positive semidefinite: $u^{†}\rho u=|v^{†}u{|}^2\ge 0$. Its trace is one, and ${\rho }^2=\rho$, as required for a pure state.

Let $a_{ij}$ be the coefficient of $|ij⟩$. The partial trace contracts the repeated index of the discarded qubit:For the first qubit, each diagonal entry is $1/3+1/6=1/2$ and the upper off-diagonal entry is $1/3-1/6=1/6$. For the second qubit, the diagonal entries are $2/3$ and $1/3$, while the upper off-diagonal entry is $-1/\sqrt{18}+1/\sqrt{18}=0$. Thus the two reduced density matrices, each in computational basis order $0,1$, areBoth have eigenvalues $2/3,1/3$ and trace one, so both are mixed states even though the joint quantum state is pure. Their different eigenvectors are visible in the useful rewriteAbsorbing the minus sign into one local basis vector makes this a Schmidt decomposition with nonnegative coefficients. It also checks both partial traces and exhibits the entanglement responsible for the mixed local descriptions.

For a Hermitian matrix $A$, the spectral theorem gives $A=U\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)U^{†}$, with real eigenvalues and a unitary matrix $U$. HenceThe square root here is the unique positive square root of an operator. Taking the trace, which is unchanged by unitary similarity, provesFor a density matrix, all eigenvalues are nonnegative and sum to one. Its trace norm is thereforeThe absolute values cannot be omitted for a general Hermitian matrix, since positive and negative eigenvalues can cancel in its trace but never in its trace norm.

With no access to the discarded qubit, the two preparations are exactly the reduced density matrices in c, with equal prior probabilities. Their difference isSince $\mathrm{Tr}\Delta =0$, its eigenvalues are $\pm \sqrt{2}/6$. The trace norm and trace distance are consequentlyThe Holevo–Helstrom theorem gives the optimumTo establish attainability, rather than only an upper bound, measure the Hermitian operatorwhere $X,Z$ are Pauli matrices. Since $\Delta =(\sqrt{2}/6)B$, report first qubit for the positive outcome; second qubit for the negative outcome. The corresponding orthogonal projections are $E_{\pm }=(I\pm B)/2$. Their success probability iswhich reaches the bound. Identical eigenvalues of the two density matrices do not make them indistinguishable: their eigenvectors differ, and this quantum measurement detects that difference.

Use the conventional phase gate $P_{\phi }=\mathrm{diag}(1,e^{i\phi })$ in computational basis order $0,1$. The single-qubit Hadamard gate and the successive quantum states areThe final Hadamard gate recombines the two components, givingThe leading factor in the last expression is a global phase. The Born rule therefore yieldsAt $\phi =0$ the output is certainly zero, whereas at $\phi =\pi$ it is certainly one. The phase gate changes no intermediate outcome probabilities; the final Hadamard gate converts a relative quantum phase into an observable quantum interference fringe.

Write $c=⟨e_0|e_1⟩=v{e}^{i\alpha }$. The Cauchy-Schwarz inequality gives $0\le v\le 1$ because the two environment states are normalized. Immediately after the interaction, the joint quantum state isApplying the last Hadamard gate givesSince the environment is unobserved, the Born rule uses the squared norm of the environment-valued coefficient of $|0⟩$:Thus the Hadamard interference with environment overlap formula isThe plus sign follows from the explicitly chosen phase gate and the order $⟨e_0|e_1⟩$ of the inner product. Equivalently, before the last Hadamard gate the partial trace over the environment givesThe complex environment overlap in qubit dephasing both reduces the quantum coherence by $v$ and adds a relative quantum phase $\alpha$. Orthogonal environment states have $v=0$ and give $P_0=1/2$ for every $\phi$. If $v=1$, the quantum interference fringe has full contrast and is only shifted; the qubit has not become mixed. For $v=0$, $\alpha$ is immaterial.

Moving the interaction to between the first Hadamard gate and the phase gate givesthe identical joint quantum state. Therefore the expression is unchanged. This is the commutation of computational-basis dephasing and phase gates; it uses the specified population-preserving interaction with the same environment states, rather than an arbitrary model of quantum decoherence.

Normalize the second qubit as $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. Since a Pauli X gate changes $|-⟩$ to $-|-⟩$, the Boolean quantum oracle acts asThis quantum phase kickback leaves the second qubit uncorrelated with the first. Put $b=f(0)\oplus f(1)$: $b=0$ for a constant function and $b=1$ for a balanced Boolean function. Apart from the irrelevant global phase $(-1{)}^{f(0)}$, the first qubit and environment reachThe population-preserving interaction commutes with the quantum oracle on this answer-register input, so its placement before or after the oracle, between the two Hadamard gates, gives the same result. Substitute $\phi =\pi b$ into b:The printed Deutsch algorithm uses the rule zero means constant function; one means balanced Boolean function. With that rule, the Deutsch algorithm with pure dephasing succeeds for either class withFor real nonnegative environment overlap this is $(1+v)/2$, ranging from certainty at $v=1$ to random guessing at $v=0$. For general complex overlap, a coherent shift can invert the printed answer: for example $v=1,\alpha =\pi$ makes the printed rule always wrong. If the overlap is known but the printed quantum measurement is retained, choose the better labeling of its outcomes; this givesThere is a further improvement if a known $\alpha$ can be compensated by the phase gate $P_{-\alpha }$ before the final Hadamard gate. It removes the coherent shift without reversing any actual quantum decoherence, and yieldsThis is optimal when only the first qubit is accessible, with equal prior probabilities for the two classes. Before the final Hadamard gate, their reduced density matrices areThe difference ${\rho }_0-{\rho }_1$ has eigenvalues $\pm v$, giving trace distance $v$. The Holevo–Helstrom theorem therefore bounds the success probability by $(1+v)/2$, exactly attained by the compensated procedure. A known phase shift and loss of coherence have different effects: at $v=0$ the two density matrices coincide and no measurement on the available qubit can reveal the answer.