A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
arXiv:1406.7601 · doi:10.1140/epjst/e2015-02347-y
Abstract
Diagnosing the minimal set of faults capable of explaining a set of given observations, e.g., from sensor readouts, is a hard combinatorial optimization problem usually tackled with artificial intelligence techniques. We present the mapping of this combinatorial problem to quadratic unconstrained binary optimization (QUBO), and the experimental results of instances embedded onto a quantum annealing device with 509 quantum bits. Besides being the first time a quantum approach has been proposed for problems in the advanced diagnostics community, to the best of our knowledge this work is also the first research utilizing the route Problem QUBO Direct embedding into quantum hardware, where we are able to implement and tackle problem instances with sizes that go beyond previously reported toy-model proof-of-principle quantum annealing implementations; this is a significant leap in the solution of problems via direct-embedding adiabatic quantum optimization. We discuss some of the programmability challenges in the current generation of the quantum device as well as a few possible ways to extend this work to more complex arbitrary network graphs.
References in corpus (22)
- 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
- Quantum Computation by Adiabatic Evolution
- Quantum Adiabatic Markovian Master Equations
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- A practical heuristic for finding graph minors
- A case study in programming a quantum annealer for hard operational planning problems
- Quantum Optimization of Fully-Connected Spin Glasses
- Experimental Demonstration of a Robust and Scalable Flux Qubit
- Optimized simulated annealing for Ising spin glasses
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
- Adiabatic Quantum Computing for Random Satisfiability Problems
- Bayesian Network Structure Learning Using Quantum Annealing
- Ramsey numbers and adiabatic quantum computing
- Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization
Cited by in corpus (31)
- Noisy intermediate-scale quantum (NISQ) algorithms
- Perspectives of quantum annealing: Methods and implementations
- Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
- Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
- A NASA Perspective on Quantum Computing: Opportunities and Challenges
- Bayesian Network Structure Learning Using Quantum Annealing
- Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks
- Multivariable Optimization: Quantum Annealing & Computation
- Readiness of Quantum Optimization Machines for Industrial Applications
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
- Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks
- Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
- Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
- Degeneracy, degree, and heavy tails in quantum annealing
- Adiabatic Quantum Optimization for Associative Memory Recall
- A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- borealis - A generalized global update algorithm for Boolean optimization problems
- Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- Test Case Minimization with Quantum Annealers
- A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
- Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
- Quantum-assisted finite-element design optimization
- Quantum annealing with pairs of molecules as qubits
- Mapping State Transition Susceptibility in Quantum Annealing
- Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
- Classical Simulated Annealing Using Quantum Analogues
- Statistical Analysis of Quantum Annealing
- Experimental verification of the inertial theorem control protocols