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

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.

arXiv comment20+2 pages

References in corpus (10)

• Quantum Computing in the NISQ era and beyond
• Towards Practical Quantum Variational Algorithms
• Trading classical and quantum computational resources
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Fixed-point quantum search with an optimal number of queries
• Applying quantum algorithms to constraint satisfaction problems
• Introduction to Quantum Algorithms for Physics and Chemistry
• Computational speedups using small quantum devices
• Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
• An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure

Cited by in corpus (4)

• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Experimental Simulation of Larger Quantum Circuits with Fewer Superconducting Qubits
• Hybrid divide-and-conquer approach for tree search algorithms
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation