Computational speedups using small quantum devices

Abstract

Suppose we have a small quantum computer with only M qubits. Can such a device genuinely speed up certain algorithms, even when the problem size is much larger than M? Here we answer this question to the affirmative. We present a hybrid quantum-classical algorithm to solve 3SAT problems involving n>>M variables that significantly speeds up its fully classical counterpart. This question may be relevant in view of the current quest to build small quantum computers.

arXiv comment5+12 pages

References in corpus (2)

• Quantum Computing in the NISQ era and beyond
• Trading classical and quantum computational resources

Cited by in corpus (22)

• Optimizing Quantum Error Correction Codes with Reinforcement Learning
• Fast quantum circuit cutting with randomized measurements
• Network Community Detection On Small Quantum Computers
• Quantum advantage and noise reduction in distributed quantum computing
• Predicting quantum advantage by quantum walk with convolutional neural networks
• Experimental Simulation of Larger Quantum Circuits with Fewer Superconducting Qubits
• Community Detection Across Emerging Quantum Architectures
• Quantum circuit compilation and hybrid computation using Pauli-based computation
• Experimental demonstration of quantum learning speed-up with classical input data
• A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
• Hybrid divide-and-conquer approach for tree search algorithms
• Cutting a Wire with Non-Maximally Entangled States
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Large-scale Quantum Approximate Optimization via Divide-and-Conquer
• Joint Wire Cutting with Non-Maximally Entangled States
• Tangible reduction in learning sample complexity with large classical samples and small quantum system
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Anticipative measurements in hybrid quantum-classical computation
• Tabu-driven Quantum Neighborhood Samplers
• Synergic quantum generative machine learning
• Experimental kernel-based quantum machine learning in finite feature space
• Circuit connectivity boosts by quantum-classical-quantum interfaces