Optimal sufficient requirements on the embedded Ising problem in polynomial time
From MaRDI portal
(Redirected from Publication:6073965)
Abstract: One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which shall actually be solved. We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. Due to the redundancy of several constraints, we can show that the formally exponentially large optimization problem can be reduced and finally solved in polynomial time for the standard embedding setting where the embedded vertices induce trees. This allows to formulate provably equivalent embedded Ising problems in a practical setup.
Recommendations
- Polynomial-Time Approximation Algorithms for the Ising Model
- scientific article; zbMATH DE number 177833
- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
- Critical Ising on the square lattice mixes in polynomial time
- Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
- Complexity of Ising polynomials
- Approximation Algorithms for the Random Field Ising Model
- Approximability of the ground state problem for certain Ising spin glasses
Cites work
- Combinatorial optimization. Theory and algorithms
- Embedding of complete graphs in broken Chimera graphs
- Expander graphs and their applications
- Fast clique minor generation in Chimera qubit connectivity graphs
- Graph minors. XIII: The disjoint paths problem
- Graph theory
- Minimizing minor embedding energy: an application in quantum annealing
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
- Quantum annealing versus digital computing. An experimental comparison
- Sparsest cuts and bottlenecks in graphs
- The unconstrained binary quadratic programming problem: a survey
Cited in
(2)
This page was built for publication: Optimal sufficient requirements on the embedded Ising problem in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6073965)
