Experimental quantum annealing: case study involving the graph isomorphism problem

Quantum annealing (QA) is a proposed combinatorial optimization technique meant to exploit quantum mechanical effects such as tunneling and entanglement1. Machines purportedly implementing a type of quantum annealing have recently become available2. While the extent of “quantumness” in these implementations is not fully understood, some evidence for quantum mechanical effects playing a useful role in the processing has been appearing3,4,5. Aside from the debate over quantumness, there are interesting questions regarding how to effectively solve a real-world problem using a quantum annealer. Quantum annealing-based solvers require a combination of annealing and classical pre- and post-processing; at this early stage, little is known about how to partition and optimize the processing. For instance, current quantum annealers have severe practical limitations on the size of problems that can be handled. Can the pre-processing algorithms be modified in order to improve scalability? A second question involves post-processing. Quantum annealers provide solutions to an “embedded” version of a problem involving physical qubits. Post-processing is generally required for translating these to solutions to the original problem involving logical qubits (aka variables). Occasionally, a chain of physical qubits representing a single variable resolves to an inconsistent state, a scenario known as a broken chain. Studies are needed regarding broken chains and the possibility of classical error correction during post-processing. This article presents an experimental case study of quantum annealing and some of the factors involved in real-world solvers, using a 504-qubit D-Wave Two machine. An example of parsimonious pre-processing is considered, along with post-processing majority voting. Through experiments on a 504-qubit D-Wave Two machine, we quantify the QA success probabilities and the impact of the methods under study. We use the graph isomorphism (GI) problem as the problem of focus. The GI problem is to determine whether two input graphs G1,2 are in essence the same, such that the adjacency matrices can be made identical with a relabeling of vertices. This problem is an interesting candidate for several reasons. First, an accurate quantum annealing-based solver for GI has never been implemented. Second, quantum approaches can sometimes provide new insight into the structure of a problem, even if no speedup over classical approaches is achieved or even expected. Third, the GI problem is mathematically interesting; though many sub-classes of the problem can be solved in polynomial time by specialized classical solvers, the run time of the best general solution is exponential and has remained at since 19836,7. The classical computational complexity of the problem is currently considered to be NP-intermediate8, and the quantum computational complexity of the problem is unknown. Graph isomorphism is a non-abelian hidden subgroup problem and is not known to be easy in the quantum regime9,10. Lastly, the GI problem is of practical interest. It appears in fields such as very large-scale integrated circuit design, where a circuit’s layout graph must be verified to be equivalent to its schematic graph11, and in drug discovery and bio-informatics, where a graph representing a molecular compound must be compared to an entire database, often via a GI tool that performs canonical labeling6. This article relates to previous works as follows. A pre-print by King and McGeoch discusses tuning of quantum annealing algorithms, including the use of low-cost classical post-processing majority voting similar to what is evaluated in this article12. Our study goes further regarding pre-processing (designing a Hamiltonian to generate compact Ising models) and covers graph isomorphism rather than problems such as random not-all-equal 3-SAT. A work by Rieffel et al. maps real-world problems such as graph coloring to a D-Wave quantum annealer13. Regarding the graph isomorphism problem in particular, multiple attempts have been made using adiabatic quantum annealing. One of the first attempts assigned a Hamiltonian to each graph and conjectured that measurements taken during each adiabatic evolution could be used to distinguish non-isomorphic pairs14. A subsequent experimental study using a D-Wave quantum annealer found that using quantum spectra in this manner was not sufficient to distinguish non-isomorphic pairs15. A second approach converted a GI problem to a combinatorial optimization problem whose non-negative cost function has a minimum of zero only for an isomorphic pair. The approach required problem variables and additional ancillary variables. It was numerically simulated up to N = 7 but not validated on a quantum annealing processor16. An alternative GI Hamiltonian was proposed by Lucas17.