A practical heuristic for finding graph minors
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 13 Pith papers
-
Ember: An Extensible Benchmark Suite for Quantum Annealing Embedding Algorithms
Ember introduces a reproducible benchmark suite with 24,016 graph instances for evaluating quantum annealing embedding algorithms across Chimera, Pegasus, and Zephyr topologies.
-
Ember: An Extensible Benchmark Suite for Quantum Annealing Embedding Algorithms
Ember provides the first standardized, reproducible benchmark framework with 24,016 diverse graph instances for quantum annealing embedding algorithms, showing that no single algorithm performs best across all graph families.
-
New minor minimal non-apex graphs
All minimal non-apex graphs with 12 or fewer vertices or 26 or fewer edges are listed, and every 13-vertex graph with minimum degree 6 is shown to be apex or to contain a K6 minor.
-
Subsystem relaxation and a calibrated sampling diagnostic for programmable quantum annealers
A subsystem-environment protocol on programmable quantum annealers identifies conditions for initial-state independence and supplies a diagnostic for reliable open-system sampling.
-
Solving Classical and Quantum Spin Glasses with Deep Boltzmann Quantum States
Deep Boltzmann Quantum States with natural-gradient optimization and annealing-like training match exact or best-known solutions for large infinite-range Ising spin glasses and solve job shop scheduling instances.
-
Exploring Quantum Annealing for Coarse-Grained Protein Folding
Compares quantum annealing models for coarse-grained protein folding, proposes interleaved-grid tetrahedral encoding, and reports hardware limits from embedding alongside scaling gains over classical simulated anneali...
-
Schedule-dependent basin occupation in a programmable quantum annealer
Cycled reverse annealing on D-Wave devices shows schedule-dependent basin occupation with hardware autocorrelations bracketed between classical and quantum equilibrium references, and a pre-registered linear landscape...
-
Schedule-dependent basin occupation in a programmable quantum annealer
Cycled reverse annealing on D-Wave devices produces autocorrelation bracketed between parallel tempering and simulated quantum annealing references, showing schedule-dependent basin occupation on specific Ising instances.
-
Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems
Neural networks transform initial embeddings into feasible unit disk configurations for QUBO problems on Rydberg qubits and outperform the Gurobi solver in experiments.
-
Neural and Tensor Networks in the Study of Quantum Annealing Processors
The thesis introduces a topology-aware tensor-network heuristic called SpinGlassPEPS.jl and thermodynamic metrics to benchmark quantum annealers on Ising problems while accounting for dissipation and effective temperature.
-
Playing Dice with the Universe: Programming Quantum Computers to Play Traditional Games
A quantum annealer can play tic-tac-toe by encoding only the game rules and sampling from paths leading to wins or losses.
-
Multi-tasking through quantum annealing
MTQA embeds multiple NP-hard problems such as minimum vertex cover and graph partitioning into spatially distinct regions on quantum hardware, delivering comparable solution quality to single-task annealing with reduc...
-
Entangled happily ever after: Wedding reception seating mapped to classical and quantum optimizers
Wedding reception seating was encoded as a cost function network and solved more reliably by classical Monte Carlo than by quantum annealing on D-Wave hardware using mappings previously developed for protein design.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.