Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization

Here we explore which heuristic quantum algorithms for combinatorial optimization might be most practical to try out on a small fault-tolerant quantum computer. We compile circuits for several variants of quantum-accelerated simulated annealing including those using qubitization or Szegedy walks to quantize classical Markov chains and those simulating spectral-gap-amplified Hamiltonians encoding a Gibbs state. We also optimize fault-tolerant realizations of the adiabatic algorithm, quantum-enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. Many of these methods are bottlenecked by calls to the same subroutines; thus, optimized circuits for those primitives should be of interest regardless of which heuristic is most effective in practice. We compile these bottlenecks for several families of optimization problems and report for how long and for what size systems one can perform these heuristics in the surface code given a range of resource budgets. Our results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup achieves an advantage over classical algorithms on modest superconducting qubit surface code processors without significant improvements in the implementation of the surface code. For instance, under quantum-favorable assumptions (e.g., that the quantum algorithm requires exactly quadratically fewer steps), our analysis suggests that quantum-accelerated simulated annealing requires roughly a day and a million physical qubits to optimize spin glasses that could be solved by classical simulated annealing in about 4 CPU-minutes.

Popular Summary

The prospect of quantum-accelerated algorithms for combinatorial optimization has driven much interest in quantum computing over the years. This is because faster optimization could prove transformative for diverse areas such as logistics, finance, machine learning, etc. Since most optimization problems are intractable in the worst case, the most practical algorithms (either quantum or classical) for these problems are often “heuristics,” which are nonexact algorithms that attempt to make use of whatever resources one has available rather than requiring a definite runtime. This paper provides the first comprehensive study of the resources required to execute popular quantum optimization heuristics on an error-corrected quantum computer.

We are able to assess the viability of many algorithms at once because most approaches to quantum optimization share the same “bottleneck” primitives when it comes to their realization within error correction. Specifically, we assess the viability of protecting these algorithms with the most popular version of error correction that is proposed for superconducting qubit processors (the surface code). But despite our algorithmic improvements and optimized compilations, we find that most of the studied computations suffer from extremely large constant factor overheads. In particular, due mostly to the fact that error-corrected quantum computers are often millions of times slower to compute optimization cost functions compared to classical computers, we conclude that the quantum algorithms need to provide much more than a quadratic speedup, or the overheads of error correction need to be reduced substantially, in order for these approaches to lead to practical quantum advantage.

Figure 1

Toffoli costs for direct evaluation of the LABS Hamiltonian by computing $H_k$ with a sum of tree sums. The average cost when computing and uncomputing the Hamiltonian is shown in (a). The cost of just computing and uncomputing $H_k$ (omitting the cost of summing the absolute values), when we just compute the Hamiltonian, is given in (b).

Figure 2

A circuit realizing the qubitized quantum walk operator $\mathcal{W}$ controlled on an ancilla qubit [26, 31]. Here $R$ is a reflection about the zero state for the entire $|\ell ⟩$ register, and therefore has Toffoli complexity $\log L+\mathcal{O}(1)$, where $\lceil \log L\rceil$ is the size of the $|\ell ⟩$ register. However, that overhead is negligible compared to the cost of the $\mathrm{PREPARE}$ and $\mathrm{SELECT}$ operators in the constructions of this paper.

Figure 3

(a) This figure shows how to perform QROM with variable spacing for the example where there are 4 bits, and we aim to group the input numbers as $0$, $1$, $2$, $3$, $\{4,5\}$, $\{6,7\}$, $\{8,9,10,11\}$, $\{12,13,14,15\}$. That is, we output the same data for inputs of $4$ and $5$, and so forth. The first four lines are the four input bits and the fifth is a control register. There are six Toffolis needed in this example for eight data points, with one more Toffoli for a control. (b) This figure shows how to perform QROM with variable spacing for the example where there are 4 bits, and we group the input numbers by powers of $2$ as $0$, $1$, 2–3, 4–7, and 8–15. There are three Toffolis needed in this example for five data points, with one more Toffoli for a control.

Figure 4

The numbers of intervals multiplied by $2^{-b_{\mathrm{fun}}/2}$ for the five functions we consider. In (a) we allow the intervals to have general endpoints, and in (b) we restrict the intervals to change by factors of $2$, to be consistent with the QROM method we use. This demonstrates that the number of intervals scales as $2^{b_{\mathrm{fun}}/2}$ with a scaling constant around $1$.

Figure 5

Effect of various methods of function approximation on optimization performance. We numerically simulate the quantum simulated annealing technique of Sec. 3e using various methods of approximating the transition probability. We consider the performance when the rotation angle is calculated to machine precision (“exact”), with piecewise linear approximation chosen to ensure the worst-case error does not exceed $0.01$ (“interpolated”), incorporating the inverse temperature $\beta$ into the definition of the function so that we are interpolating $f(z)=\arcsin [\exp (-\beta z/2)]$ rather than $f(z)=\arcsin [\exp (-z/2)]$ to avoid a multiplication (“include $\beta$”), and when we round off the output of the function to $7$ bits (“rounded output”). Each of these approximations builds upon the previous approximation, so we perform linear interpolation in all but the exact method. We simulate the performance averaging over $4096$ random SK instances on $16$ qubits, with $\beta$ linearly increasing over $50$ steps from $0$ to $1.2$. We report the average failure probability (bottom) as well as an estimate of the computational cost (top) in which we calculate the number of annealing steps divided by the probability of success. We observe that the differences in performance are not meaningfully affected by the method of function approximation, suggesting that we can pick the computationally cheapest option for our cost analysis.

Figure 6

Hadamard test circuit for computing the expectation value of one of the terms in the cost function. Here ${\mathcal{U}}_{\psi }$ is a unitary operation that prepares the ansatz state: ${\mathcal{U}}_{\psi }|0⟩=|\psi ⟩$.

Figure 7

Generalized form of a Hadamard test that we use for our QAOA implementation using LCU oracles. Here ${\mathcal{U}}_{\psi }$ is a unitary operation that prepares the ansatz state: ${\mathcal{U}}_{\psi }|0⟩=|\psi ⟩$.

Figure 8

The qubitized quantum walk operator $\mathcal{W}$ using the Szegedy approach.

Figure 9

The quantum walk operator using the Szegedy approach, where we have moved the controlled preparation to the end.

Figure 10

The probability for success using a rotation of the form $2\pi /2^s$ with $s=7$.

Figure 11

A circuit to perform addition on 5 qubits modulo $2^5$ when the most significant target qubit is in a $|+⟩$ state.

Figure 12

A simplification of Fig. 11 to eliminate the cnots on the last carry qubit. The $|+⟩$ state is omitted here because it is not acted upon.

Figure 13

A simplification of Fig. 12 where the last carry qubit is eliminated entirely and the Toffoli is replaced with a controlled phase.

Figure 14

In orange is the number of powers of $2$ needed to give integer $m$, when we allow additions and subtractions. The formula $\lceil (n+1)/2\rceil$ is shown in orange, where the number of bits required to represent $m$ is $n=\lceil \log (m+1)\rceil$.

Figure 15

A depiction of the binary-to-unary circuit mapping an $n$-bit binary number to an $N$-bit ($N=2^n$) unary encoding of the input. In (a) we have the specific example where $N=8$ (i.e., ${\mathrm{B2U}}^8$). In (b) we have the circuit (${\mathrm{B2U}}^N$) defined recursively (in terms of ${\mathrm{B2U}}^{N/2}$), In (b) the controlled-swap symbols are used to represent many controlled-swaps, one for each qubit in the relevant registers. The symbol “$>0$” signifies that the multi-cnot is activated on any state other than the state of all zeros, which can be implemented with a cascade of cnots because the input is promised to have at most one nonzero qubit. The labeled rails in both circuit diagrams refer to the bits of the binary-encoded input $k$, and the unlabeled inputs are fresh ancillae.

Figure 16

A circuit to perform addition on 5 qubits modulo $2^5$ from Ref. [35].

Figure 17

(a) The component of the adder circuit where the qubit containing classical data is the target of a cnot. (b) The circuit may be rewritten so the value on the second qubit is never changed.

Figure 18

A circuit to perform addition on 5 qubits modulo $2^5$ such that the $i_j$ registers are only used as controls. Because they are only used as controls, if the number $i$ is given classically the addition can be performed entirely using classical control, without using any ancillas to store $i$.

Figure 19

Numerical justification for our choice of $d$ in Eq. (D17). We plot the ratio of $(d+1)/2^{}d$ to the error bound $\epsilon$. A value less than $1$ ensures that our choice of $d$ yields a multiplication result whose error is less than $\epsilon$.

Figure 20

Energy evaluation for the $L$-term spin model and QUBO.

Figure 21

Energy evaluation for LABS model.