Quantum Annealing versus Digital Computing

DOI10.1145/3459606zbMath1499.68123OpenAlexW3182160993MaRDI QIDQ5102052

Petra Mutzel, Elisabeth Lobe, Michael Jünger, Giovanni Rinaldi, Tobias Stollenwerk, Franz Rendl, Gerhard Reinelt

Publication date: 6 September 2022

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3459606

zbMATH Keywords

integer programmingsemidefinite programmingIsing modelbranch and cutquantum annealingexperimental evaluationmaximum cut problemquadratic unconstrained binary optimizationChimera graphsexact methods for combinatorial optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Optimal sufficient requirements on the embedded Ising problem in polynomial time, Faster exact solution of sparse maxcut and QUBO problems, Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B, Embedding of complete graphs in broken Chimera graphs, Minor embedding in broken chimera and derived graphs is NP-complete

Cites Work

• Unnamed Item
• Unnamed Item
• Fast clique minor generation in Chimera qubit connectivity graphs
• Lifting and separation procedures for the cut polytope
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• PANDA: a software for polyhedral transformations
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Experiments in quadratic 0-1 programming
• The ellipsoid method and its consequences in combinatorial optimization
• Optimization, approximation, and complexity classes
• Easy and difficult objective functions for max cut
• A fixed-parameter algorithm for the Max-Cut problem on embedded 1-planar graphs
• QUBO formulations for the graph isomorphism problem and related problems
• Exact ground states of two-dimensional \(\pm J\) Ising spin glasses
• A case study in programming a quantum annealer for hard operational planning problems
• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the cut polytope
• Reducibility among Combinatorial Problems
• Maximum Cut Parameterized by Crossing Number
• What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
• Unifying maximum cut and minimum cut of a planar graph