Embedding equality constraints of optimization problems into a quantum annealer
type: Item
instance of: scholarly article
title: Embedding equality constraints of optimization problems into a quantum annealer
zbMATH Open document ID: 1461.90087
author: Hristo N. Djidjev
author: Tomáš Vyskočil
published in: Algorithms
publication date: 2019-07-08T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 81P68
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7077452
zbMATH Keywords: quantum annealing
zbMATH Keywords: D-wave
zbMATH Keywords: QUBO
zbMATH Keywords: constrained optimization
zbMATH Keywords: mixed-integer programming
describes a project that uses: AMPL
describes a project that uses: MathSAT5
describes a project that uses: ALGENCAN
describes a project that uses: Gurobi
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a12040077
OpenAlex ID: W2938689170
cites work: Q4198056
cites work: Computationally Related Problems
cites work: Graph partitioning
cites work: The MathSAT5 SMT Solver
cites work: Q3151174
cites work: Asymptotic Analysis for Penalty and Barrier Methods in Convex and Linear Programming
cites work: Practical Augmented Lagrangian Methods for Constrained Optimization
cites work: The unconstrained binary quadratic programming problem: a survey
cites work: Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
cites work: Q3104215
cites work: Adiabatic quantum programming: minor embedding with hard faults
cites work: Fast clique minor generation in Chimera qubit connectivity graphs
cites work: A case study in programming a quantum annealer for hard operational planning problems
cites work: Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
cites work: Optimizing adiabatic quantum program compilation using a graph-theoretic framework
cites work: Efficiently embedding QUBO problems on adiabatic quantum computers
DOI: 10.3390/A12040077
Recommended article: Integer programming techniques for minor-embedding in quantum annealers
Recommended article: Optimization and quantum annealing
Recommended article: Quantum annealing and related optimization methods
Recommended article: A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
Recommended article: Garden optimization problems for benchmarking quantum annealers
Recommended article: Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
Recommended article: Solving SAT and MaxSAT with a quantum annealer: foundations and a preliminary report
Recommended article: Convergence theorems for quantum annealing
Recommended article: Quantum Annealing of Hard Problems
Recommended article: Quantum annealing learning search for solving QUBO problems
description: scientific article; zbMATH DE number 7077452