The Exercise

A function $f$ from one bit to one bit is constant when $f(0) = f(1)$ and balanced when $f(0) \neq f(1)$. There are four of them: the constants $0$ and $1$, the identity $x \mapsto x$ and the negation $x \mapsto x \oplus 1$, where $\oplus$ is the sum modulo $2$. Given $f$ only as a black box acting on two qubits, Deutsch’s algorithm tells the two kinds apart with a single use of the box. The exercise is to build this circuit from optical elements acting on single photons.

The library gives a black box, an oracle, for each of the four functions, and writes the two balanced ones as a controlled phase shift of angle $\pi$, the optical Kerr gate, between Hadamard gates. It realises the Hadamard gate on one photon in two modes by a beamsplitter and a mirror, and states for each oracle which bit the measurement of the first qubit returns.

A Quantum System

A quantum system $S$ is given by its state space, 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 two level system with state space $\mathbb{C}^2$, and its basis states $|0\rangle$ and $|1\rangle$ are the two standard basis vectors.

A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$, and pure states $|\psi\rangle$ of $S$ and $|\varphi\rangle$ of $T$ give the product state $|\psi\rangle \otimes |\varphi\rangle$ of $S \otimes T$. A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$.^✦ A pure state $|\psi\rangle$ gives the state $|\psi\rangle\langle\psi|$, the projector onto its vector.^✦

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 $|\psi\rangle$ to the pure state $U|\psi\rangle$. For two unitaries $U$ and $V$ of $S$, the product $UV$ is the unitary that applies $V$ first and then $U$, and the identity evolution $I$ is the unitary whose operator is the identity. Unitaries $U$ of $S$ and $V$ of $T$ give the product unitary $U \otimes V$ of $S \otimes T$; with the identity on the other factor, $U \otimes I$ is $U$ on the first factor and $I \otimes V$ is $V$ on the last. On two copies of one system, the SWAP is the unitary that exchanges the factors, $\mathrm{SWAP}\,(|\alpha\rangle \otimes |\beta\rangle) = |\beta\rangle \otimes |\alpha\rangle$.^✦

Gates

The Hadamard gate $H$ and the Pauli $X$, the quantum NOT, are the unitaries of the qubit whose matrices in the basis $|0\rangle, |1\rangle$ are $$H = \frac{1}{\sqrt 2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.$$(1) For a real angle $\alpha$, the phase shift $P(\alpha)$ is the unitary of the qubit that leaves $|0\rangle$ alone and multiplies $|1\rangle$ by $e^{i\alpha}$.^✦

For a unitary $U$ of a system $S$, the controlled gate $C(U)$ is the unitary of the composite system of a control qubit and a target $S$ given by $$C(U) = |0\rangle\langle 0| \otimes I + |1\rangle\langle 1| \otimes U.$$(2)^✦ The controlled NOT, or CNOT, is $C(X)$, and the controlled phase shift with angle $\varphi$ is $C(P(\varphi))$.

For angles $\varphi_a$, $\varphi_b$ and $\Delta$, the optical Kerr gate is the unitary of two qubits that applies the controlled phase shift $C(P(\Delta))$ and then a phase shift on each qubit: $$K(\varphi_a, \varphi_b, \Delta) = \bigl(P(\varphi_b) \otimes I\bigr) \bigl(I \otimes P(\varphi_a)\bigr)\, C\bigl(P(\Delta)\bigr).$$(3)^✦

Single Photons

A single photon shared between two optical modes is described on the composite system of two qubits, one for each mode, $|1\rangle$ standing for a photon in the mode and $|0\rangle$ for none. The dual rail logical zero $|0_L\rangle = |01\rangle$ is a photon in the second mode, and the logical one $|1_L\rangle = |10\rangle$ a photon in the first. For complex amplitudes $c_0$ and $c_1$ with $|c_0|^2 + |c_1|^2 = 1$, the dual rail state $c_0|0_L\rangle + c_1|1_L\rangle$ is the pure state of the two modes with these amplitudes, the general state of one photon in two modes.^✦

The beamsplitter with mixing angle $\theta$ is the unitary of the two modes with operator $$B(\theta) = 1 + (\cos\theta - 1)\,P + \sin\theta\, G,$$(4) where $P = |01\rangle\langle 01| + |10\rangle\langle 10|$ is the projector onto the dual rail plane, spanned by $|0_L\rangle$ and $|1_L\rangle$, and $G = |10\rangle\langle 01| - |01\rangle\langle 10|$ is the generator of rotations in that plane. Followed by a mirror that exchanges the two modes, the SWAP, the beamsplitter at $\theta = \pi/4$ gives the unitary $\mathrm{SWAP}\,B(\pi/4)$.^✦

The Oracles and the Circuit

For a function $f$ from one bit to one bit, a unitary $U_f$ of two qubits is an oracle for $f$ when, for all bits $x$ and $y$, $$U_f\bigl(|x\rangle \otimes |y\rangle\bigr) = |x\rangle \otimes |y \oplus f(x)\rangle.$$(5)^✦ The library defines one unitary of two qubits for each function on one bit: $$U_0 = I,$$(6) $$U_1 = I \otimes X,$$(7) $$U_{\mathrm{id}} = \mathrm{CNOT},$$(8) $$U_{\neg} = (X \otimes I)\, \mathrm{CNOT}\, (X \otimes I).$$(9)

The Deutsch circuit for a unitary $U$ of two qubits applies a Hadamard gate to each qubit, then $U$, then a Hadamard gate to the first qubit alone: $$D(U) = (H \otimes I)\, U\, (H \otimes H).$$(10)^✦

Measuring the Control Qubit

A measurement on a system $S$ with a finite set of outcomes is a family of operators $M_i$ on the state space of $S$, one for each outcome $i$, with $\sum_i M_i^\dagger M_i = 1$, the completeness relation.^✦ Performed on a state $\rho$ of $S$, it gives the outcome $i$ with the probability $$p(i) = \operatorname{Tr}\bigl(M_i \rho M_i^\dagger\bigr) = \operatorname{Tr}(E_i \rho)$$(11) of the Born rule, where the positive operators $E_i = M_i^\dagger M_i$ make up the positive operator valued measure of the measurement.

The projective measurement in an orthonormal basis $\{|b_i\rangle\}$ is the measurement whose operator for the outcome $i$ is the projector $|b_i\rangle\langle b_i|$.^✦ A measurement with operators $M_i$ on $S$ gives the measurement on the first factor of $S \otimes T$, with the same outcomes and the operators $M_i \otimes I$.^✦ The measurement of the control qubit on the composite system of a qubit and a system $S$ is the projective measurement of the qubit in the basis $|0\rangle, |1\rangle$ performed on the first factor: its outcomes are $0$ and $1$, its operators $|0\rangle\langle 0| \otimes I$ and $|1\rangle\langle 1| \otimes I$.^✦

The Claim

What Is Checked

The claim is stated over the Deutsch circuit (10) with the four oracles (6) to (9), the oracle condition (5), and the Born probability (11) of the measurement of the control qubit; on the optical side, over the Kerr gate (3) between Hadamard gates and over the beamsplitter (4) with its mirror acting on the dual rail states.

About these constructions the library proves that the beamsplitter operator $B(\theta)$ is unitary for every angle $\theta$ and that $C(U)$ is unitary for every unitary $U$. It proves that the dual rail superposition $c_0|0_L\rangle + c_1|1_L\rangle$ is a unit vector whenever $|c_0|^2 + |c_1|^2 = 1$, and that the amplitudes $\tfrac{\sqrt 2}{2}(c_0 + c_1)$ and $\tfrac{\sqrt 2}{2}(c_0 - c_1)$ then satisfy the same condition. A measurement on the first factor, the measurement of the control qubit among them, again satisfies the completeness relation.