Selected 1QBit™ Research

Research Papers

A Novel Graph-based Approach for Determining Molecular Similarity

By Maritza Hernandez, Arman Zaribafiyan, Maliheh Aramon, & Mohammad Naghibi
Posted on January 26, 2016

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. The context of our study is molecular similarity where the presence of noise might be due to regular errors in measuring molecular features. We develop a similarity measure and use it to predict the mutagenicity of a molecule. Our results indicate that the relaxed similarity measure, designed to accommodate the regular errors, yields a higher prediction accuracy than the measure that ignores the noise.

arXiv preprint

Homology Computation of Large Point Clouds Using Quantum Annealing

By Raouf Dridi & Hedayat Alghassi
Posted on December 23, 2015

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. Finally, it computes the homology of the Mayer-Vietoris complex in parallel. The novelty here is the use of clique covering which, compared to graph partitioning, substantially reduces the computational load assigned to each slave machine in the computing cluster. We describe two different clique covers and their quantum annealing formulation in the form of quadratic unconstrained binary optimization (QUBO).

arXiv preprint

Solving Constrained Quadratic Binary Problems via Quantum Adiabatic Evolution

By Pooya Ronagh, Brad Woods, & Ehsan Iranmanesh
Posted on September 16, 2015

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. In this paper, we give a method for solving the Lagrangian dual of a binary quadratic programming (BQP) problem in the presence of inequality constraints and employ this procedure within a branch-and-bound framework for constrained BQP (CBQP) problems.

arXiv preprint

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
Posted on August 22, 2015

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. The discrete multi-period portfolio optimization problem we solve is significantly harder than the continuous variable problem. We present insight into how results may be improved using suitable software enhancements, and why current quantum annealing technology limits the size of problem that can be successfully solved today. The formulation presented is specifically designed to be scalable, with the expectation that as quantum annealing technology improves, larger problems will be solvable using the same techniques.

arXiv preprint

Building an Iterative Heuristic Solver for a Quantum Annealer

By Gili Rosenberg, Mohammad Vazifeh, Brad Woods, & Eldad Haber
Posted on July 27, 2015

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. We present our algorithm, several variants, and the results for the optimization of standard QUBO problem instances from OR-Library of sizes 500 and 2500 as well as the Palubeckis instances of sizes 3000 to 7000. For practical use of the solver, we show the dependence of the time to best solution on the desired gap to the best known solution. In addition, we study the dependence of the gap and the time to best solution on the size of the problems solved by the underlying optimizer.

arXiv preprint

Quantum Annealing Implementation of
Job-Shop Scheduling

By Davide Venturelli, Dominic Marchand, & Galo Rojo
Posted on June 29, 2015

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. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.

arXiv preprint

White Papers

Cognitive Radio Optimization

By Arman Zaribafiyan & Jaspreet Oberoi
Posted on March 3, 2015

This research proposes a new approach for tackling cognitive radio asset allocation optimization problems. The cognitive radio optimization problem is generally an NP-hard mixed-integer programming problem due to its convoluted constraints. In contrast to conventional methods of using meta-heuristics and evolutionary algorithms, we implement non-linear constraints as polynomial penalty functions of binary variables and build a new objective function in a quadratic unconstrained binary optimization (QUBO) format.

White paper

Quantum Approaches to Graph Similarity

By Maritza Hernandez, Arman Zaribafiyan, & Mohammad Naghibi
Posted on January 22, 2015

At 1QBit™ we have developed a method of measuring similarity between graphs with the aid of a quantum annealer. In contrast to conventional methods, our method is capable of identifying the reasons for determining that two arbitrary graphs are similar, and can illustrate how much each component of each graph contributes to the decision. Moreover, the method can be used to mine similar patterns in a group of graphs by solving subset matching problems. To validate our approach we apply our method in a biochemical scenario, classifying the toxicity properties of a library of molecules based on their similarity to labelled molecules. Benchmarking results show that this general-purpose similarity determination method can perform as accurately as the best-known classical solution while providing higher sensitivity or higher specificity, and maintaining the same predictive accuracy.

White paper

Simulated Annealing via Quantum Annealing

By Pooya Ronagh
Posted on July 23, 2014

This paper describes a general method developed by 1QBit for solving continuous optimization problems inspired by different types of simulated annealing and genetic algorithms. This method works under the assumption of the existence of a computation model with a Turing reduction of problems to either quadratic unconstrained binary optimization (QUBO) problems or to an Ising spin problem. The paper presents an application of this method to a mixed-integer optimization problem. This will demonstrate an interesting method of representing a cardinality-constrained optimization problem using analytic expressions, and the ability of the method to solve such mixed-integer optimization problems.

White paper

Integer Optimization Toolbox

By Pooya Ronagh
Posted on August 13, 2013

We describe how the Integer Optimization Toolbox approaches the problem of minimization of a (low-degree) polynomial over an integer lattice. In theory, the method illustrated here can be used for arbitrarily large polynomials with a large enough quantum annealing oracle.

White paper