A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing

DOI10.1142/S0219749919500424zbMATH Open1430.81019arXiv1803.04340OpenAlexW3100218203WikidataQ127148148 ScholiaQ127148148MaRDI QIDQ5207191FDOQ5207191

Authors: Alastair A. Abbott, Michael J. Dinneen, Richard Hua, Cristian S. Calude 

Publication date: 8 January 2020

Published in: International Journal of Quantum Information (Search for Journal in Brave)

Abstract: Despite rapid recent progress towards the development of quantum computers capable of providing computational advantages over classical computers, it seems likely that such computers will, initially at least, be required to run in a hybrid quantum-classical regime. This realisation has led to interest in hybrid quantum-classical algorithms allowing, for example, quantum computers to solve large problems despite having very limited numbers of qubits. Here we propose a hybrid paradigm for quantum annealers with the goal of mitigating a different limitation of such devices: the need to embed problem instances within the (often highly restricted) connectivity graph of the annealer. This embedding process can be costly to perform and may destroy any computational speedup. In order to solve many practical problems, it is moreover necessary to perform many, often related, such embeddings. We will show how, for such problems, a raw speedup that is negated by the embedding time can nonetheless be exploited to give a real speedup. As a proof-of-concept example we present an in-depth case study of a simple problem based on the maximum weight independent set problem. Although we do not observe a quantum speedup experimentally, the advantage of the hybrid approach is robustly verified, showing how a potential quantum speedup may be exploited and encouraging further efforts to apply the approach to problems of more practical interest.

Full work available at URL: https://arxiv.org/abs/1803.04340

Recommendations

• Efficiently embedding QUBO problems on adiabatic quantum computers
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Embedding equality constraints of optimization problems into a quantum annealer
• A case study in programming a quantum annealer for hard operational planning problems
• Quantum annealing learning search for solving QUBO problems

zbMATH Keywords

graph embeddingquantum annealingquantum speeduphybrid quantum computing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Recent examples in the theory of partition graphs
• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
• A study of heuristic guesses for adiabatic quantum computation
• Dynamic graph models
• Statistical mechanics, three-dimensionality and NP-completeness
• BQP and the polynomial hierarchy
• Unifying tree decompositions for reasoning in graphical models
• Quantum versus classical annealing of Ising spin glasses
• Boosting quantum annealer performance via sample persistence
• A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
• The theory of variational hybrid quantum-classical algorithms
• Solving NP-Complete Problems with Quantum Search

Cited In (10)

• Quantum solutions for densest \(k\)-subgraph problems
• Efficiency of quantum vs. classical annealing in nonconvex learning problems
• Embedding equality constraints of optimization problems into a quantum annealer
• Quantum k-community detection: algorithm proposals and cross-architectural evaluation
• A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
• A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
• Boosting quantum annealer performance via sample persistence
• A copositive framework for analysis of hybrid Ising-classical algorithms
• A QUBO formulation for the tree containment problem
• The road to quantum computational supremacy

Uses Software

• SageMath
• Python

This page was built for publication: A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207191)