Scaling overhead of embedding optimization problems in quantum annealing
arXiv:2103.15991 · doi:10.1103/PRXQuantum.2.040322
Abstract
In order to treat all-to-all connected quadratic binary optimization problems (QUBO) with hardware quantum annealers, an embedding of the original problem is required due to the sparsity of the hardware's topology. Embedding fully-connected graphs - typically found in industrial applications - incurs a quadratic space overhead and thus a significant overhead in the time to solution. Here we investigate this embedding penalty of established planar embedding schemes such as minor embedding on a square lattice, minor embedding on a Chimera graph, and the Lechner-Hauke-Zoller scheme using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggest a polynomial time-to-solution overhead. Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers and could also serve as benchmark for improvements of the standard quantum annealing protocol.
arXiv comment10 pages, 10 figures, 1 table
References in corpus (39)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Perspectives of quantum annealing: Methods and implementations
- Mathematical Foundation of Quantum Annealing
- Architectural considerations in the design of a superconducting quantum annealing processor
- Experimental signature of programmable quantum annealing
- Quantum Optimization of Fully-Connected Spin Glasses
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Error corrected quantum annealing with hundreds of qubits
- Entanglement in a quantum annealing processor
- Quantum versus Classical Annealing of Ising 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
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Quantum annealing correction for random Ising problems
- Reexamining classical and quantum models for the D-Wave One processor
- Quantum Annealing Correction with Minor Embedding
- How "Quantum" is the D-Wave Machine?
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- A deceptive step towards quantum speedup detection
- Unraveling Quantum Annealers using Classical Hardness
- MAX 2-SAT with up to 108 qubits
- Rapid counter-diabatic sweeps in lattice gauge adiabatic quantum computing
- Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
- Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
- Error correction for encoded quantum annealing
- Variational optimization of the quantum annealing schedule for the Lechner-Hauke-Zoller scheme
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Performance enhancement of quantum annealing under the Lechner-Hauke-Zoller scheme by non-linear driving of the constraint term
- Computational Bottlenecks of Quantum Annealing
Cited by in corpus (21)
- Quantum Annealing for Industry Applications: Introduction and Review
- Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
- Digitized-Counterdiabatic Quantum Optimization
- Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
- Energy landscapes of combinatorial optimization in Ising machines
- Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
- Effectiveness of quantum annealing for continuous-variable optimization
- Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
- Phase transition of Frustrated Ising model via D-wave Quantum Annealing Machine
- 4-clique Network Minor Embedding for Quantum Annealers
- Quantum computing for genomics: conceptual challenges and practical perspectives
- Experimental Demonstrations of Native Implementation of Boolean Logic Hamiltonian in a Superconducting Quantum Annealer
- Speeding up Quantum Annealing with Engineered Dephasing
- A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem
- Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
- Mapping State Transition Susceptibility in Quantum Annealing
- Posiform Planting: Generating QUBO Instances for Benchmarking
- Quantum-inspired dynamical models on quantum and classical annealers
- Four-body coupler for superconducting qubits based on Josephson parametric oscillators
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
- Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm