The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
arXiv:1703.00622 · doi:10.1088/2058-9565/aa7877
Abstract
In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully-crafted gadget-based problems whose logical structure has typically a planar topology. Recent experiments on these gadget problems using a commercially-available quantum annealer have demonstrated an impressive performance over a selection of commonly-used classical optimization heuristics. Here we show that efficient classical optimization techniques, such as minimum-weight perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly-used benchmark problems based on planar logical topologies.
arXiv comment5 pages, 2 figures
References in corpus (12)
- Quantum Annealing in the Transverse Ising Model
- Quantum annealing with more than one hundred qubits
- Defining and detecting quantum speedup
- Architectural considerations in the design of a superconducting quantum annealing processor
- What is the Computational Value of Finite Range Tunneling?
- Quantum Optimization of Fully-Connected Spin Glasses
- Probing for quantum speedup in spin glass problems with planted solutions
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Practical engineering of hard spin-glass instances
Cited by in corpus (23)
- Quantum Computing in the NISQ era and beyond
- Perspectives of quantum annealing: Methods and implementations
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Nonnegative/binary matrix factorization with a D-Wave quantum annealer
- A deceptive step towards quantum speedup detection
- Network Community Detection On Small Quantum Computers
- Uncertain fate of fair sampling in quantum annealing
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Scaling overhead of embedding optimization problems in quantum annealing
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Scaling Advantage in Approximate Optimization with Quantum Annealing
- Evaluating Ising Processing Units with Integer Programming
- Fair sampling of ground-state configurations of binary optimization problems
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Initial State Encoding via Reverse Quantum Annealing and h-gain Features
- A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
- Verifying the output of quantum optimizers with ground-state energy lower bounds
- Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
- Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
- Absence of small-world effects at the quantum level and stability of the quantum critical point
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking