Past exam of the computer science course of the University of Oxford / 2019 / Quantum information / 3

For normalized vector representatives in the same Hilbert space, the vector-norm convention is $\Vert |\psi ⟩-|\varphi ⟩{\Vert }_2\le \epsilon$. Since physical pure states identify global phases, a phase-insensitive version isThe equality follows by choosing the phase to make the overlap real and nonnegative. This states an explicit pure-state norm distance convention; fidelity-based or trace-distance conventions use different numerical error parameters. We use the phase-insensitive convention for the universality claim below.

Under fixed phase representatives, two unitary operators on the same space are $\epsilon$-close when $\Vert U-V{\Vert }_{\mathrm{op}}\le \epsilon$, where the operator norm isThus every input vector is approximated uniformly, not merely one selected input. Under the phase-insensitive convention, replace this bound by ${\min }_{\theta }\Vert U-e^{i\theta }V{\Vert }_{\mathrm{op}}\le \epsilon$. The minimization uses one phase for the whole operator, not a separately chosen phase inside the supremum for each input. This is operator-norm distance between unitary gates with the stated global-phase identification.

A finite universal quantum gate set can approximate every unitary on any fixed finite number of qubits to any prescribed positive accuracy, using a finite circuit of its gates on allowed wires. Explicitly, for every target $U$ and $\epsilon >0$ there is such a circuit $C$ withThe global-phase convention is the one just specified. Universality means arbitrary approximation, not exact representation of an uncountable family by finitely described circuits. Products of approximate gates can be controlled using the quantum circuit gate-error telescoping bound.

Both the controlled-NOT gate and Pauli X gate permute computational basis vectors. Any finite composition remains a permutation matrix, and so sends $|0\cdots 0⟩$ to another computational basis vector. It cannot prepare a superposition such as $|+⟩\otimes |0\cdots 0⟩$.

This also rules out approximation: the squared overlap of that target with any computational basis vector is at most $1/2$, so even after optimizing global phase the pure-state norm distance is at least $\sqrt{2-\sqrt{2}}>0$. Hence $\{CNOT,X\}$ is not universal. Basis permutations can create entanglement on some superposed inputs, but this gate set cannot create the required superposition from the specified basis input.

Squaring the diagonal gate givesThus the T gate is available up to a global phase. Reading the supplied W columns in order $00,01,10,11$, it sends $|01⟩$ to $|11⟩$, $|11⟩$ to $|01⟩$, and fixes the other two vectors: it is CNOT with the second wire controlling the first. Conjugating both wires by the Hadamard gate reverses that orientation:For instance, write $W=I\otimes |0⟩⟨0|+X\otimes |1⟩⟨1|$. Conjugation uses $HXH=Z$ and $H|0⟩=|+⟩$, $H|1⟩=|-⟩$, yielding $I\otimes |+⟩⟨+|+Z\otimes |-⟩⟨-|$. Expanding the first-wire Z eigenspaces gives $|0⟩⟨0|\otimes I+|1⟩⟨1|\otimes X$, as required.

We have H directly and finite constructions of CNOT and T up to physically irrelevant global phase. By universality transfer by exact gate synthesis, the assumed universality of $\{CNOT,H,T\}$ proves that $\{V,H,W\}$ is universal under the phase-insensitive convention. There is no assertion of arbitrary strict operator-norm phases: on a fixed register these generators have only a finite set of possible determinants, which would obstruct density in the entire unitary group if global phase were treated as an observable target.

By the spectral theorem, the nonscalar unitary V has orthonormal eigenvectors $|v_0⟩,|v_1⟩$ with distinct eigenvalues ${\lambda }_0\ne {\lambda }_1$. Choose $|b⟩=(|v_0⟩+|v_1⟩)/\sqrt{2}$. Then $V|b⟩=({\lambda }_0|v_0⟩+{\lambda }_1|v_1⟩)/\sqrt{2}$ is not proportional to $|b⟩$.

On the product input $|+⟩\otimes |b⟩$, the controlled unitary gate producesIts two conditional target vectors are linearly independent, so the conditional-vector product-state criterion proves that the output is entangled. Equivalently, in the control computational basis and target eigenbasis its coefficient matrix is $\frac{1}{2}\left(\begin{array}{cc}1& 1\\ {\lambda }_0& {\lambda }_1\end{array}\right)$, whose determinant is $({\lambda }_1-{\lambda }_0)/4\ne 0$. Thus U is an entangling gate. The excluded scalar case would only apply a phase gate to the control and could not entangle the factors; this is the controlled-unitary entangling criterion.

Let $N_0,N_1$ be the two output counts. Choose a known preparation unitary F with $F|0⟩=N^{-1/2}{\sum }_x|x⟩=:|s⟩$. The Deutsch-Jozsa algorithm applies the supplied phase oracle $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ and then $F^{†}$, declaring constant exactly for outcome 0. Its amplitude on that outcome isThis is the Deutsch-Jozsa test with an arbitrary uniform-state unitary. For $N=2^m$, the usual preparation is $F=H^{\otimes m}$; the argument itself needs only a uniform preparation on the stated N-dimensional space.

For an actually constant-up-to-k function, the two counts are $k$ and $N-k$, so the outcome-0 probability is $(1-2k/N{)}^2$. The error is returning the other label. ThereforeHere the possible count k is nonnegative, and the supplied bound implies $0\le k/N\le 1/8$. The error is consequently at most $7/16$; at $k=0$ it vanishes. This is the error conditional on the stated constant-up-to-k case, not an average over unspecified prior probabilities. For comparison, the printed balanced-up-to-k definition has count difference $\pm k$, so its outcome-0 probability would be $(k/N{)}^2$, not the expression for the constant-up-to-k case. No change to that promise definition is made.

One Grover iteration returns a marked label with certainty. Prepare $|s⟩=N^{-1/2}{\sum }_x|x⟩$; apply the supplied phase oracle to negate amplitudes on the $N/4$ marked inputs; apply the Grover diffusion operator $D=2|s⟩⟨s|-I$; and measure in the computational basis. If F prepares $|s⟩$ from $|0⟩$, the reflection is $D=F(2|0⟩⟨0|-I)F^{†}$, requiring no further oracle query.

After the oracle the amplitudes are $1/\sqrt{N}$ on the $3N/4$ unmarked labels and $-1/\sqrt{N}$ on the marked labels. Their average isThe reflection performs inversion about the mean, $a_x\mapsto 2\mu -a_x$. It therefore sends every unmarked amplitude to zero and every marked amplitude to $2/\sqrt{N}$. The resulting normalized state isEach marked label has Born rule probability $4/N$, every unmarked label has probability zero, and the marked probabilities sum to $(N/4)(4/N)=1$. This is one-step exact Grover search with a quarter of the inputs marked, using one reduced-oracle query. The positive integer N must be divisible by four; a qubit implementation may take $N=2^m$, but the stated reflection proof does not assume that register convention.

Use the Bernstein-Vazirani algorithm: initialize n qubits in $|0^n⟩$, apply $H^{\otimes n}$, query the supplied phase oracle once, apply $H^{\otimes n}$ again, and measure all n computational bits. Immediately after the query the state iswhere the dot product in the exponent is taken modulo two. The Walsh-Hadamard transform gives amplitudeEvery factor is one if $y_j=a_j$ and zero otherwise. Thus the final state is exactly $|a⟩$, and the measurement outputs a with certainty after one oracle query. This is the character cancellation behind Bernstein-Vazirani phase kickback; because access here is already to the reduced phase oracle, no extra target ancilla or conversion from a bit-flip oracle is required.