Experimental quantum annealing: case study involving the graph isomorphism problem

Abstract

Quantum annealing is a proposed combinatorial optimization technique meant to exploit quantum mechanical effects such as tunneling and entanglement. Real-world 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. 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 and the graph isomorphism problem. To illustrate the role of classical pre-processing, a compact Hamiltonian is presented that enables a reduced Ising model for each problem instance. On random N-vertex graphs, the median number of variables is reduced from N^2 to fewer than N lg N and solvable graph sizes increase from N = 5 to N = 13. Additionally, a type of classical post-processing error correction is evaluated. While the solution times are not competitive with classical approaches to graph isomorphism, the enhanced solver ultimately classified correctly every problem that was mapped to the processor and demonstrated clear advantages over the baseline approach. The results shed some light on the nature of real-world quantum annealing and the associated hybrid classical-quantum solvers.

15 pages, 6 figures

References in corpus (4)

• A practical heuristic for finding graph minors
• Reexamining classical and quantum models for the D-Wave One processor
• Algorithm engineering for a quantum annealing platform
• Computational Role of Collective Tunneling in a Quantum Annealer

Cited by in corpus (22)

• Quantum Annealing for Constrained Optimization
• Basic Elements for Simulations of Standard Model Physics with Quantum Annealers: Multigrid and Clock States
• Driver Hamiltonians for constrained optimization in quantum annealing
• Graph isomorphism and Gaussian boson sampling
• Readiness of Quantum Optimization Machines for Industrial Applications
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Practical Integer-to-Binary Mapping for Quantum Annealers
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• Memory-Efficient FPGA Implementation of Stochastic Simulated Annealing
• Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems
• Exponential capacity of associative memories under quantum annealing recall
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• Local Energy Distribution Based Hyperparameter Determination for Stochastic Simulated Annealing
• GPU-accelerated simulated annealing based on p-bits with real-world device-variability modeling
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Stochastic Simulated Quantum Annealing for Fast Solution of Combinatorial Optimization Problems
• Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization
• Performance Models for Split-execution Computing Systems
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints
• TIGER: Topology-aware Assignment using Ising machines Application to Classical Algorithm Tasks and Quantum Circuit Gates
• Finding Hadamard matrices by a quantum annealing machine