A practical heuristic for finding graph minors

Abstract

We present a heuristic algorithm for finding a graph $H$ as a minor of a graph $G$ that is practical for sparse $G$ and $H$ with hundreds of vertices. We also explain the practical importance of finding graph minors in mapping quadratic pseudo-boolean optimization problems onto an adiabatic quantum annealer.

16 pages, 7 figures

Cited by in corpus (75)

• A case study in programming a quantum annealer for hard operational planning problems
• Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
• A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
• Support vector machines on the D-Wave quantum annealer
• Application of Quantum Annealing to Nurse Scheduling Problem
• Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
• Traffic Signal Optimization on a Square Lattice with Quantum Annealing
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
• Quantum-assisted Helmholtz machines: A quantum-classical deep learning framework for industrial datasets in near-term devices
• Bayesian Network Structure Learning Using Quantum Annealing
• Prime factorization using quantum annealing and computational algebraic geometry
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Flight Gate Assignment with a Quantum Annealer
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Parallel Quantum Annealing
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Quantum processor-inspired machine learning in the biomedical sciences
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
• Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer
• Algorithm engineering for a quantum annealing platform
• Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods
• Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks
• Charged particle tracking with quantum annealing-inspired optimization
• Quantum Annealing for Large MIMO Downlink Vector Perturbation Precoding
• An Application of Quantum Annealing Computing to Seismic Inversion
• Sampling on NISQ Devices: "Who's the Fairest One of All?"
• Simulated Quantum Annealing with Two All-to-All Connectivity Schemes
• Evaluating Ising Processing Units with Integer Programming
• A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting
• Quantum adiabatic machine learning with zooming
• Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm
• Equation Planting: A Tool for Benchmarking Ising Machines
• Quantum Annealing Algorithms for Boolean Tensor Networks
• Guiding Principle for Minor-Embedding in Simulated-Annealing-Based Ising Machines
• Heterogeneous Quantum Computing for Satellite Constellation Optimization: Solving the Weighted K-Clique Problem
• Homology Computation of Large Point Clouds using Quantum Annealing
• Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits
• Fast clique minor generation in Chimera qubit connectivity graphs
• Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• Phase transition of Frustrated Ising model via D-wave Quantum Annealing Machine
• Defence against adversarial attacks using classical and quantum-enhanced Boltzmann machines
• GPU Based Parallel Ising Computing for Combinatorial Optimization Problems in VLSI Physical Design
• 4-clique Network Minor Embedding for Quantum Annealers
• Hybrid quantum-classical computation for automatic guided vehicles scheduling
• Track clustering with a quantum annealer for primary vertex reconstruction at hadron colliders
• Computing Wasserstein Distance for Persistence Diagrams on a Quantum Computer
• Accelerating equilibrium spin-glass simulations using quantum annealers via generative deep learning
• Breaking RSA Security With A Low Noise D-Wave 2000Q Quantum Annealer: Computational Times, Limitations And Prospects
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form
• Dynamical process of a bit-width reduced Ising model with simulated annealing
• Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems
• A Decomposition Method for the Hybrid Quantum-Classical Solution of the Number Partitioning Problem
• Dynamic Optimization on Quantum Hardware: Feasibility for a Process Industry Use Case
• Analyzing the Effectiveness of Quantum Annealing with Meta-Learning
• Quantum Annealing for Prime Factorization
• A Lattice-Reduction Aided Vector Perturbation Precoder Relying on Quantum Annealing
• Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
• Quantum Annealing Formulation for Binary Neural Networks
• Optimization of Connection Patterns between Mobile Phones and Base Stations using Quantum Annealing
• Mapping NP-Hard Problems to Restricted Adiabatic Quantum Architectures
• Solving Large Break Minimization Problems in a Mirrored Double Round-robin Tournament Using Quantum Annealing
• Quantum Software Ecosystem Design
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• A CMOS-compatible Ising Machine with Bistable Nodes
• Leveraging Quantum Annealer to identify an Event-topology at High Energy Colliders
• Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer
• Minor embedding with Stuart-Landau oscillator networks
• Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes