The Exercise

A single photon in an optical network can travel in any of $d$ modes, and its state is a superposition of the $d$ possibilities. Two kinds of element act on it: a beamsplitter mixes the amplitudes of two modes, and a phase shifter multiplies the amplitude of one mode by a phase. Every unitary of the $d$ modes can be assembled from these two elements.^✦ Two qubits fit into four modes, one mode for each of their basis states, and in that encoding the circuit of Deutsch’s algorithm and one iteration of Grover’s search over four items are both optical networks. The construction does not scale: $n$ qubits need $2^n$ modes, and some unitaries of those modes need at least $2^n - 1$ elements.^✦

Here the system is a quantum system with $d$ levels, the qudit, and an optical network is a finite product of beamsplitters and phase shifters acting on it.

A Quantum System

A quantum system $S$ is given by its state space, a finite dimensional complex Hilbert space.^✦ Two systems $S$ and $T$ form the composite system $S \otimes T$, whose state space is the tensor product of theirs.^✦ A pure state $|\psi\rangle$ of $S$ is a unit vector in 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 = 1$, and the identity evolution of $S$ is the unitary with operator $1$. For unitaries $U$ and $V$ of $S$, the unitary $U$ after $V$ is the product $UV$, in which $V$ acts first.^✦ Unitaries $U$ of $S$ and $U'$ of $T$ give the product unitary $U \otimes U'$ of $S \otimes T$, whose operator is the tensor product of the two.^✦

An identification $J$ of a system $S$ with a system $T$ is a linear isometric bijection from the state space of $S$ onto that of $T$; its inverse $J^{-1}$ identifies $T$ with $S$. Along $J$, a unitary $U$ of $S$ is relabelled as the unitary $J U J^{-1}$ of $T$.^✦

The qudit with $d$ levels is the system with state space $\mathbb{C}^d$.^✦ The computational basis of the qudit with $d$ levels is the orthonormal basis of standard unit vectors $|0\rangle, \dots, |d-1\rangle$, and each basis state $|i\rangle$ is a pure state of the qudit. In the optical setting the levels are modes, and $|i\rangle$ is the photon in mode $i$. The qubit is the qudit with two levels, and the qudit with $2^n$ levels is a register of $n$ qubits.

Beamsplitters and Phase Shifters

The gate of a unitary $d \times d$ matrix $M$ is the unitary of the qudit with $d$ levels that acts on state vectors as $M$ does in the computational basis.^✦

For modes $p$ and $q$, the two level embedding of a complex $2 \times 2$ matrix $G$ is the $d \times d$ matrix that acts as $G$ on $|p\rangle$ and $|q\rangle$, taken in that order as the two basis states of a qubit, and as the identity on every other mode.^✦

The Pauli matrices are $X = \left(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right)$, $Y = \left(\begin{smallmatrix} 0 & -i \\ i & 0 \end{smallmatrix}\right)$ and $Z = \left(\begin{smallmatrix} 1 & 0 \\ 0 & -1 \end{smallmatrix}\right)$. The Pauli vector is $\vec\sigma = (X, Y, Z)$. A real vector $\vec n = (n_x, n_y, n_z)$ in three dimensions gives the matrix $\vec n \cdot \vec\sigma = n_x X + n_y Y + n_z Z$, and a unit vector $\hat n$ gives the rotation $R_{\hat n}(\theta) = \exp(-i\theta\, \hat n \cdot \vec\sigma / 2)$ about $\hat n$ by an angle $\theta$. About the axis $\hat y = (0, 1, 0)$ it is $R_{\hat y}(\theta) = e^{-i\theta Y/2}$.^✦

For modes $p$ and $q$ and an angle $\theta$, the beamsplitter matrix on $p$ and $q$ is the two level embedding of $R_{\hat y}(\theta)$.^✦ The beamsplitter gate $B_{pq}(\theta)$ on distinct modes $p$ and $q$ is the gate of the beamsplitter matrix on $p$ and $q$, the unitary of the qudit with $d$ levels that acts on the basis states as follows: $$\begin{aligned} B_{pq}(\theta)\,|p\rangle &= \cos\tfrac{\theta}{2}\,|p\rangle + \sin\tfrac{\theta}{2}\,|q\rangle, \qquad B_{pq}(\theta)\,|q\rangle = -\sin\tfrac{\theta}{2}\,|p\rangle + \cos\tfrac{\theta}{2}\,|q\rangle,\\ B_{pq}(\theta)\,|i\rangle &= |i\rangle \quad (i \neq p, q). \end{aligned}$$(1)^✦

The phase shifter matrix on a mode $p$ with phase $\varphi$ is the diagonal matrix with entry $e^{i\varphi}$ at $p$ and $1$ at every other mode, and the phase shifter gate $P_p(\varphi)$ is its gate: $$P_p(\varphi)\,|p\rangle = e^{i\varphi}\,|p\rangle, \qquad P_p(\varphi)\,|i\rangle = |i\rangle \quad (i \neq p).$$(2)

A linear optical gate on $d$ modes is a unitary $V$ of the qudit with $d$ levels that is a beamsplitter or a phase shifter: $$V = B_{pq}(\theta) \text{ for modes } p \neq q \text{ and an angle } \theta, \quad \text{or} \quad V = P_p(\varphi) \text{ for a mode } p \text{ and a phase } \varphi.$$(3)^✦

Two Qubits in Four Modes

For qudits with $a$ and $b$ levels, the product basis of their composite consists of the vectors $|i\rangle \otimes |k\rangle$ with $0 \le i < a$ and $0 \le k < b$. The factoring of the qudit with $ab$ levels is the identification of it with that composite which sends $|bi + k\rangle$ to $|i\rangle \otimes |k\rangle$. The unary encoding $\mathcal{E}$ is the inverse of the factoring for $a = b = 2$, an identification of two qubits with the qudit of four levels: $$\mathcal{E}\,(|i\rangle \otimes |k\rangle) = |2i + k\rangle, \qquad i, k \in \{0, 1\}.$$(4)^✦

The Hadamard $H$ is the unitary of the qubit with matrix $\tfrac{1}{\sqrt 2}\left(\begin{smallmatrix} 1 & 1 \\ 1 & -1 \end{smallmatrix}\right)$, and $H \otimes 1$ is the gate on the first of two qubits, with the identity on the second. For a unitary $U_f$ of two qubits, standing in the place of the oracle of Deutsch’s algorithm, the Deutsch circuit $D(U_f)$ is the unitary of two qubits given below. Along the unary encoding, the Deutsch circuit $D(U_f)$ is relabelled as the unitary $\tilde D(U_f)$ of the qudit with four levels: $$D(U_f) = (H \otimes 1)\, U_f\, (H \otimes H), \qquad \tilde D(U_f) = \mathcal{E}\, D(U_f)\, \mathcal{E}^{-1}.$$(5)

The reflection about a pure state $|\psi\rangle$ of a system is the unitary $1 - 2|\psi\rangle\langle\psi|$.^✦

The uniform superposition of the qudit with $d \ge 1$ levels is the pure state $|s\rangle = \frac{1}{\sqrt d}\sum_{k=0}^{d-1} |k\rangle$.

Search over four items marks the item $x \in \{0, 1, 2, 3\}$ by the mode $|x\rangle$. The search oracle $O_x$ is the reflection about $|x\rangle$, $$O_x = 1 - 2\,|x\rangle\langle x|,$$(6) and the inversion about the mean $W$ is the reflection about the uniform superposition of the four modes, $$W = 1 - 2\,|s\rangle\langle s|, \qquad |s\rangle = \tfrac{1}{2}\left(|0\rangle + |1\rangle + |2\rangle + |3\rangle\right).$$(7) One Grover iteration $G_x$ for the marked mode $x$ is the search oracle $O_x$ followed by the inversion about the mean $W$: $$G_x = W\, O_x.$$(8)

The Claim

Parts (b) and (c) are instances of part (a) with $d = 4$.

What Is Checked

The four claims are stated over the linear optical gates (3), the beamsplitters (1) and phase shifters (2) on $d$ modes, and, on four modes, over the Deutsch circuit in the unary encoding (5) and the Grover iteration (8).

The library proves that the beamsplitter matrix on two distinct modes is unitary for every angle $\theta$, and that the phase shifter matrix on a mode is unitary for every phase $\varphi$. The product $UV$ of two unitaries is a unitary, and so are the relabelling $J U J^{-1}$ of a unitary along an identification and the product unitary $U \otimes U'$. The reflection $1 - 2|\psi\rangle\langle\psi|$ about a pure state is a unitary, the Hadamard matrix is unitary, so that $H$ is a unitary of the qubit, and the uniform superposition has unit norm, hence is a pure state.