Leveraging Artificial Intelligence to Advance Problem-Solving with Quantum Annealers
May 1, 2020
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 L0-norm problem of sparse recovery) through reducing the original problem of compressive sensing to Weighted-MAX-SAT instances, casting the L0-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.
PhdThesis
University of Maryland, Baltimore County
University of Maryland, Baltimore County
Downloads: 832 downloads