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 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 processor 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
We show how to leverage quantum annealers 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 quantum annealers that sample from the ground state of Ising Hamiltonians at cryogenic temperatures and use retrieved samples to estimate the probability distribution of problem variables. More specifically, we look at each spin in 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 processor revealed that the proposed quantum-assisted greedy algorithm (QAGA) can find remarkably better solutions, compared to the state-of-the-art techniques in the realm of quantum annealing.
We introduce the reinforcement quantum annealing (RQA) scheme in which an intelligent agent interacts with a quantum annealer that plays the stochastic environment role of learning automata and tries to iteratively find better Ising Hamiltonians for the given problem of interest. As a proof-of-concept, we propose a novel approach for reducing the NP-complete problem of Boolean satisfiability (SAT) to minimizing Ising Hamiltonians and show how to apply the RQA for increasing the probability of finding the global optimum. Our experimental results on two different benchmark SAT problems (namely factoring pseudo-prime numbers and random SAT with phase transitions), using a D-Wave 2000Q quantum processor, demonstrated that RQA finds notably better solutions with fewer samples, compared to 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.
We introduce the notion of reinforcement quantum annealing (RQA) scheme in which an intelligent agent searches in the space of Hamiltonians and interacts with a quantum annealer that plays the stochastic environment role of learning automata. At each iteration of RQA, after analyzing results (samples) from the previous iteration, the agent adjusts the penalty of unsatisfied constraints and re-casts the given problem to a new Ising Hamiltonian. As a proof-of-concept, we propose a novel approach for casting the problem of Boolean satisfiability (SAT) to Ising Hamiltonians and show how to apply the RQA for increasing the probability of finding the global optimum. Our experimental results on two different benchmark SAT problems (namely factoring pseudo-prime numbers and random SAT with phase transitions), using a D-Wave 2000Q quantum processor, demonstrated that RQA finds notably better solutions with fewer samples, compared to the best-known techniques in the realm of quantum annealing.
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.