Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
arXiv:1606.07146 · doi:10.1103/PhysRevLett.118.070502
Abstract
We study the performance of the D-Wave 2X quantum annealing machine on systems with well-controlled ground-state degeneracy. While obtaining the ground state of a spin-glass benchmark instance represents a difficult task, the gold standard for any optimization algorithm or machine is to sample all solutions that minimize the Hamiltonian with more or less equal probability. Our results show that while naive transverse-field quantum annealing on the D-Wave 2X device can find the ground-state energy of the problems, it is not well suited in identifying all degenerate ground-state configurations associated to a particular instance. Even worse, some states are exponentially suppressed, in agreement with previous studies on toy model problems [New J. Phys. 11, 073021 (2009)]. These results suggest that more complex driving Hamiltonians are needed in future quantum annealing machines to ensure a fair sampling of the ground-state manifold.
6 pages, 5 figures, 1 table
References in corpus (4)
- Mathematical Foundation of Quantum Annealing
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Reexamining classical and quantum models for the D-Wave One processor
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
Cited by in corpus (50)
- Adiabatic Quantum Computing
- Perspectives of quantum annealing: Methods and implementations
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
- Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
- 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
- Rapid fair sampling of XY spin Hamiltonian with a laser simulator
- Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
- Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machine
- Practical Integer-to-Binary Mapping for Quantum Annealers
- Fair Sampling by Simulated Annealing on Quantum Annealer
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Sampling on NISQ Devices: "Who's the Fairest One of All?"
- Physics-Inspired Heuristics for Soft MIMO Detection in 5G New Radio and Beyond
- Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
- Advantages of Unfair Quantum Ground-State Sampling
- Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
- Programmable Superpositions of Ising Configurations
- Assessment of Quantum Annealing for the Construction of Satisfiability Filters
- Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer
- Possible Ergodic-nonergodic regions in the quantum Sherrington-Kirkpatrick spin glass model and quantum annealing
- Fair sampling of ground-state configurations of binary optimization problems
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Estimating the Density of States of Frustrated Spin Systems
- Fair Sampling Error Analysis on NISQ Devices
- Achieving fair sampling in quantum annealing
- Fluctuation guided search in quantum annealing
- Patch-planting spin-glass solution for benchmarking
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- Error measurements for a quantum annealer using the one-dimensional Ising model with twisted boundaries
- Feeding the multitude: A polynomial-time algorithm to improve sampling
- On the Question of Ergodicity in Quantum Spin Glass Phase and its role in Quantum Annealing
- Designing ground states of Hopfield networks for quantum state preparation
- Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
- Graph minor embedding can affect sampling degenerate ground states using quantum annealing
- Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
- Analysis of a Programmable Quantum Annealer as a Random Number Generator
- Spin networks on adiabatic quantum computer
- Mapping State Transition Susceptibility in Quantum Annealing
- Classical Criticality via Quantum Annealing
- Posiform Planting: Generating QUBO Instances for Benchmarking
- The Binomial Spin Glass
- Adiabatic evolution on a spatial-photonic Ising machine
- Computing Canonical Averages with Quantum and Classical Optimizers: Thermodynamic Reweighting for QUBO Models of Physical Systems
- Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
- Boltzmann Sampling of Frustrated J1 - J2 Ising Models with Programmable Quantum Annealers
- Counting with the quantum alternating operator ansatz
- Reducing quantum annealing biases for solving the graph partitioning problem