In this paper, we propose a new quantum version of the Balanced K-means algorithm in the D-wave quantum annealer. D-wave 2000Q quantum computer has been used by many papers in the last few years to solve optimization problems and for finding the global minimum of the balanced K-means optimization problem. However, in this paper, we modify the quadratic unconstrained binary optimization (QUBO) formulation of the Balanced K-means that has been proposed in a recent paper. Our modification is trained on different data sets: Iris, Wine and Breast Cancer. Also, we performed a comparative analysis between the two approaches (our approach and the paper's approach) to find the one that assigns the largest number of data to clusters and we also use the Davies-Bouldi metric to prove that our method gives the best clustering.
In this paper, we propose a new quantum version of the Balanced K-means algorithm in the D-wave quantum annealer. D-wave 2000Q quantum computer has been used by many papers in the last few years to solve optimization problems and for finding the global minimum of the balanced K-means optimization problem. However, in this paper, we modify the quadratic unconstrained binary optimization (QUBO) formulation of the Balanced K-means that has been proposed in a recent paper. Our modification is trained on different data sets: Iris, Wine and Breast Cancer. Also, we performed a comparative analysis between the two approaches (our approach and the paper's approach) to find the one that assigns the largest number of data to clusters and we also use the Davies-Bouldi metric to prove that our method gives the best clustering.
We present an algorithm for quantum-assisted cluster analysis (QACA) that makes use of the topological properties of a D-Wave 2000Q quantum processing unit (QPU). Clustering is a form of unsupervised machine learning, where instances are organized into groups whose members share similarities. The assignments are, in contrast to classification, not known a priori, but generated by the algorithm. We explain how the problem can be expressed as a quadratic unconstrained binary optimization (QUBO) problem, and show that the introduced quantum-assisted clustering algorithm is, regarding accuracy, equivalent to commonly used classical clustering algorithms. Quantum annealing algorithms belong to the class of metaheuristic tools, applicable for solving binary optimization problems. Hardware implementations of quantum annealing, such as the quantum annealing machines produced by D-Wave Systems, have been subject to multiple analyses in research, with the aim of characterizing the technology's usefulness for optimization, sampling, and clustering. Our first and foremost aim is to explain how to represent and solve parts of these problems with the help of the QPU, and not to prove supremacy over every existing classical clustering algorithm.
We present an algorithm for quantum-assisted cluster analysis (QACA) that makes use of the topological properties of a D-Wave 2000Q quantum processing unit (QPU). Clustering is a form of unsupervised machine learning, where instances are organized into groups whose members share similarities. The assignments are, in contrast to classification, not known a priori, but generated by the algorithm. We explain how the problem can be expressed as a quadratic unconstrained binary optimization (QUBO) problem, and show that the introduced quantum-assisted clustering algorithm is, regarding accuracy, equivalent to commonly used classical clustering algorithms. Quantum annealing algorithms belong to the class of metaheuristic tools, applicable for solving binary optimization problems. Hardware implementations of quantum annealing, such as the quantum annealing machines produced by D-Wave Systems [1], have been subject to multiple analyses in research, with the aim of characterizing the technology’s usefulness for optimization, sampling, and clustering [2–16, 38]. Our first and foremost aim is to explain how to represent and solve parts of these problems with the help of the QPU, and not to prove supremacy over every existing classical clustering algorithm.
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.
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.
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.
Vehicle Routing Problem is a well-known optimization issue, which has many extensions resulting from practical appliances. The problem is NP-hard, therefore it may be impossible to find an optimal solution for big instances, with traditional computation methods. Recent development of quantum technology, may be a response for this challenge, which however requires a different formulation of the model. The problem is then modeled using Quadratic Unconstrained Binary Optimization (QUBO) equations. Such model can be run using quantum annealers (QA), designed specifically for optimization purposes. This paper is a systematic survey of Vehicle Routing Problem models that are formulated using QUBO, to be solved on quantum computers. The main goal of the paper is to check research gaps in this subject, compare and explain different approaches of modeling various problem extensions with QUBO. The results obtained in reviewed papers will be presented and analyzed. Moreover, the theoretical basis for quantum computation will be presented, with focus on D-Wave company solutions.