Research Papers

Selected research papers published by 1QBit's team and collaborators.

Combinatorial Optimization on Gate Model Quantum Computers: A Survey

By Ehsan Zahedinejad & Arman Zaribadiyan

The advent of quantum computing processors with possibility to scale beyond experimental capacities magnifies the importance of studying their applications. Combinatorial optimization problems can be one of the promising applications of these new devices. These problems are recurrent in industrial applications and they are in general difficult for classical computing hardware. In this work, we provide a survey of the approaches to solving different types of combinatorial optimization problems, in particular quadratic unconstrained binary optimization (QUBO) problems on a gate model quantum computer. We focus mainly on four different approaches including digitizing the adiabatic quantum computing, global quantum optimization algorithms, the quantum algorithms that
approximate the ground state of a general QUBO problem, and quantum sampling. We also discuss the quantum algorithms that are custom designed to solve certain types of QUBO problems.

PDF    ARXIV PREPRINT

Combinatorial Optimization by Decomposition on Hybrid CPU–non-CPU Solver Architectures

By Ali Narimani, Seyed Saeed Rezaei, & Arman Zaribadiyan 

The advent of special-purpose hardware such as FPGA- or ASIC-based annealers and quantum processors has shown potential in solving certain families of complex combinatorial optimization problems more efficiently than conventional CPUs. We show that to address an industrial optimization problem, a hybrid architecture of CPUs and non-CPU devices is inevitable. In this paper, we propose problem decomposition as an effective method for designing a hybrid CPU–non-CPU optimization problem solver. We introduce the required algorithmic elements for making problem decomposition a viable approach in meeting real-world constraints such as communication time and the potential higher cost of using non-CPU hardware. We then turn to the well-known maximum clique problem, and propose a new decomposition method for this problem. Our method enables us to solve the maximum clique problem on very large graphs using non-CPU hardware that is considerably smaller in size than the graph. As an example, we demonstrate that the maximum clique problem on the com-Amazon graph, with 334,863 vertices and 925,872 edges, can be solved using a single problem embedding on fully connected hardware with at least 21 nodes, such as the D-Wave 2000Q. We also show that our proposed problem decomposition approach can improve the runtime of two of the best-known classical algorithms for large, sparse graphs, namely PMC and BBMCSP, by orders of magnitude. In the light of our study, we believe that even new non-CPU hardware that is small in size could become competitive with CPUs if it could be either mass produced and highly parallelized, or able to provide high-quality solutions to specific problems significantly faster than CPUs.

PDF    ARXIV PREPRINT

Effective Optimization Using Sample Persistence: A Case Study on Quantum Annealers and Various Monte Carlo Optimization Methods

By Hamed Karimi, Gili Rosenberg, & Helmut G. Katzgraber

We present and apply a general-purpose, multi-start algorithm for improving the performance of low-energy samplers used for solving optimization problems. The algorithm iteratively fixes the value of a large portion of the variables to values that have a high probability of being optimal. The resulting problems are smaller and less connected, and samplers tend to give better low-energy samples for these problems. The algorithm is trivially parallelizable, since each start in the multi-start algorithm is independent, and could be applied to any heuristic solver that can be run multiple times to give a sample. We present results for several classes of hard problems solved using simulated annealing, path-integral quantum Monte Carlo, parallel tempering with isoenergetic cluster moves, and a quantum annealer, and show that the success metrics as well as the scaling are improved substantially. When combined with this algorithm, the quantum annealer’s scaling was substantially improved for native Chimera graph problems. In addition, with this algorithm the scaling of the time to solution of the quantum annealer is comparable to the Hamze–de Freitas–Selby algorithm on the weak-strong cluster problems introduced by Boixo et al. Parallel tempering with isoenergetic cluster moves was able to consistently solve 3D spin glass problems with 8000 variables when combined with our method, whereas without our method it could not solve any.

Presented at:   Adiabatic Quantum Computing Conference 2017   (AQC 2017)

PDF    ARXIV PREPRINT

Practical Integer-to-Binary Mapping for Quantum Annealers

By Sahar Karimi & Pooya Ronagh

Recent advancements in quantum annealing hardware and numerous studies in this area suggests that quantum annealers have the potential to be effective in solving unconstrained binary quadratic programming problems. Naturally, one may desire to expand the application domain of these machines to problems with general discrete variables. In this paper, we explore the possibility of employing quantum annealers to solve unconstrained quadratic programming problems over a bounded integer domain. We present an approach for encoding integer variables into binary ones, thereby representing unconstrained integer quadratic programming problems as unconstrained binary quadratic programming problems. To respect some of the limitations of the currently developed quantum annealers, we propose an integer encoding, named bounded-coefficient encoding, in which we limit the size of the coefficients that appear in the encoding. Furthermore, we propose an algorithm for finding the upper bound on the coefficients of the encoding using the precision of the machine and the coefficients of the original integer problem. Finally, we experimentally show that this approach is far more resilient to the noise of the quantum annealers compared to traditional approaches for the encoding of integers in base two.

Presented at:  SIAM Conference on Optimization 2017 
PDF    ARXIV PREPRINT

Free-Energy-based Reinforcement Learning Using a Quantum Processor

By Anna Levit, Daniel Crawford, Navid Ghadermarzy, Jaspreet S. Oberoi,
Ehsan Zahedinejad, & Pooya Ronagh

Recent theoretical and experimental results suggest the possibility of using current and near-future quantum hardware in challenging sampling tasks. In this paper, we introduce free-energy-based reinforcement learning (FERL) as an application of quantum hardware. We propose a method for processing a quantum annealer’s measured qubit spin configurations in approximating the free energy of a quantum Boltzmann machine (QBM). We then apply this method to perform reinforcement learning on the grid-world problem using the D-Wave 2000Q quantum annealer. The experimental results show that our technique is a promising method for harnessing the power of quantum sampling in reinforcement learning tasks.

Presented at: Theory of Quantum Computation, Communication and Cryptography TCQ 2017

PDF     arXiv preprint

Reinforcement Learning Using Quantum Boltzmann Machines

By Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, & Pooya Ronagh

We investigate whether quantum annealers with select chip layouts can outperform classical computers in reinforcement learning tasks. We associate a transverse fi eld Ising spin Hamiltonian with a layout of qubits similar to that of a deep Boltzmann machine (DBM) and use simulated quantum annealing (SQA) to numerically simulate quantum sampling from this system. We design a reinforcement learning algorithm in which the set of visible nodes representing the states and actions of an optimal policy are the fi rst and last layers of the deep network. In absence of a transverse eld, our simulations show that DBMs train more effectively than restricted Boltzmann machines (RBM) with the same number of weights. Since sampling from Boltzmann distributions of a DBM is not classically feasible, this is evidence of advantage of a non-Turing sampling oracle. We then develop a framework for training the network as a quantum Boltzmann machine (QBM) in the presence of a signifi cant transverse field for reinforcement learning. This further improves the reinforcement learning method using DBMs.

Presented at: Theory of Quantum Computation, Communication and Cryptography TCQ 2017, and Tokyo Institute of Technology, Nanoscience and Quantum Physics Seminar 

PDF     arXiv preprint

A Subgradient Approach for Constrained Binary Optimization via Quantum Adiabatic Evolution

By Sahar Karimi & Pooya Ronagh

An earlier work proposes a method for solving the Lagrangian dual of a constrained binary quadratic programming problem via quantum adiabatic evolution using an outer approximation method. This should be an efficient prescription for solving the Lagrangian dual problem in the presence of an ideally noise-free quantum adiabatic system. However, current implementations of quantum annealing systems demand methods that are efficient at handling possible sources of noise. In this paper, we consider a subgradient method for finding an optimal primal-dual pair for the Lagrangian dual of a constrained binary polynomial programming problem. We then study the quadratic stable set (QSS) problem as a case study. We see that this method applied to the QSS problem can be viewed as an instance-dependent penalty-term approach that avoids large penalty coefficients. Finally, we report our experimental results of using the D-Wave 2X quantum annealer and conclude that our approach helps this quantum processor to succeed more often in solving these problems compared to the usual penalty-term approaches.

Presented at: Canadian Operational Research Society (CORS) 58th Annual Conference 2016 

PDF     arXiv preprint

Enhancing Quantum Annealing Performance for the Molecular Similarity Problem

By Maritza Hernandez & Maliheh Aramon

Quantum annealing is a promising technique which leverages quantum mechanics to solve hard optimization problems. Considerable progress has been made in the development of a physical quantum annealer, motivating the study of methods to enhance the efficiency of such a solver. In this work, we present a quantum annealing approach to measure similarity among molecular structures. Implementing real-world problems on a quantum annealer is challenging due to hardware limitations such as sparse connectivity, intrinsic control error, and limited precision. In order to overcome the limited connectivity, a problem must be reformulated using minor-embedding techniques. Using a real data set, we investigate the performance of a quantum annealer in solving the molecular similarity problem. We provide experimental evidence that common practices for embedding can be replaced by new alternatives which mitigate some of the hardware limitations and enhance its performance. Common practices for embedding include minimizing either the number of qubits or the chain length, and determining the strength of ferromagnetic couplers empirically. We show that current criteria for selecting an embedding do not improve the hardware’s performance for the molecular similarity problem. Furthermore, we use a theoretical approach to determine the strength of ferromagnetic couplers. Such an approach removes the computational burden of the current empirical approaches, and also results in hardware solutions that can benefit from simple local classical improvement. Although our results are limited to the problems considered here, they can be generalized to guide future benchmarking studies.

Journal reference:  Quantum Information Processing, 

PDF     arXiv preprint

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. This approach significantly increases the success rate and number of observations of the best known energy value in samples obtained from the quantum annealer, when compared with calling the quantum annealer without using it, even when using fewer annealing cycles. Use of the method results in a considerable improvement in success metrics even for problems with high-precision couplers and biases, which are more challenging for the quantum annealer to solve. The results are further enhanced by applying the method iteratively and combining it with classical pre-processing. We present results for both Chimera graph-structured problems and embedded problems from a real-world application.

Presented at: Adiabatic Quantum Computing Conference 2016 (AQC)
Journal reference: Quantum Information Processing – July 2017 

PDF    arXiv preprint

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.

Journal reference: Nature, Scientific Reports 7, Article number: 43048 (2017)

PDF     arXiv preprint

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. To alleviate this difficulty, we propose a systematic and deterministic embedding method, exploiting the structures of both the input graph of the specific problem and the quantum annealer. We focus on the specific case of the Cartesian product of two complete graphs, a regular structure that occurs in many problems. We divide the embedding problem by first embedding one of the factors of the Cartesian product in a repeatable pattern. The resulting simplified problem consists of the placement and connecting together of these copies to reach a valid solution. Aside from the obvious advantage of a systematic and deterministic approach with respect to speed and efficiency, the embeddings produced are easily scaled for larger processors and show desirable properties for the number of qubits used and the chain length distribution. To conclude, we briefly address the problem of circumventing inoperable qubits by presenting possible extensions of the method.

Journal reference:  Quantum Information Processing, 
Presented at: American Physical Society APS March Meeting 2016, Session F45: Adiabatic Quantum Computation and Quantum Annealing: Energy Landscapes, Speedup and Embedding APS March Meeting 2016, Volume 61, Number 2 

PDF     arXiv preprint

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. 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.

PDF     arXiv preprint

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. 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).

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. 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.

Journal reference: Quantum Information & Computation 16(11&12): 1029-1047 (2016)
Presented at: The Fields Institute for Research in Mathematical Sciences, Quantum Optimization Workshop 2014 

PDF     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

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.

Journal reference: IEEE Journal of Selected Topics in Signal Processing (JSTSP), Volume 10, Issue 6, 2016 and Proc. of the 8th Workshop on High Performance Computational Finance (WHPCF), p. 7, ACM, 2015 and The Journal of Investing, Fall 2016, Vol. 25, No. 3: pp. 81-87

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. 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.

Journal reference: Computational Optimization and Applications , Volume 65, Issue 3, pp 845–869

PDF     arXiv preprint

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. 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.

Presented at: Constraint Satisfaction Techniques for Planning and Scheduling 2016 (COPLAS) at The 26th International Conference on Automated Planning and Scheduling (ICAPS) and the Fourth Conference in Adiabatic Quantum Computing 2015 (AQC)    

PDF     arXiv preprint