Readiness of Quantum Optimization Machines for Industrial Applications

Abstract

There have been multiple attempts to demonstrate that quantum annealing and, in particular, quantum annealing on quantum annealing machines, has the potential to outperform current classical optimization algorithms implemented on CMOS technologies. The benchmarking of these devices has been controversial. Initially, random spin-glass problems were used, however, these were quickly shown to be not well suited to detect any quantum speedup. Subsequently, benchmarking shifted to carefully crafted synthetic problems designed to highlight the quantum nature of the hardware while (often) ensuring that classical optimization techniques do not perform well on them. Even worse, to date a true sign of improved scaling with the number of problem variables remains elusive when compared to classical optimization techniques. Here, we analyze the readiness of quantum annealing machines for real-world application problems. These are typically not random and have an underlying structure that is hard to capture in synthetic benchmarks, thus posing unexpected challenges for optimization techniques, both classical and quantum alike. We present a comprehensive computational scaling analysis of fault diagnosis in digital circuits, considering architectures beyond D-wave quantum annealers. We find that the instances generated from real data in multiplier circuits are harder than other representative random spin-glass benchmarks with a comparable number of variables. Although our results show that transverse-field quantum annealing is outperformed by state-of-the-art classical optimization algorithms, these benchmark instances are hard and small in the size of the input, therefore representing the first industrial application ideally suited for testing near-term quantum annealers and other quantum algorithmic strategies for optimization problems.

22 pages, 12 figures. Content updated according to Phys. Rev. Applied version

References in corpus (10)

• Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers
• Feedback-optimized parallel tempering Monte Carlo
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Interplay of quantum and thermal fluctuations in a frustrated magnet
• On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
• Bayesian Network Structure Learning Using Quantum Annealing
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods

Cited by in corpus (22)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Perspectives of quantum annealing: Methods and implementations
• Challenges and Opportunities in Quantum Optimization
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• Quantum Computing: Towards Industry Reference Problems
• Benchmarking Hamiltonian Noise in the D-Wave Quantum Annealer
• A quantum annealer with fully programmable all-to-all coupling via Floquet engineering
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• QUARK: A Framework for Quantum Computing Application Benchmarking
• Resonant Quantum Principal Component Analysis
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
• Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing
• Computational Overhead of Locality Reduction in Binary Optimization Problems
• Measurement-based adaptation protocol with quantum reinforcement learning in a Rigetti quantum computer
• Energy landscapes of combinatorial optimization in Ising machines
• Garden optimization problems for benchmarking quantum annealers
• Solving systems of Boolean multivariate equations with quantum annealing
• The Coming Decades of Quantum Simulation
• Quantum annealing with pairs of ${}^2\Sigma$ molecules as qubits
• Introduction to Quantum Error Correction with Stabilizer Codes
• Minor embedding with Stuart-Landau oscillator networks
• A Statistical Analysis for Per-Instance Evaluation of Stochastic Optimizers: Avoiding Unreliable Conclusions