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

DOI10.1063/1.5119235zbMATH Open1431.81044arXiv1907.01258OpenAlexW3100134366WikidataQ126334850 ScholiaQ126334850MaRDI QIDQ5218804FDOQ5218804

Authors: Yimin Ge, Vedran Dunjko 

Publication date: 5 March 2020

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

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.

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

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

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)

Cites Work

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

Cited In (2)

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

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)