Error tolerance of quantum annealing

Juan Atalaya, K. Birgitta Whaley, Murphy Yuezhen Niu

Tameem Albash, Walter Vinci, Daniel A. Lidar

Quantum annealing aims to exploit quantum mechanics to speed up the search for the solution to optimization problems. Most problems exhibit complete connectivity between the logical spin variables after they are mapped to the Ising spin Hamiltonian of quantum annealing. To account for hardware constraints of current and future physical quantum annealers, methods enabling the embedding of fully connected graphs of logical spins into a constant-degree graph of physical spins are therefore essential. Here, we compare the recently proposed embedding scheme for quantum annealing with all-to-all connectivity by Lechner, Hauke, and Zoller (LHZ) [Sci. Adv. 1, e1500838 (2015)] to the commonly used minor embedding (ME) scheme. Using both simulated quantum annealing and parallel tempering simulations, we find that for a set of instances randomly chosen from a class of fully connected, random Ising problems, the ME scheme outperforms the LHZ scheme when using identical simulation parameters, despite the fault tolerance of the latter to weakly correlated spin-flip noise. This result persists even after we introduce several decoding strategies for the LHZ scheme, including a minimum-weight decoding algorithm that results in substantially improved performance over the original LHZ scheme. We explain the better performance of the ME scheme in terms of more efficient spin updates, which allows it to better tolerate the correlated spin-flip errors that arise in our model of quantum annealing. Our results leave open the question of whether the performance of the two embedding schemes can be improved using scheme-specific parameters and new error correction approaches.

Daniel A. Lidar

Arnaud Rémi, François Damanet, Christophe Geuzaine

Solving Helmholtz problems using finite elements leads to the resolution of a linear system which is challenging to solve for classical computers. In this paper, we investigate how quantum annealers could address this challenge. We first express the linear system arising from the Helmholtz problem as a generalized eigenvalue problem (gEVP). The obtained gEVP is mapped into quadratic unconstrained binary optimization problems (QUBOs) which we solve using an adaptive quantum annealing eigensolver (AQAE) and its classical equivalent. We identify two key parameters in the success of AQAE for solving Helmholtz problems: the system condition number and the integrated control errors (ICE) in the quantum hardware. Our results show that a large system condition number implies a finer discretization grid for AQAE to converge, leading to a variable overhead, and that AQAE is either tolerant or not with respect to ICE depending on the gEVP. Finally, we establish lower bounds on the annealing time, narrowing the possibility of a quantum advantage for solving Helmholtz problems.

Andrea Di Gioacchino, Salvatore Mandrà, Eleanor Gilbert Rieffel

Y. S. Yang, P. Tyson, A. B Murphy

The weighted Max-Cut problem is an NP-hard problem with application implications. It is investigated on a cubic lattice with 113 nodes and mixed-signed random edge weights. For a fixed upper bound on edge weights, it has been demonstrated that the computational difficulty increases as the lower bound on edge weights becomes more negative. The solution time for the problem using a novel error-mitigated quantum annealing approach is compared with standard D-Wave quantum annealing (QA) and BQM hybrid solvers, as well as various classical solvers. For the QPU-embeddable weighted Max-Cut instances with mixed-signed edge weights, it has been quantitatively demonstrated that the SEMO (spin-error mitigation for optimisation) error-mitigated quantum annealing achieved substantially shorter time-to solution than standard D-Wave QA, D-Wave BQM, simulated annealing and Tabu search baselines. The error-mitigated quantum annealing approach presented in this article potentially elevates the efficiency and application scope of quantum annealing and would be applicable in solving other discrete optimisation problems that can be formulated as QUBO or Ising instances. The promising solution time advantage would be particularly impactful for time-critical optimisation applications.