The Exercise

A quantum system $S$ carries a marked pure state $|x\rangle$, and an oracle recognises it by flipping an extra qubit when the system is in $|x\rangle$. The circuit of Figure 6.4 runs the system together with that qubit, prepared in $|0\rangle$, through the oracle, a phase shift by $-\Delta t$ on the qubit, and the oracle once more. The exercise is to verify that this circuit evolves the system for a time $\Delta t$ under the Hamiltonian $|x\rangle\langle x|$, taking $|\varphi\rangle$ to $e^{-i|x\rangle\langle x|\Delta t}|\varphi\rangle$, and hands the qubit back in $|0\rangle$.^✦ The circuit of Figure 6.5 places the first one between $W^\dagger$ and $W$ on the system, for a unitary $W$, and is to give the evolution $e^{-i|\psi\rangle\langle\psi|\Delta t}$ under the projector onto $|\psi\rangle = W|x\rangle$.

The System and the Qubit

A quantum system $S$ is a physical object whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $|\varphi\rangle$ of $S$ is a unit vector in the state space of $S$.^✦ The qubit $Q$ is the two level system whose state space is $\mathbb{C}^2$, and its basis states $|0\rangle$ and $|1\rangle$ are the standard basis vectors of $\mathbb{C}^2$.

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.^✦ For pure states $|\varphi\rangle$ of $S$ and $|\chi\rangle$ of $T$, the product $|\varphi\rangle \otimes |\chi\rangle$ is the pure state of $S \otimes T$ whose vector is the tensor product of the two vectors.^✦

Unitaries and Hamiltonians

A unitary $U$ of $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$; it carries a pure state $|\varphi\rangle$ of $S$ to the pure state $U|\varphi\rangle$. The adjoint $U^\dagger$ of a unitary $U$ of $S$ is the unitary of $S$ whose operator is the Hilbert space adjoint of that of $U$.^✦ For two unitaries $U$ and $V$ of $S$, the unitary $UV$, $U$ after $V$, applies first $V$ and then $U$.^✦

For 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 the two operators.^✦ The identity evolution $1$ of a system is the unitary whose operator is the identity.^✦ A gate is a unitary of a system. On $S \otimes Q$, a gate on the system alone is $U \otimes 1$, and a gate on the qubit alone is $1 \otimes V$, with the identity evolution on the other factor.

An observable $A$ of $S$ is a self adjoint operator on the state space of $S$, $A^\dagger = A$.^✦ For a pure state $|x\rangle$ of $S$, the projector $|x\rangle\langle x|$, which sends $|\varphi\rangle$ to $\langle x|\varphi\rangle\,|x\rangle$, is self adjoint and so an observable of $S$; it is the Hamiltonian of the exercise.^✦

The propagator $U(t_1, t_2)$ of an observable $H$ of $S$, with Planck’s constant $\hbar$, from time $t_1$ to time $t_2$ is the unitary of $S$ $$U(t_1, t_2) = \exp\bigl[-iH(t_2 - t_1)/\hbar\bigr],$$(1) which carries the state at $t_1$ to the state at $t_2$ under the Schrödinger equation. With $\hbar = 1$, $t_1 = 0$, $t_2 = \Delta t$ and $H = |x\rangle\langle x|$, the propagator (1) is the operation $e^{-i|x\rangle\langle x|\Delta t}$ of the exercise.

The Gates and the Circuits

The Pauli $X$, the quantum NOT gate, is the unitary of the qubit with matrix $$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$(2)^✦ in the basis $|0\rangle, |1\rangle$. The phase gate $P(\alpha)$ with angle $\alpha$ is the unitary of the qubit that is diagonal in the basis $|0\rangle, |1\rangle$, with the matrix $$P(\alpha) = \mathrm{diag}\bigl(1, e^{i\alpha}\bigr),$$(3)^✦

The marking oracle $O$ for a pure state $|x\rangle$ of $S$ is the unitary of $S \otimes Q$ with operator $$O = |x\rangle\langle x| \otimes X + \bigl(1 - |x\rangle\langle x|\bigr) \otimes 1 .$$(4)^✦

For a real time step $\Delta t$, the circuit of Figure 6.4 is the unitary of $S \otimes Q$ $$C_x(\Delta t) = O\,\bigl(1 \otimes P(-\Delta t)\bigr)\,O .$$(5)^✦ The circuit of Figure 6.5 takes in addition a unitary $W$ of $S$ and conjugates the first circuit by $W$ on the system: $$C_{W,x}(\Delta t) = (W \otimes 1)\, C_x(\Delta t)\, (W^\dagger \otimes 1) .$$(6)^✦

The Claim

What Is Checked

The claim is stated over the circuits (5) and (6) acting on the product state $|\varphi\rangle \otimes |0\rangle$, and over the propagator (1), with $\hbar = 1$, of the projector onto $|x\rangle$ or onto $W|x\rangle$.

About these constructions the library proves that the oracle (4) is unitary, and that the phase gate is unitary because its diagonal entries have unit modulus. Tensor products and composites of unitaries are unitary, so each circuit is a unitary of $S \otimes Q$, and $|\varphi\rangle \otimes |0\rangle$ is a pure state because the norm of a product vector is the product of the norms.