Boosting quantum annealer performance via sample persistence
arXiv:1606.07797 · doi:10.1007/s11128-017-1615-x
Abstract
We propose a novel method for reducing the number of variables in quadratic unconstrained binary optimization problems, using a quantum annealer (or any sampler) to fix the value of a large portion of the variables to values that have a high probability of being optimal. The resulting problems are usually much easier for the quantum annealer to solve, due to their being smaller and consisting of disconnected components. This approach significantly increases the success rate and number of observations of the best known energy value in samples obtained from the quantum annealer, when compared with calling the quantum annealer without using it, even when using fewer annealing cycles. Use of the method results in a considerable improvement in success metrics even for problems with high-precision couplers and biases, which are more challenging for the quantum annealer to solve. The results are further enhanced by applying the method iteratively and combining it with classical pre-processing. We present results for both Chimera graph-structured problems and embedded problems from a real-world application.
References in corpus (23)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- 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?
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Error corrected quantum annealing with hundreds of qubits
- Quantum versus Classical Annealing of Ising Spin Glasses
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Probing for quantum speedup in spin glass problems with planted solutions
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- Quantum annealing correction for random Ising problems
- Quantum Annealing Correction with Minor Embedding
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Performance of two different quantum annealing correction codes
- Error correction for encoded quantum annealing
- From local to global ground states in Ising spin glasses
- Backbone structure of the Edwards-Anderson spin-glass model
Cited by in corpus (16)
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Temperature scaling law for quantum annealing optimizers
- Network Community Detection On Small Quantum Computers
- Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
- Hybrid Quantum Annealing via Molecular Dynamics
- Physics-Inspired Heuristics for Soft MIMO Detection in 5G New Radio and Beyond
- Towards Hybrid Classical-Quantum Computation Structures in Wirelessly-Networked Systems
- Quantum Annealing for Jet Clustering with Thrust
- A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
- Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer
- Modernizing Quantum Annealing II: Genetic algorithms with the Inference Primitive Formalism
- Dynamical process of a bit-width reduced Ising model with simulated annealing
- Advantages of fixing spins in quantum annealing
- Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling
- Improving the efficiency of quantum annealing with controlled diagonal catalysts
- Frustration-enhanced quantum annealing correction models with additional inter-replica interactions