RESEARCH PAPERS
Selected research papers published by 1QBit’s team and collaborators.
Boosting Quantum Annealer Performance via Quantum Persistence
By Hamed Karimi & Gili Rosenberg
We propose a novel method for reducing the number of variables in quadratic unconstrained binary optimization problems, using a quantum annealer to fix the value of a large portion of the variables to values that have a high probability of being optimal. The resulting problems are usually much easier for the quantum annealer to solve, due to their being smaller and consisting of disconnected components…
Prime Factorization Using Quantum Annealing and Algebraic Geometry
By Raouf Dridi & Hedayat Alghassi
We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Gröbner bases. We present a novel autonomous algorithm which combines the two approaches and leads to the factorization of all bi-primes up to just over 200 000, the largest number factored to date using a quantum processor. We also explain how Gröbner bases can be used to reduce the degree of Hamiltonians…
Systematic and Deterministic Graph-Minor Embedding for Cartesian Products of Graphs
By Arman Zaribafiyan, Dominic Marchand, & S. Saeed C. Rezaei
The limited connectivity of current and next-generation quantum annealers motivates the need for efficient graph-minor embedding methods. These methods allow non-native problems to be adapted to the target annealer’s architecture. The overhead of the widely used heuristic techniques is quickly proving to be a significant bottleneck for solving real-world applications…
A Novel Graph-based Approach for Determining Molecular Similarity
By Maritza Hernandez, Arman Zaribafiyan, Maliheh Aramon, & Mohammad Naghibi
In this paper, we tackle the problem of measuring similarity among graphs that represent real objects with noisy data. To account for noise, we relax the definition of similarity using the maximum weighted co-k-plex relaxation method, which allows dissimilarities among graphs up to a predetermined level. We then formulate the problem as a novel quadratic unconstrained binary optimization problem that can be solved by a quantum annealer…
Homology Computation of Large Point Clouds Using Quantum Annealing
By Raouf Dridi & Hedayat Alghassi
In this paper we present a quantum annealing algorithm for computation of homology of large point clouds. It is designed to work on resizable cloud computing platforms. The algorithm takes as input a witness complex K approximating the given point cloud. It uses quantum annealing to compute a clique cover of the 1-skeleton of K and then uses this cover to blow up K into a Mayer-Vietoris complex…
Solving Constrained Quadratic Binary Problems via Quantum Adiabatic Evolution
By Pooya Ronagh, Brad Woods, & Ehsan Iranmanesh
Quantum adiabatic evolution is perceived as useful for binary quadratic programming problems that are a priori unconstrained. For constrained problems, it is a common practice to relax linear equality constraints as penalty terms in the objective function. However, there has not yet been proposed a method for efficiently dealing with inequality constraints using the quantum adiabatic approach…
Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
By Gili Rosenberg, Poya Haghnegahdar, Phil Goddard, Peter Carr, Kesheng Wu, & Marcos López de Prado
We solve a multi-period portfolio optimization problem using D-Wave Systems’ quantum annealer. We derive a formulation of the problem, discuss several possible integer encoding schemes, and present numerical examples that show high success rates. The formulation incorporates transaction costs (including permanent and temporary market impact), and, significantly, the solution does not require the inversion of a covariance matrix…
Building an Iterative Heuristic Solver for a Quantum Annealer
By Gili Rosenberg, Mohammad Vazifeh, Brad Woods, & Eldad Haber
A quantum annealer heuristically minimizes quadratic unconstrained binary optimization (QUBO) problems, but is limited by the physical hardware in the size and density of the problems it can handle. We have developed a meta-heuristic solver that utilizes D-Wave Systems’ quantum annealer (or any other QUBO problem optimizer) to solve larger or denser problems, by iteratively solving subproblems, while keeping the rest of the variables fixed…
Quantum Annealing Implementation of Job-Shop Scheduling
By Davide Venturelli, Dominic Marchand, & Galo Rojo
A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor…