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 Zaribafiyan The advent of quantum computing processors with the 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...

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

By Ali Narimani, Seyed Saeed Rezaei, & Arman Zaribafiyan 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...

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

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

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

Reinforcement Learning Using Quantum Boltzmann Machines

By Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, & Pooya Ronagh
Posted on December 17, 2016

We investigate whether quantum annealers with select chip layouts can outperform classical computers in reinforcement learning tasks. We associate a transverse field 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 first 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 significant transverse field for reinforcement learning. This further improves the reinforcement learning method using DBMs.

A Subgradient Approach for Constrained Binary Optimization via Quantum Adiabatic Evolution

By Sahar Karimi & Pooya Ronagh
Posted on January 25, 2017

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.

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.

Boosting Quantum Annealer Performance via Quantum Persistence

By Hamed Karimi & Gili Rosenberg
Posted on June 24, 2016

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.

Prime Factorization Using Quantum Annealing and Algebraic Geometry

By Raouf Dridi & Hedayat Alghassi
Posted on April 20, 2016

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.