Embedding equality constraints of optimization problems into a quantum annealer
Summary: Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type \(\sum x_i = k\) for binary variables \(x_i\). Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed \(k\).
- Integer programming techniques for minor-embedding in quantum annealers
- Optimization and quantum annealing
- Quantum annealing and related optimization methods
- A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
- Garden optimization problems for benchmarking quantum annealers
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Solving SAT and MaxSAT with a quantum annealer: foundations and a preliminary report
- Convergence theorems for quantum annealing
- Quantum annealing of hard problems
- Quantum annealing learning search for solving QUBO problems
- A case study in programming a quantum annealer for hard operational planning problems
- Adiabatic quantum programming: minor embedding with hard faults
- Asymptotic Analysis for Penalty and Barrier Methods in Convex and Linear Programming
- Computationally Related Problems
- Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems
- Efficiently embedding QUBO problems on adiabatic quantum computers
- Embedding equality constraints of optimization problems into a quantum annealer
- Fast clique minor generation in Chimera qubit connectivity graphs
- Graph partitioning
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- Practical augmented Lagrangian methods for constrained optimization
- The MathSAT5 SMT solver
- The unconstrained binary quadratic programming problem: a survey
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- Enhancing quantum annealing performance for the molecular similarity problem
- Biclustering with a quantum annealer
- Embedding equality constraints of optimization problems into a quantum annealer
- Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing
- Quantum annealing learning search for solving QUBO problems
- Leveraging special-purpose hardware for local search heuristics
- Boolean hierarchical Tucker networks on quantum annealers
- FEqa: Finite element computations on quantum annealers
- Optimal quadratic reformulations of fourth degree pseudo-Boolean functions
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Penalty and partitioning techniques to improve performance of QUBO solvers
- Least-squares solutions to polynomial systems of equations with quantum annealing
- Models in quantum computing: a systematic review
- Performing fully parallel constraint logic programming on a quantum annealer
- A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
- A distributed optimization approach via symmetric group actions under time-varying communication networks
- Practical integer-to-binary mapping for quantum annealers
This page was built for publication: Embedding equality constraints of optimization problems into a quantum annealer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2003330)
