Readiness of Quantum Optimization Machines for Industrial Applications
arXiv:1708.09780 · doi:10.1103/PhysRevApplied.12.014004
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.
arXiv comment22 pages, 12 figures. Content updated according to Phys. Rev. Applied version
References in corpus (40)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Experimental signature of programmable quantum annealing
- Quantum Adiabatic Markovian Master Equations
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers
- What is the Computational Value of Finite Range Tunneling?
- Feedback-optimized parallel tempering Monte Carlo
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- A case study in programming a quantum annealer for hard operational planning problems
- Quantum versus Classical Annealing of Ising Spin Glasses
- Probing for quantum speedup in spin glass problems with planted solutions
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- 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
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Modernizing Quantum Annealing using Local Searches
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Bayesian Network Structure Learning Using Quantum Annealing
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- 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
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
- Ramsey numbers and adiabatic quantum computing
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- Experimental quantum annealing: case study involving the graph isomorphism problem
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Quantum annealing via environment-mediated quantum diffusion
- Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
- Approximate Model-Based Diagnosis Using Greedy Stochastic Search
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 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