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.
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.
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.
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.
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.
Density matrix electronic structure theory is used in many quantum chemistry methods to "alleviate" the computational cost that arises from directly using wave functions. Although density matrix based methods are computationally more efficient than wave function based methods, significant computational effort is involved. Because the Schrödinger equation needs to be solved as an eigenvalue problem, the time-to-solution scales cubically with the system size in mean-field type approaches such as Hartree-Fock and density functional theory and is solved as many times in order to reach charge or field self-consistency. We hereby propose and study a method to compute the density matrix by using a quadratic unconstrained binary optimization (QUBO) solver. This method could be useful to solve the problem with quantum computers and, more specifically, quantum annealers. Our proposed approach is based on a direct construction of the density matrix using a QUBO eigensolver. We explore the main parameters of the algorithm focusing on precision and efficiency. We show that, while direct construction of the density matrix using a QUBO formulation is possible, the efficiency and precision have room for improvement. Moreover, calculations performed with quantum annealing on D-Wave's new Advantage quantum computer are compared with results obtained with classical simulated annealing, further highlighting some problems of the proposed method. We also suggest alternative methods that could lead to a more efficient QUBO-based density matrix construction.
We present QuantumSync, the first quantum algorithm for solving a synchronization problem in the context of computer vision. In particular, we focus on permutation synchronization which involves solving a non-convex optimization problem in discrete variables. We start by formulating synchronization into a quadratic unconstrained binary optimization problem (QUBO). While such formulation respects the binary nature of the problem, ensuring that the result is a set of permutations requires extra care. Hence, we: (i) show how to insert permutation constraints into a QUBO problem and (ii) solve the constrained QUBO problem on the current generation of the adiabatic quantum computers D-Wave. Thanks to the quantum annealing, we guarantee global optimality with high probability while sampling the energy landscape to yield confidence estimates. Our proof-of-concepts realization on the adiabatic D-Wave computer demonstrates that quantum machines offer a promising way to solve the prevalent yet difficult synchronization problems.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.