Perils of Embedding for Sampling Problems

Abstract

Advances in techniques for thermal sampling in classical and quantum systems would deepen understanding of the underlying physics. Unfortunately, one often has to rely solely on inexact numerical simulation, due to the intractability of computing the partition function in many systems of interest. Emerging hardware, such as quantum annealers, provide novel tools for such investigations, but it is well known that studying general, non-native systems on such devices requires graph minor embedding, at the expense of introducing additional variables. The effect of embedding for sampling is more pronounced than for optimization; for optimization one is just concerned with the ground state physics, whereas for sampling one needs to consider states at all energies. We argue that as the system size or the embedding size grows, the chance of a sample being in the subspace of interest - the logical subspace - can be exponentially suppressed. Though the severity of this scaling can be lessened through favorable parameter choices, certain physical constraints (such as a fixed temperature and range of couplings) provide hard limits on what is currently feasible. Furthermore, we show that up to some practical and reasonable assumptions, any type of post-processing to project samples back into the logical subspace will bias the resulting statistics. We introduce a new such technique, based on resampling, that substantially outperforms majority vote, which is shown to fail quite dramatically at preserving distribution properties.

14+1 pages, 13 Figures. v2: updated to published version, including additional discussions throughout

References in corpus (17)

• An efficient, multiple range random walk algorithm to calculate the density of states
• Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram
• Spin-Glass Theory for Pedestrians
• Quantum Boltzmann Machine
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Quantum Optimization of Fully-Connected Spin Glasses
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Quantum Variational Autoencoder
• Searching for quantum speedup in quasistatic quantum annealers
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
• Dissipative quantum bifurcation machine: Quantum heating of coupled nonlinear oscillators
• Global warming: Temperature estimation in annealers
• Thermalization, freeze-out and noise: deciphering experimental quantum annealers
• Analog Errors in Ising Machines
• Estimating the Density of States of Frustrated Spin Systems

Cited by in corpus (12)

• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• High-quality Thermal Gibbs Sampling with Quantum Annealing Hardware
• Improved Boltzmann machines with error corrected quantum annealing
• Solving Larger Maximum Clique Problems Using Parallel Quantum Annealing
• Quantum-assisted associative adversarial network: Applying quantum annealing in deep learning
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Ferromagnetically shifting the power of pausing
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Advantage of pausing: parameter setting for quantum annealers
• Perils of Embedding for Quantum Sampling
• Graph minor embedding can affect sampling degenerate ground states using quantum annealing
• Boltzmann Sampling of Frustrated J1 - J2 Ising Models with Programmable Quantum Annealers