Applying quantum algorithms to constraint satisfaction problems

Abstract

Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over $10^5$ relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over $10^3$. However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.

arXiv comment30 pages, 22 figures, 12 tables; v2: minor changes following referee comments, uses journal style

References in corpus (43)

• Quantum Mechanics helps in searching for a needle in a haystack
• Surface codes: Towards practical large-scale quantum computation
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Quantum Simulation
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Strengths and Weaknesses of Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Quantum Algorithms Revisited
• High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions
• High-fidelity quantum logic gates using trapped-ion hyperfine qubits
• Elucidating Reaction Mechanisms on Quantum Computers
• Grover's quantum searching algorithm is optimal
• Defining and detecting quantum speedup
• Roads towards fault-tolerant universal quantum computation
• Surface code quantum computing by lattice surgery
• Toward the first quantum simulation with quantum speedup
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• On the relationship between continuous- and discrete-time quantum walk
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Magic state distillation with low overhead
• Realizing Rapid, High-Fidelity, Single-Shot Dispersive Readout of Superconducting Qubits
• Gate count estimates for performing quantum chemistry on small quantum computers
• Halving the cost of quantum addition
• Fast quantum logic gates with trapped-ion qubits
• Quantum circuits of T-depth one
• Quantum attacks on Bitcoin, and how to protect against them
• Novel constructions for the fault-tolerant Toffoli gate
• Quantum computation with realistic magic state factories
• Efficient synthesis of universal Repeat-Until-Success circuits
• A unified framework for magic state distillation and multi-qubit gate-synthesis with reduced resource cost
• A magic state's fidelity can be superior to the operations that created it
• Unifying gate-synthesis and magic state distillation
• Distilling one-qubit magic states into Toffoli states
• Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
• Robustness of error-suppressing entangling gates in cavity-coupled transmon qubits
• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• Going after the k-SAT Threshold
• Improved quantum backtracking algorithms using effective resistance estimates
• Magic State Distillation at Intermediate Size
• Super-Additivity and Entanglement Assistance in Quantum Reading

Cited by in corpus (33)

• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Exponential suppression of bit or phase flip errors with repetitive error correction
• Building a fault-tolerant quantum computer using concatenated cat codes
• Optimizing Quantum Error Correction Codes with Reinforcement Learning
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Low-overhead fault-tolerant quantum computing using long-range connectivity
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Early fault-tolerant simulations of the Hubbard model
• Error mitigation via verified phase estimation
• Quantum speedup of branch-and-bound algorithms
• Quantum enhancements for deep reinforcement learning in large spaces
• Low depth mechanisms for quantum optimization
• Towards large-scale quantum optimization solvers with few qubits
• Preparing Bethe Ansatz Eigenstates on a Quantum Computer
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• High-Fidelity Magic-State Preparation with a Biased-Noise Architecture
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Quantum-accelerated constraint programming
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• ERASER: Towards Adaptive Leakage Suppression for Fault-Tolerant Quantum Computing
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
• Hybrid divide-and-conquer approach for tree search algorithms
• A quantum procedure for map generation
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Quantifying Grover speed-ups beyond asymptotic analysis
• Conditions for a quadratic quantum speedup in nonlinear transforms with applications to energy contract pricing
• Practical implementation of a quantum backtracking algorithm
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz