Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems

Abstract

Quantum annealing is a novel type of analog computation that aims to use quantum mechanical fluctuations to search for optimal solutions of Ising problems. Quantum annealing in the Transverse Ising model, implemented on D-Wave QPUs, are available as cloud computing resources. In this article we report concise benchmarks across three generations of D-Wave quantum annealers, consisting of four different devices, for the NP-Hard combinatorial optimization problems unweighted maximum clique and unweighted maximum cut on random graphs. The Ising, or equivalently QUBO, formulation of these problems do not require auxiliary variables for order reduction, and their overall structure and weights are not highly complex, which makes these problems simple test cases to understand the sampling capability of current D-Wave quantum annealers. All-to-all minor embeddings of size $52$, with relatively uniform chain lengths, are used for a direct comparison across the Chimera, Pegasus, and Zephyr device topologies. A grid search over annealing times and the minor embedding chain strengths is performed in order to determine the level of reasonable performance for each device and problem type. Experiment metrics that are reported are approximation ratios for non-broken chain samples and chain break proportions. How fairly the quantum annealers sample optimal maximum cliques, for instances which contain multiple maximum cliques, is also quantified using entropy of the measured ground state distributions. The newest generation of quantum annealing hardware, which has a Zephyr hardware connectivity, performed the best overall with respect to approximation ratios and chain break frequencies.

References in corpus (23)

• Mathematical Foundation of Quantum Annealing
• Quantum Annealing for Industry Applications: Introduction and Review
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Qubit spin ice
• Benchmarking Hamiltonian Noise in the D-Wave Quantum Annealer
• Parallel Quantum Annealing
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Scaling overhead of embedding optimization problems in quantum annealing
• Benchmark test of Black-box optimization using D-Wave quantum annealer
• Quantum annealing simulation of out-of-equilibrium magnetization in a spin-chain compound
• Sampling on NISQ Devices: "Who's the Fairest One of All?"
• Experimental Realization of Classical ${\mathbb{Z}}_2$ Spin Liquids in a Programmable Quantum Device
• Computational Overhead of Locality Reduction in Binary Optimization Problems
• Quantum Annealing Algorithms for Boolean Tensor Networks
• Fair sampling of ground-state configurations of binary optimization problems
• Fair Sampling Error Analysis on NISQ Devices
• Advanced unembedding techniques for quantum annealers
• Perils of Embedding for Quantum Sampling
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• Ground-state statistics from annealing algorithms: Quantum vs classical approaches

Cited by in corpus (10)

• Scalable Connectivity for Ising Machines: Dense to Sparse
• Lagrange Oscillatory Neural Networks for Constraint Satisfaction and Optimization
• Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Quantum-inspired dynamical models on quantum and classical annealers
• Hamiltonian formulations of centroid-based clustering
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Quantum annealing and condensed matter physics
• Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization