The Exercise

A search problem runs over $N$ items, labelled $0, \ldots, N-1$, and a set $T$ of $M \geq 1$ of them are solutions. In the continuous time version the items are the computational basis states of a system with $N$ levels. The system starts in the uniform superposition of all of them and evolves under a Hamiltonian for a time $t$; then it is measured in the computational basis. The task is to find a Hamiltonian, which may depend on $T$, and a time after which the measurement returns a solution.

A Qudit and Its Basis

A quantum system $S$ is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $|\psi\rangle$ of $S$ is a unit vector in the state space of $S$, $\lVert \psi \rVert = 1$.^✦

The qudit with $N$ levels is the quantum system whose state space is $\mathbb{C}^N$ with its standard inner product.^✦ The computational basis $\{|i\rangle\}$ of the qudit with $N$ levels, for $i = 0, \ldots, N-1$, is the orthonormal basis of standard unit vectors, $|i\rangle$ having a one in position $i$ and zeros elsewhere, and the computational basis state $|i\rangle$ is the pure state of the qudit with that vector.

For $N \geq 1$ the uniform superposition $|s\rangle$ is the pure state of the qudit in which every level enters with amplitude $1/\sqrt{N}$.^✦ For a nonempty set $T$ of $M$ levels the superposition over the solutions $|\beta\rangle$ is the pure state in which each level of $T$ enters with amplitude $1/\sqrt{M}$ and no other level enters: $$|s\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} |k\rangle, \qquad |\beta\rangle = \frac{1}{\sqrt{M}} \sum_{x \in T} |x\rangle.$$(1)^✦

The Search Hamiltonian

An observable $A$ on $S$ is a self adjoint operator on the state space of $S$, $A^\dagger = A$.^✦ The projector Hamiltonian of a pure state $|\psi\rangle$ of $S$ is the observable $|\psi\rangle\langle\psi|$, the projector onto $|\psi\rangle$.^✦ The search Hamiltonian of pure states $|\varphi\rangle$ and $|\psi\rangle$ of $S$ is the observable $|\varphi\rangle\langle\varphi| + |\psi\rangle\langle\psi|$, the sum of their projector Hamiltonians. For the solutions $T$ the Hamiltonian is the search Hamiltonian of $|\beta\rangle$ and $|s\rangle$: $$H = |\beta\rangle\langle\beta| + |s\rangle\langle s|.$$(2)^✦

Evolution and Measurement

A unitary $U$ of $S$ is a closed system evolution of $S$: an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ It carries a pure state $|\psi\rangle$ of $S$ to the pure state $U|\psi\rangle$.^✦ A Hamiltonian $H$ on $S$ is an observable on $S$, the energy of the system. The propagator of $H$ from time $t_1$ to time $t_2$, with Planck’s constant $\hbar$, is the unitary $$U(t_1, t_2) = \exp\bigl[-iH(t_2 - t_1)/\hbar\bigr],$$(3)^✦ which takes the state at $t_1$ to the state at $t_2$, $|\psi(t_2)\rangle = U(t_1, t_2)|\psi(t_1)\rangle$.

A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$, and a pure state $|\psi\rangle$ determines the state $|\psi\rangle\langle\psi|$, the projector onto its vector.

A measurement on $S$ with a finite set of outcomes is a family of measurement operators $M_i$ on the state space of $S$, one for each outcome $i$, satisfying the completeness relation $\sum_i M_i^\dagger M_i = 1$.^✦ The positive operator valued measure (POVM) of this measurement is the family of effects $E_i = M_i^\dagger M_i$, one for each outcome $i$. The probability of outcome $i$ when the measurement is performed on a state $\rho$ is the Born rule value $$p(i) = \operatorname{Tr}\bigl(M_i \rho M_i^\dagger\bigr) = \operatorname{Tr}(E_i \rho).$$(4)^✦

The projective measurement in an orthonormal basis $\{|b_i\rangle\}$ of $S$ is the measurement whose operator for outcome $i$ is the projector $|b_i\rangle\langle b_i|$.^✦ The computational basis measurement of the qudit is the projective measurement in its computational basis, with outcomes $0, \ldots, N-1$ and measurement operators $|i\rangle\langle i|$.^✦

The Claim

With $\hbar = 1$ the propagator of $H$ from $0$ to $t$ is $e^{-iHt}$. The Hamiltonian maps the plane spanned by $|s\rangle$ and $|\beta\rangle$ into itself, and with the overlap $\langle\beta|s\rangle = \sqrt{M/N}$ the evolution of $|s\rangle$ is $$e^{-iHt}|s\rangle = e^{-it}\Bigl(\cos\bigl(\sqrt{M/N}\,t\bigr)|s\rangle - i \sin\bigl(\sqrt{M/N}\,t\bigr)|\beta\rangle\Bigr).$$(5) At $t = \frac{\pi}{2}\sqrt{N/M}$ the cosine vanishes, and the qudit is in $|\beta\rangle$ up to a phase.

What Is Checked

The claim is stated over the qudit with $N$ levels, for every $N \geq 1$ and every nonempty set $T$ of its levels, and over two constructions on it: the propagator of the search Hamiltonian $H$ applied to $|s\rangle$, and the computational basis measurement with its Born rule probabilities.

The library proves that $|s\rangle$ and $|\beta\rangle$ are unit vectors and that $H$, a sum of two projectors, is self adjoint. For the measurement, the projectors $|i\rangle\langle i|$ satisfy the completeness relation, and the effects $E_i$ are positive with sum $1$.