A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
arXiv:2105.03528 · doi:10.1038/s41534-024-00856-3
Abstract
We study the performance scaling of three quantum algorithms for combinatorial optimization: measurement-feedback coherent Ising machines (MFB-CIM), discrete adiabatic quantum computation (DAQC), and the Dürr-Hoyer algorithm for quantum minimum finding (DH-QMF) that is based on Grover's search. We use MaxCut problems as a reference for comparison, and time-to-solution (TTS) as a practical measure of performance for these optimization algorithms. For each algorithm, we analyze its performance in solving two types of MaxCut problems: weighted graph instances with randomly generated edge weights attaining 21 equidistant values from to ; and randomly generated Sherrington-Kirkpatrick (SK) spin glass instances. We empirically find a significant performance advantage for the studied MFB-CIM in comparison to the other two algorithms. We empirically observe a sub-exponential scaling for the median TTS for the MFB-CIM, in comparison to the almost exponential scaling for DAQC and the proven scaling for DH-QMF. We conclude that the MFB-CIM outperforms DAQC and DH-QMF in solving MaxCut problems.
28 pages, 22 figures; published in npj Quantum Information
References in corpus (32)
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- Barren plateaus in quantum neural network training landscapes
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- A Quantum Approximate Optimization Algorithm
- Quantum annealing with more than one hundred qubits
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Quantum Search by Local Adiabatic Evolution
- Connecting ansatz expressibility to gradient magnitudes and barren plateaus
- Network of Time-Multiplexed Optical Parametric Oscillators as a Coherent Ising Machine
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- ProjectQ: An Open Source Software Framework for Quantum Computing
- A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Large-scale Ising spin network based on degenerate optical parametric oscillators
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
- Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity
- Ultra-low-power second-order nonlinear optics on a chip
- Effects of Noisy Oracle on Search Algorithm Complexity
- Applying quantum algorithms to constraint satisfaction problems
- Characterizing local noise in QAOA circuits
- The effect of unitary noise on Grover's quantum search algorithm
- Noise effect on Grover algorithm
- Coherent Ising machines with error correction feedback
- Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machine
- A Quantum Model for Coherent Ising Machine: Stochastic Differential Equations with Replicator Dynamics
- Decoherence on Grover's quantum algorithm: perturbative approach
- Noise effects in the quantum search algorithm from the computational complexity point of view
- Grover search under localized dephasing
- Optimal working point in digitized quantum annealing