Quantum annealing is a method based on simulated annealing where temperature variations are replaced by quantum fluctuations that cause qubit state transitions. ISING problems and Quadratic Unconstrained Binary Optimization problems (QUBO) can be tackled by quantum annealing-based machines. We can link the interconnected qubits of the machine and the binaries of our model: qubits are binary variables and each pair of them linked by a coupler has a strong impact on the equality or the non-equality of the two binaries of the associated pair. Quantum annealing is based on the fact that any system tends to seek its minimum energy state. Starting from qubits in a state of superposition where all the solutions to the problem are fairly represented, the machine will apply a magnetic field by targeting the qubits and couplers in such a way as to make their value energetically favorable in the direction of optimization (minimization). For the coupled qubits, it is the quadratic products of the binary variables that are considered here and the physical system will make it energetically favorable for them to take (or not) the same values. To work on these machines based on quantum annealing in order to solve optimization problems with constraints, the latter must be relaxed while penalizing the Objective function. After presenting the case of the Max-Cut problem, we will look at such constrained problems.
Quantum annealing is a method based on simulated annealing where temperature variations are replaced by quantum fluctuations that cause qubit state transitions. ISING problems and Quadratic Unconstrained Binary Optimization problems (QUBO) can be tackled by quantum annealing-based machines. We can link the interconnected qubits of the machine and the binaries of our model: qubits are binary variables and each pair of them linked by a coupler has a strong impact on the equality or the non-equality of the two binaries of the associated pair. Quantum annealing is based on the fact that any system tends to seek its minimum energy state. Starting from qubits in a state of superposition where all the solutions to the problem are fairly represented, the machine will apply a magnetic field by targeting the qubits and couplers in such a way as to make their value energetically favorable in the direction of optimization (minimization). For the coupled qubits, it is the quadratic products of the binary variables that are considered here and the physical system will make it energetically favorable for them to take (or not) the same values. To work on these machines based on quantum annealing in order to solve optimization problems with constraints, the latter must be relaxed while penalizing the Objective function. After presenting the case of the Max-Cut problem, we will look at such constrained problems.
Quantum Annealing is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). Quantum computers such as the D-Wave systems are indeed implementing those ideas in hardware, as well as "quantum-inspired" devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. All those systems use the same modeling language: Quadratic Unconstrained Binary Optimization (QUBO). However, QUBO is a low-level language and for modeling combinatorial problems such as constraint satisfaction and constrained optimization problems, we need to introduce higher-level abstractions in order to define complex constraints.
Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.
Most quantum annealers, or Ising machines have the hardware limitations in its qubit size and thus the computable problem size is much limited. This paper proposes a novel classical-Ising hybrid annealing method which virtually extends the computable size of Ising machines based on a theoretical analysis. Given a quadratic unconstrained binary optimization (QUBO) model, the proposed method selects the cutting binary variable that is most likely to have the same value as the ground-state solution. Then, we recursively cut the QUBO model based on the cutting binary variable until we obtain sufficiently small-sized subQUBO models. Experimental evaluations demonstrate that the proposed hybrid annealing method can give much better quasi-ground-state solutions than state-of-the-art existing methods for large-sized QUBO models.
Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.
The quantum annealing devices, which encode the solution to a computational problem in the ground state of a quantum Hamiltonian, are implemented in D-Wave systems with more than 2,000 qubits. However, quantum annealing can solve only a classical combinatorial optimization problem such as an Ising model, or equivalently, a quadratic unconstrained binary optimization (QUBO) problem. In this paper, we formulate the QUBO model to solve elliptic problems with Dirichlet and Neumann boundary conditions using the finite element method. In this formulation, we develop the objective function of quadratic binary variables represented by qubits and the system finds the binary string combination minimizing the objective function globally. Based on the QUBO formulation, we introduce an iterative algorithm to solve the elliptic problems. We discuss the validation of the modeling on the D-Wave quantum annealing system.
Quantum annealers offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.