We show how to leverage quantum annealers (QAs) to better select candidates in greedy algorithms. Unlike conventional greedy algorithms that employ problem-specific heuristics for making locally optimal choices at each stage, we use QAs that sample from the ground state of a problem-dependent Hamiltonians at cryogenic temperatures and use retrieved samples to estimate the probability distribution of problem variables. More specifically, we look at each spin of the Ising model as a random variable and contract all problem variables whose corresponding uncertainties are negligible. Our empirical results on a D-Wave 2000Q quantum proces-sor demonstrate that the proposed quantum-assisted greedy algorithm (QAGA) scheme can find notably better solutions compared to the state-of-the-art techniques in the realm of quantum annealing.
Genetic algorithms, which mimic evolutionary processes to solve optimization problems, can be enhanced by using powerful semi-local search algorithms as mutation operators. Here, we introduce reverse quantum annealing, a class of quantum evolutions that can be used for performing families of quasi-local or quasi-nonlocal search starting from a classical state, as novel sources of mutations. Reverse annealing enables the development of genetic algorithms that use quantum fluctuation for mutations and classical mechanisms for the crossovers -- we refer to these as Quantum-Assisted Genetic Algorithms (QAGAs). We describe a QAGA and present experimental results using a D-Wave 2000Q quantum annealing processor. On a set of spin-glass inputs, standard (forward) quantum annealing finds good solutions very quickly but struggles to find global optima. In contrast, our QAGA proves effective at finding global optima for these inputs. This successful interplay of non-local classical and quantum fluctuations could provide a promising step toward practical applications of Noisy Intermediate-Scale Quantum (NISQ) devices for heuristic discrete optimization.
Routing and scheduling problems with time windows have long been important optimization problems for logistics and planning. Many classical heuristics and exact methods exist for such problems. However, there are no satisfactory methods for generating routes using quantum computing (QC), for mainly two reasons: inequality constraints, and the trade-off of feasibility and solution quality. Inequality constraints are typically handled using slack variables; and feasible solutions are found by filtering samples. These challenges are amplified in the presence of noise inherent in QC. Here, we propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer. By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution. We prove its convergence to a feasible solution, and illustrate its efficacy by solving the Fleet Sizing Vehicle Routing Problem with Time Windows (FSVRPTW). Our computational results show that this method obtains a lower objective value than the current state-of-the-art annealing approaches, both classical and hybrid, for the same amount of time using D-Wave Hybrid Solvers. We also show its robustness to noise on D-Wave Advantage2 through computational results as compared to the filtering approach on DWaveSampler, even when the filtering approach is given a longer annealing time, and a larger sample size.
Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to larger applications. We present a simple greedy method for solving larger-than-QPU lattice-structured Ising optimization problems. The method, implemented in the open source D-Wave Hybrid framework, uses a QPU coprocessor operating with generic parameters. Performance is evaluated for standard spin-glass problems on two lattice types with up to 11,616 spin variables, double the size that is directly programmable on any available QPU. The proposed method is shown to converge to low-energy solutions faster than an open source simulated annealing method that is either directly employed or substituted as a coprocessor in the hybrid method. Using newer Advantage QPUs in place of D-Wave 2000Q QPUs is shown to enhance convergence of the hybrid method to low energies and to achieve a lower final energy.
We show how to advance quantum information processing, specifically problem-solving with quantum annealers, in the realm of artificial intelligence. We introduce SAT++, as a novel quantum programming paradigm, that can compile classical algorithms (implemented in classical programming languages) and execute them on quantum annealers. Moreover, we introduce a post-quantum error correction method that can find samples with significantly lower energy values, compared to the state-of-the-art techniques in quantum annealing. We also demonstrate that performing post-quantum error correction methods can make results of quantum annealers reproducible?i.e., more robust behavior of quantum annealers, compared to recent software and hardware advancements in quantum annealing. In addition, we offer to conjugate both optimization and sampling aspects of the quantum annealers and introduce two AI hybrid approaches. In reinforcement quantum annealing (RQA) scheme, an intelligent agent interacts with a quantum annealer that plays the stochastic environment role of learning automata and searches in the space of Hamiltonians, rather than exploring the Hilbert space of a given Ising model. In the same manner, greedy quantum annealing (GQA) is a novel model that utilizes quantum annealers to better select candidates in greedy algorithms. We experimentally demonstrate that our proposed AI hybrid approaches outperform the best-known techniques in quantum annealing, specifically when problems require longer chains for forming virtual qubits with higher connectivity. Furthermore, we introduce the theory of ensemble quantum annealing (EQA) that generates multiple (distinct) Ising Hamiltonians whose ground states are all identical to a solution to the problem of interest. Our experimental results reveal that applying EQA can significantly boost the performance of the quantum annealers. After benchmarking the D-Wave 2000Q quantum processors, as a proof-of-concept, we apply our proposed models on two real-world problems. As our first study case, we use SAT++ for factoring pseudo-prime numbers on a D-Wave quantum processor that can jeopardize the security of modern public-key cryptography systems. As our second case of study, we address the NP-hard problem of compressive sensing (i.e., the
ℓ0-norm problem of sparse recovery) through reducing the original problem of compressive sensing to Weighted-MAX-SAT instances, casting the
ℓ0-norm problem of binary compressive sensing to quadratic unconstrained binary optimization (QUBO), and proposing to solve the original problems of binary compressive sensing and binary compressive sensing with matrix uncertainty on quantum annealers.
Quantum annealing is a form of quantum computing that exploits quantum effects to probabilistically solve a specific, NP-hard problem: finding the ground state of a classical, Ising-model Hamiltonian. Because physical quantum annealers are already available, there exists the pressing question of how to program such systems. That is, how can one map a computational problem into the coefficients of an Ising-model Hamiltonian for solution by quantum-annealing hardware? In this article, we address that question primarily from a practical standpoint. We survey extant software tools intended for programming D-wave annealing-based quantum processors and examine the programming model and solution technique promoted by each tool in an attempt to showcase the variety of contemporary approaches to solving computationally challenging problems on an existing annealing-based quantum computer.