A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles

DOI10.1063/1.5119235MaRDI QIDQ5218804zbMATH OpenOpenAlexWikidataFDO

Authors Yimin Ge, Vedran Dunjko

Publication date 5 March 2020

Published in Journal of Mathematical Physics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30) Quantum control (81Q93)

Abstract: Recent works have shown that quantum computers can polynomially speed up certain SAT-solving algorithms even when the number of available qubits is significantly smaller than the number of variables. Here we generalise this approach. We present a framework for hybrid quantum-classical algorithms which utilise quantum computers significantly smaller than the problem size. Given an arbitrarily small ratio of the quantum computer to the instance size, we achieve polynomial speedups for classical divide-and-conquer algorithms, provided that certain criteria on the time- and space-efficiency are met. We demonstrate how this approach can be used to enhance Eppstein's algorithm for the cubic Hamiltonian cycle problem, and achieve a polynomial speedup for any ratio of the number of qubits to the size of the graph.

Recommendations

• A Quantum Algorithm for Finding a Hamilton Circuit
• An alternative adiabatic quantum algorithm for the Hamiltonian cycle problem
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• scientific article; zbMATH DE number 1285153
• A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing

Cites work

• scientific article; zbMATH DE number 3705907 (Why is no real title available?)
• scientific article; zbMATH DE number 6313121 (Why is no real title available?)
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A full derandomization of Schöning's \(k\)-\textsc{SAT} algorithm
• Faster ground state preparation and high-precision ground energy estimation with fewer qubits
• Quantum-walk speedup of backtracking algorithms
• Reversible space equals deterministic space
• The Traveling Salesman Problem for Cubic Graphs
• Universal Quantum Simulators

Cited in

(2)

• Using small-scale quantum devices to solve algebraic equations
• Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm

This page was built for publication: A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles

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