The Exercise

Grover’s algorithm on two qubits looks for one marked item among four, $x = 0, 1, 2, 3$, written in binary as the computational basis states $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$, the first qubit carrying the higher bit. The oracle for the marked item $x_0$ is the unitary that multiplies $|x_0\rangle$ by $-1$ and leaves the other three basis states unchanged; for $x_0 = 3$ it is the controlled $Z$ gate.

In nuclear magnetic resonance (NMR) the two qubits are two coupled nuclear spins, acted on by rotations of each spin and by free evolution under their coupling, of strength $J$. The exercise builds the oracles for $x_0 = 0$, $1$ and $2$ from these: a rotation by $-\pi/2$ about $z$ of each spin, evolution under the coupling for a time $t$ with $Jt = \pi/4$, and, before and after, a rotation by $\pi$ about $x$ of each spin whose bit in $x_0$ is $0$. Each sequence equals its oracle up to a global phase, and so acts on every state of the two spins as the oracle does. The library states both, for each of the three oracles.

Systems and Their Evolution

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ The composite system $S \otimes T$ of two systems $S$ and $T$ is the system whose state space is the tensor product of their state spaces.^✦ The qubit is the system whose state space is $\mathbb{C}^2$ itself, and the two spins form the composite system of two qubits.

A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$.^✦ The computational basis states $|0\rangle$ and $|1\rangle$ of the qubit are the pure states given by the two standard basis vectors of $\mathbb{C}^2$.^✦ A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$.^✦

A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = I$, where $I$ is the identity operator.^✦

Under $U$ a state $\rho$ of $S$ evolves as $$\rho \mapsto U \rho U^\dagger .$$(1)^✦

For two unitaries $U$ and $V$ of $S$, $U$ after $V$ is the unitary $UV$ of $S$, first $V$ and then $U$.^✦

Given a unitary $U$ of $S$ and a unitary $V$ of $T$, the product unitary $U \otimes V$ is the unitary of $S \otimes T$ whose operator is the tensor product of theirs.^✦ The gate $U \otimes I$ is the unitary of $S \otimes T$ that applies $U$ to the first factor, and the gate $I \otimes V$ is the unitary of $S \otimes T$ that applies $V$ to the second factor.

An observable $A$ of $S$ is a self adjoint operator on the state space of $S$.^✦ The tensor product $A \otimes B$ of an observable $A$ of $S$ and an observable $B$ of $T$ is the observable of $S \otimes T$ whose operator is the tensor product of theirs.^✦

The propagator of an observable $H$ of $S$, taken as the Hamiltonian, from time $t_1$ to time $t_2$ and with Planck’s constant $\hbar$, is the unitary of $S$ $$U(t_1, t_2) = \exp\left[-\frac{i H (t_2 - t_1)}{\hbar}\right] .$$(2)^✦

Pauli Matrices and Rotations

The Pauli matrices are the $2 \times 2$ complex matrices $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \qquad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(3) For a real vector $\vec{n} = (n_x, n_y, n_z)$ in three dimensions, the matrix $\vec{n} \cdot \vec{\sigma}$ is $n_x X + n_y Y + n_z Z$, and the rotation about $\vec{n}$ by a real angle $\theta$ is the matrix $$R_{\vec{n}}(\theta) = \exp\left(-\frac{i \theta}{2}\, \vec{n} \cdot \vec{\sigma}\right),$$(4) written $R_{\hat{n}}(\theta)$ when the axis is a unit vector $\hat{n}$. The rotations about the $\hat{x}$ axis $(1, 0, 0)$ and the $\hat{z}$ axis $(0, 0, 1)$ are $R_x(\theta) = e^{-i\theta X/2}$ and $R_z(\theta) = e^{-i\theta Z/2}$.

The gates $X$, the quantum NOT, $Z$, the phase flip, and $R_x(\theta)$ and $R_z(\theta)$ are the unitaries of the qubit whose matrices in the computational basis are the ones above. The Pauli observable $\vec{n} \cdot \vec{\sigma}$ is the observable of the qubit with matrix $\vec{n} \cdot \vec{\sigma}$, and the observable $Z$ is the one for $\hat{n} = \hat{z}$.

Gates on Two Qubits

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of the composite of a control qubit with the target $S$ given by $$C(U) = |0\rangle\langle 0| \otimes I + |1\rangle\langle 1| \otimes U .$$(5)^✦ The controlled $Z$ gate is $CZ = C(Z)$ on two qubits, the first the control; its matrix in the computational basis is $\mathrm{diag}(1, 1, 1, -1)$.^✦

For a real angle $\alpha$, the global phase gate $e^{i\alpha}$ on a system $S$ is the unitary $e^{i\alpha} I$.^✦

Oracles and Pulse Sequences

The Grover oracles for $x_0 = 0$, $1$ and $2$ are $CZ$ conjugated by $X$ on the qubits whose bit in $x_0$ is $0$, $$\begin{aligned} O_0 &= P\, CZ\, P, \qquad P = (X \otimes I)(I \otimes X), \\ O_1 &= (X \otimes I)\, CZ\, (X \otimes I), \\ O_2 &= (I \otimes X)\, CZ\, (I \otimes X), \end{aligned}$$(6)

The coupling Hamiltonian of the two spins with coupling constant $J$ is the observable $H = J Z_1 Z_2$ of two qubits, the real number $J$ times the tensor product $Z_1 Z_2 = Z \otimes Z$ of the observable $Z$ with itself.^✦

For a coupling constant $J$ and a time $t$, the controlled $Z$ pulse sequence is the unitary of two qubits $$S(J, t) = e^{-i J t Z_1 Z_2}\, \bigl(R_z(-\tfrac{\pi}{2}) \otimes I\bigr)\bigl(I \otimes R_z(-\tfrac{\pi}{2})\bigr),$$(7)^✦ whose first factor is the propagator (2) of $H$ from time $0$ to time $t$, in units with $\hbar = 1$.

For a coupling constant $J$ and a time $t$, the pulse sequences $N_0(J, t)$, $N_1(J, t)$ and $N_2(J, t)$ for the three oracles are the unitaries of two qubits that put rotations by $\pi$ about $x$ around $S(J, t)$: $$\begin{aligned} N_0(J, t) &= Q\, S(J, t)\, Q, \qquad Q = \bigl(R_x(\pi) \otimes I\bigr)\bigl(I \otimes R_x(\pi)\bigr), \\ N_1(J, t) &= \bigl(R_x(\pi) \otimes I\bigr)\, S(J, t)\, \bigl(R_x(\pi) \otimes I\bigr), \\ N_2(J, t) &= \bigl(I \otimes R_x(\pi)\bigr)\, S(J, t)\, \bigl(I \otimes R_x(\pi)\bigr). \end{aligned}$$(8)

The Claim

What Is Checked

The claim is stated over two families of unitaries of two qubits: the pulse sequences $N_{x_0}(J, t)$ of (8) and the oracles $O_{x_0}$ of (6).

The library proves that $C(U)$ is unitary for every unitary $U$ of a system, which makes $CZ$, and with it each oracle, a unitary of the two qubits.^✦ A product and a tensor product of unitaries are unitary, and $U \rho U^\dagger$ is again a state, so that both sides of (12), (13) and (14) are states of the two qubits.