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…

read more

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…

read more

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…

read more

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…

read more

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…

read more

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…

read more

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…

read more

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…

read more

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…

read more