Quantum Simulations of Classical Annealing Processes

We describe a quantum algorithm that solves combinatorial optimization problems by quantum simulation of a classical simulated annealing process. Our algorithm exploits quantum walks and the quantum Zeno effect induced by evolution randomization. It requires order $1/\sqrt{\delta }$ steps to find an optimal solution with bounded error probability, where $\delta$ is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order $1/\delta$ steps required by the latter.

Figure 1

(a) Phase estimation algorithm. The top $p$-qubit register encodes a $p$-bit approximation to an eigenphase of $W_{k+1}$ on readout, and is initialized with Hadamard gates to an equal superposition state. The second register’s states are in ${\mathcal{H}}_A\otimes {\mathcal{H}}_B$. A sequence of $2^p-1$ controlled $W_{k+1}$ operations is applied, and the first register is measured after an inverse quantum Fourier transform. If the measurement outcome is $|0{⟩}^{\otimes p}$, the second register is approximately projected onto a 0-phase eigenstate of $W_{k+1}$. (b) Randomization procedure. If the PEA’s outcome is ignored, the overall effect on ${\mathcal{H}}_A\otimes {\mathcal{H}}_B$ is equivalent to the one induced by initializing a set of $p$ bits (first register) in a random state $r$, with $r\in \{0,\dots ,2^p-1\}$, and by acting on ${\mathcal{H}}_A\otimes {\mathcal{H}}_B$ with $(W_{k+1}{)}^r$. Here, double vertical lines indicate classical control.

Figure 2

Flow diagram for the QSA. The parameters $r$, $s$, and $Q$ are chosen so that the final state ${\rho }^Q$ is sufficiently close to the desired state $|{\psi }_0^Q⟩$ (see text).