The Exercise

A quantum search looks for one marked level $x$ of a system with $d$ levels. It starts in the uniform superposition $|\psi\rangle$ of the $d$ basis states, whose overlap with the marked state $|x\rangle$ is only $1/\sqrt{d}$. The exercise lets the system evolve under the Hamiltonian $H = |x\rangle\langle\psi| + |\psi\rangle\langle x|$, which couples the start state to the solution. Evolution under $H$ for the time $\pi/2$ then turns $|\psi\rangle$ into $|x\rangle$, however large $d$ is.^✦ The evolution can also be simulated: $H$ splits into three terms built from projectors, and $m$ symmetric products of their evolutions over a short time step $\Delta t$ follow the evolution under $H$ with an error of order $m\Delta t^3$.^✦

The library states both parts for the qudit with any number of levels $d \ge 1$ and any marked level $x$.

A Quantum System

A quantum system is a physical system whose state space is a finite dimensional complex Hilbert space.^✦ A pure state $|\varphi\rangle$ of a system $S$ is a unit vector in the state space of $S$, determined physically up to a global phase.^✦ A state $\rho$ of $S$ is a positive operator of unit trace on the state space of $S$.^✦ Each pure state $|\varphi\rangle$ gives the state $|\varphi\rangle\langle\varphi|$, the projector onto its vector.^✦

The qudit with $d$ levels is the quantum system whose state space is $\mathbb{C}^d$ with its standard inner product.^✦ For a level $i$ among $0, \ldots, d-1$, the computational basis state $|i\rangle$ is the pure state of the qudit whose vector has entry $1$ at $i$ and $0$ elsewhere.^✦ For $d \ge 1$, the uniform superposition $|\psi\rangle$ is the pure state of the qudit in which every basis state enters with the same amplitude, $$|\psi\rangle = \frac{1}{\sqrt{d}} \sum_{k=0}^{d-1} |k\rangle.$$(1)^✦

Evolution Under a Hamiltonian

A unitary $U$ of a system $S$ is an operator on the state space of $S$ with $U^\dagger U = U U^\dagger = 1$.^✦ It describes a closed evolution of $S$ and carries a pure state $|\varphi\rangle$ to the pure state $U|\varphi\rangle$. An observable $A$ of $S$ is a self adjoint operator on the state space of $S$, $A^\dagger = A$.^✦ Taken as the Hamiltonian, an observable $H$ has as its propagator from time $t_1$ to time $t_2$ the unitary $$U(t_1, t_2) = \exp\bigl[-iH(t_2 - t_1)/\hbar\bigr],$$(2)^✦ which solves the Schrödinger equation, $|\varphi(t_2)\rangle = U(t_1, t_2)|\varphi(t_1)\rangle$. In both claims $\hbar = 1$ and $t_1 = 0$, and evolution for a time $t$ is $e^{-iHt}$.

The coupling Hamiltonian of two pure states $|a\rangle$ and $|b\rangle$ of a system $S$ is the observable $|a\rangle\langle b| + |b\rangle\langle a|$ on $S$.^✦ On the qudit with $d \ge 1$ levels, the alternative search Hamiltonian for the marked level $x$ is the coupling Hamiltonian of the basis state $|x\rangle$ and the uniform superposition (1): $$H = |x\rangle\langle\psi| + |\psi\rangle\langle x|.$$(3)^✦

The Claim

Simulating the Evolution

The gate error $E(U, V)$ between two unitaries $U$ and $V$ of a system is the operator norm of their difference, $$E(U, V) = \lVert U - V \rVert = \max_{\langle\varphi|\varphi\rangle = 1} \bigl\lVert (U - V)|\varphi\rangle \bigr\rVert.$$(5)^✦

For observables $H_1, \ldots, H_L$ of a system and a time step $\Delta t$, the symmetric Trotter step is the unitary obtained by multiplying the propagators $e^{-iH_k\Delta t}$ of the terms, first in the order $1, \ldots, L$ and then in the order $L, \ldots, 1$.^✦

The coupling Hamiltonian of $|a\rangle$ and $|b\rangle$ is the sum of three terms built from projectors, $H_1 = (|a\rangle + |b\rangle)(\langle a| + \langle b|)$, $H_2 = -|a\rangle\langle a|$ and $H_3 = -|b\rangle\langle b|$, and its Trotter step for a time step $\Delta t$ is the symmetric Trotter step of these three. For the alternative search Hamiltonian, where $|a\rangle = |x\rangle$ and $|b\rangle = |\psi\rangle$, this is the simulation step $$U_{\Delta t} = e^{-iH_1\Delta t}\, e^{-iH_2\Delta t}\, e^{-iH_3\Delta t}\, e^{-iH_3\Delta t}\, e^{-iH_2\Delta t}\, e^{-iH_1\Delta t}.$$(6)^✦

A step runs each term for the time $2\Delta t$, so $m$ steps are set against the evolution under $H$ for the time $2m\Delta t$.

For $m \ge 1$ and $\Delta t = \pi/(4m)$, the $m$ steps reach the time $\pi/2$ of (4) with a gate error of at most $\alpha\pi^3/(64m^2)$.

What Is Checked

The first claim is stated over the qudit with $d$ levels, its basis state $|x\rangle$, the uniform superposition $|\psi\rangle$, the propagator of the alternative search Hamiltonian, and the states $|\varphi\rangle\langle\varphi|$ of the pure states it compares; the second adds the simulation step $U_{\Delta t}$ and the gate error.

About these constructions the library proves that $|\psi\rangle$ and every basis state $|i\rangle$ are unit vectors, that the coupling Hamiltonian and its three terms are self adjoint, that the propagator of an observable and the symmetric Trotter step are unitary, that a unitary takes unit vectors to unit vectors, and that $|\varphi\rangle\langle\varphi|$ is a density operator.