Uncertain fate of fair sampling in quantum annealing
arXiv:1806.06081 · doi:10.1103/PhysRevA.100.030303
Abstract
Recently, it was demonstrated both theoretically and experimentally on the D-Wave quantum annealer that transverse-field quantum annealing does not find all ground states with equal probability. In particular, it was proposed that more complex driver Hamiltonians beyond transverse fields might mitigate this shortcoming. Here, we investigate the mechanisms of (un)fair sampling in quantum annealing. While higher-order terms can improve the sampling for selected small problems, we present multiple counterexamples where driver Hamiltonians that go beyond transverse fields do not remove the sampling bias. Using perturbation theory we explain why this is the case. In addition, we present large-scale quantum Monte Carlo simulations for spin glasses with known degeneracy in two space dimensions and demonstrate that the fair-sampling performance of quadratic driver terms is comparable to standard transverse-field drivers. Our results suggest that quantum annealing machines are not well suited for sampling applications, unless post-processing techniques to improve the sampling are applied.
arXiv comment6 pages, 5 figures
References in corpus (41)
- Quantum Annealing in the Transverse Ising Model
- QuTiP 2: A Python framework for the dynamics of open quantum systems
- 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
- Quantum Computation by Adiabatic Evolution
- Mathematical Foundation of Quantum Annealing
- Experimental signature of programmable quantum annealing
- Quantum Optimization of Fully-Connected Spin Glasses
- 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
- Optimized simulated annealing for Ising spin glasses
- 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
- Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- A deceptive step towards quantum speedup detection
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- MAX 2-SAT with up to 108 qubits
- Unraveling Quantum Annealers using Classical Hardness
- Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
- Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- Degeneracy, degree, and heavy tails in quantum annealing
- Programmable Superpositions of Ising Configurations
- Assessment of Quantum Annealing for the Construction of Satisfiability Filters
- Feeding the multitude: A polynomial-time algorithm to improve sampling
- Quantum Monte Carlo Annealing with Multi-Spin Dynamics
Cited by in corpus (31)
- Perspectives of quantum annealing: Methods and implementations
- Polymer Physics by Quantum Computing
- Rapid fair sampling of XY spin Hamiltonian with a laser simulator
- Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machine
- Fair Sampling by Simulated Annealing on Quantum Annealer
- Quantum neural networks to simulate many-body quantum systems
- High-quality Thermal Gibbs Sampling with Quantum Annealing Hardware
- Sampling on NISQ Devices: "Who's the Fairest One of All?"
- Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
- Testing a quantum annealer as a quantum thermal sampler
- Sampling Rare Conformational Transitions with a Quantum Computer
- Achieving fair sampling in quantum annealing
- Fair Sampling Error Analysis on NISQ Devices
- Fluctuation guided search in quantum annealing
- Error measurements for a quantum annealer using the one-dimensional Ising model with twisted boundaries
- Designing ground states of Hopfield networks for quantum state preparation
- Mixed-Integer Programming Using a Bosonic Quantum Computer
- 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
- A quantum algorithm to count weighted ground states of classical spin Hamiltonians
- Bifurcation-based quantum annealing with nested spins
- Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
- Analysis of a Programmable Quantum Annealer as a Random Number Generator
- Mapping State Transition Susceptibility in Quantum Annealing
- Posiform Planting: Generating QUBO Instances for Benchmarking
- 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
- Quantum annealing and condensed matter physics
- Reducing quantum annealing biases for solving the graph partitioning problem
- Boltzmann Sampling of Frustrated J1 - J2 Ising Models with Programmable Quantum Annealers