ABSTRACT Approximate block diagonalization is a problem of transforming a given symmetric matrix as close to block diagonal as possible by symmetric permutations of its rows and columns. This problem arises as a preprocessing stage of various scientific calculations and has been shown to be NP‐complete. In this paper, we consider solving this problem approximately using the D‐Wave Advantage quantum annealer. For this purpose, several steps are needed. First, we have to reformulate the problem as a quadratic unconstrained binary optimization (QUBO) problem. Second, the QUBO has to be embedded into the physical qubit network of the quantum annealer. Third, and optionally, reverse annealing for improving the solution can be applied. We propose two QUBO formulations and four embedding strategies for the problem and discuss their advantages and disadvantages. Through numerical experiments, it is shown that the combination of domain‐wall encoding and D‐Wave's automatic embedding is the most efficient in terms of usage of physical qubits, while the combination of one‐hot encoding and automatic embedding is superior in terms of the probability of obtaining a feasible solution. It is also shown that reverse annealing is effective in improving the solution for medium‐sized problems.
ABSTRACT Approximate block diagonalization is a problem of transforming a given symmetric matrix as close to block diagonal as possible by symmetric permutations of its rows and columns. This problem arises as a preprocessing stage of various scientific calculations and has been shown to be NP‐complete. In this paper, we consider solving this problem approximately using the D‐Wave Advantage quantum annealer. For this purpose, several steps are needed. First, we have to reformulate the problem as a quadratic unconstrained binary optimization (QUBO) problem. Second, the QUBO has to be embedded into the physical qubit network of the quantum annealer. Third, and optionally, reverse annealing for improving the solution can be applied. We propose two QUBO formulations and four embedding strategies for the problem and discuss their advantages and disadvantages. Through numerical experiments, it is shown that the combination of domain‐wall encoding and D‐Wave's automatic embedding is the most efficient in terms of usage of physical qubits, while the combination of one‐hot encoding and automatic embedding is superior in terms of the probability of obtaining a feasible solution. It is also shown that reverse annealing is effective in improving the solution for medium‐sized problems.
We consider the problem of transforming a given symmetric matrix into a nearly block diagonal form by permutation of its rows and columns. Such a transformation is useful as preconditioning to accelerate the convergence of an eigenvalue solver, but the problem of finding an optimal permutation that maximizes the Frobenius norms of the diagonal blocks is NP-complete. We formulate this problem as QUBO (Quadratic Unconstrained Binary Optimization) and solve it using D-Wave Advantage quantum annealing machine. Experimental results on small problems show that the true minimum can be obtained with high probability. We also discuss how to improve the mapping of the problem onto the physical qubit network to increase the size of the problems that can be solved.
In this paper we provide the quantum version of the Convex Non-negative Matrix Factorization algorithm (Convex-NMF) by using the D-wave quantum annealer. More precisely, we use D-wave 2000Q to find the low rank approximation of a fixed real-valued matrixXby the product of two non-negative matrices factorsWandGsuch that the Frobenius norm of the differenceX- XWG is minimized. In order to solve this optimization problem we proceed in two steps. In the first step we transform the global real optimization problem depending onW,Ginto two quadratic unconstrained binary optimization problems (QUBO) depending onWandGrespectively. In the second step we use an alternative strategy between the two QUBO problems corresponding toWandGto find the global solution. The running of these two QUBO problems on D-wave 2000Q need to use an embedding to the chimera graph of D-wave 2000Q, this embedding is limited by the number of qubits of D-wave 2000Q. We perform a study on the maximum number of real data to be used by our approach onD-wave 2000Q. The proposed study is based on the number of qubits used to represent each real variable. We also tested our approach on D-Wave 2000Q with several randomly generated data sets to prove that our approach is faster than the classical approach and also to prove that it gets the best results.
Abstract Quantum annealing is a type of analog computation that aims to use quantum mechanical fluctuations in search of optimal solutions of QUBO (quadratic unconstrained binary optimization) or, equivalently, Ising problems. Since NP-hard problems can in general be mapped to Ising and QUBO formulations, the quantum annealing paradigm has the potential to help solve various NP-hard problems. Current quantum annealers, such as those manufactured by D-Wave Systems, Inc. have various practical limitations including the size (number of qubits) of the problem that can be solved, the qubit connectivity, and error due to the environment or system calibration, which can reduce the quality of the solutions. Typically, for an arbitrary problem instance, the corresponding QUBO (or Ising) structure will not natively embed onto the available qubit architecture on the quantum chip. Thus, in these cases, a minor embedding of the problem structure onto the device is necessary. However, minor embeddings on these devices do not always make use of the full sparse chip hardware graph, and a large portion of the available qubits stay unused during quantum annealing. In this work, we embed a disjoint random QUBO on the unused parts of the chip alongside the QUBO to be solved, which acts as an indicator of the solution quality of the device over time. Using experiments on three different D-Wave quantum annealers, we demonstrate that (i) long term trends in solution quality exist on the D-Wave device, and (ii) the unused qubits can be used to measure the current level of noise of the quantum system.
Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Quantum annealing algorithms were introduced to solve combinatorial optimization problems by taking advantage of quantum fluctuations to escape local minima in complex energy landscapes typical of NP - hard problems. In this work, we propose using quantum annealing for the theory of cuts, a field of paramount importance in theoretical computer science. We have proposed a method to formulate the Minimum Multicut Problem into the QUBO representation, and the technical difficulties faced when embedding and submitting a problem to the quantum annealer processor. We show two constructions of the quadratic unconstrained binary optimization functions for the Minimum Multicut Problem and we review several tradeoffs between the two mappings and provide numerical scaling analysis results from several classical approaches. Furthermore, we discuss some of the expected challenges and tradeoffs in the implementation of our mapping in the current generation of D-Wave machines.