Quantum annealers are an emerging computational architecture that have the potential to address some challenging computational issues that will be left unresolved as we approach the end of the Moore's Law era of computing. D-Wave quantum annealers are designed to solve a challenging set of problems - quadratic unconstrained binary optimization problems. This makes them a natural fit for solving problems with binary or Boolean variables. Here, we explore the use of a quantum annealer to solve Boolean tensor factorization. The goal of Boolean tensor factorization is to represent a high-dimensional tensor filled with Boolean values as a product of Boolean matrices and a Boolean core tensor. We show that a particular Boolean tensor factorization problem (called Tucker-1 factorization) can be decomposed into a sequence of quadratic unconstrained binary optimization problems that can be solved with a D-Wave 2000Q quantum annealer. While quantum annealers specifically and quantum computers in general are at a fairly early stage in their development, they are currently capable of solving these Boolean tensor factorization problems. Our results show that for fairly small tensors, we are frequently able to obtain an accurate (sometimes exact) factorization using quantum annealing.
Quantum annealers are an emerging computational architecture that have the potential to address some challenging computational issues that will be left unresolved as we approach the end of the Moore's Law era of computing. D-Wave quantum annealers are designed to solve a challenging set of problems - quadratic unconstrained binary optimization problems. This makes them a natural fit for solving problems with binary or Boolean variables. Here, we explore the use of a quantum annealer to solve Boolean tensor factorization. The goal of Boolean tensor factorization is to represent a high-dimensional tensor filled with Boolean values as a product of Boolean matrices and a Boolean core tensor. We show that a particular Boolean tensor factorization problem (called Tucker-1 factorization) can be decomposed into a sequence of quadratic unconstrained binary optimization problems that can be solved with a D-Wave 2000Q quantum annealer. While quantum annealers specifically and quantum computers in general are at a fairly early stage in their development, they are currently capable of solving these Boolean tensor factorization problems. Our results show that for fairly small tensors, we are frequently able to obtain an accurate (sometimes exact) factorization using quantum annealing.
Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., [Formula: see text]) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor's with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.
To date, conventional computers have never been able to efficiently handle certain tasks, where the number of computation steps is likely to blow up as the problem size increases. As an emerging technology and new computing paradigm, quantum computing has a great potential to tackle those hard tasks efficiently. Among all the existing quantum computation models, quantum annealing has drawn significant attention in recent years due to the realization of the commercialized quantum annealer, sparking research interests in developing applications to solve problems that are intractable for classical computers.However, designing and implementing algorithms that manage to harness the enormous computation power from quantum annealer remains a challenging task. Generally, it requires mapping of the given optimization problem into quadratic unconstrained binary optimization(QUBO) problem and embedding the subsequent QUBO onto the physical architecture of quantum annealer. Additionally, practical quantum annealers are susceptible to errors leading to low probability of the correct solution.In this study, we focus on solving Boolean satisfiability (SAT) problem using quantum annealer while addressing practical limitations. We have proposed a mapping technique that maps SAT problem to QUBO, and we have further devised a tool flow that embeds the QUBO onto the architecture of a quantum annealing device. Additionally, We have optimized the proposed embedding flow to reduce run-time in addition to shortening the qubit chain length, leading to robust quantum annealing. To further improve the reliability of quantum annealing, we have also developed a post processing embedding technique that enlarges the energy gap between ground state and the first excited state. To demonstrate the effectiveness of proposed methods, we have conducted experiments on real quantum annealing devices manufactured by D-Wave Systems, showing compelling result of using quantum annealer to solve SAT problem.
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.
In this article we want to demonstrate the effectiveness of the new D-Wave quantum annealer, D-Wave 2000Q, in dealing with real world problems. In particular, it is shown how the quantum annealing process is able to find global optima even in the case of problems that do not directly involve binary variables. The problem addressed in this work is the following: taking a matrix V, find two matrices W and H such that the norm between V and the matrix product WH is as small as possible. The work is inspired by O'Malley's article [1], where the author proposed an algorithm to solve a problem very similar to ours, where however the matrix H was formed by only binary variables. In our case neither of the two matrices W or H is a binary matrix. In particular, the factorization foresees that the matrix W is composed of real numbers between 0 and 1 and that the sum of its rows is equal to 1. The QUBO problem associated with this type of factorization generates a potential composed of many local minima. We show that simple forward-annealing techniques are not sufficient to solve the problem. The new D-Wave 2000Q has introduced new solution refinement techniques, including reverse-annealing. Reverse-annealing allows to explore the configuration space starting from a point chosen by the user, for example a local minimum obtained with a precedent forward-annealing. In this article we propose an algorithm based on the reverse annealing technique (that we called adaptive reverse annealing) able to reach global minimum even in the case of QUBO problems where the classic forward annealing, or uncontrolled reverse annealing, can not reach satisfactory solutions.
Quantum annealing device has shown a great potential in solving discrete problems that are theoretically and empirically hard. Boolean Satisfiability (SAT) problem, determining if there is an assignment of variables that satisfies a given Boolean function, is the first proven NP-complete problem widely used in various domains. Here, we present a novel mapping of the SAT problem to the quadratic unconstrained binary optimization problem (QUBO), and further develop a tool flow embedding the proposed QUBO to the architecture of the commercialized quantum computer D-Wave. By leveraging electronic design automation techniques including synthesis, placement and routing, this is not only the first work providing the detail flow that embeds the QUBO, but also a technique scalable for real world applications and some hard SAT problems with over 6000 variables in QUBO. Based on our results, we discuss the challenges in solving SAT using the current generation of annealing device, and explore the problem solving capability of future quantum annealing computers.
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.