Exact sampling hardness of Ising spin models
arXiv:1701.03167 · doi:10.1103/PhysRevA.96.032324
Abstract
We study the complexity of classically sampling from the output distribution of an Ising spin model, which can be implemented naturally in a variety of atomic, molecular, and optical systems. In particular, we construct a specific example of an Ising Hamiltonian that, after time evolution starting from a trivial initial state, produces a particular output configuration with probability very nearly proportional to the square of the permanent of a matrix with arbitrary integer entries. In a similar spirit to BosonSampling, the ability to sample classically from the probability distribution induced by time evolution under this Hamiltonian would imply unlikely complexity theoretic consequences, suggesting that the dynamics of such a spin model cannot be efficiently simulated with a classical computer. Physical Ising spin systems capable of achieving problem-size instances (i.e. qubit numbers) large enough so that classical sampling of the output distribution is classically difficult in practice may be achievable in the near future. Unlike BosonSampling, our current results only imply hardness of exact classical sampling, leaving open the important question of whether a much stronger approximate-sampling hardness result holds in this context. As referenced in a recent paper of Bouland, Mancinska, and Zhang (A. Bouland, L. Mancinska, and X. Zhang, CCC 2016, pp. 28:1-28:33), our result completes the sampling hardness classification of two-qubit commuting Hamiltonians.
arXiv comment5 pages, 2 figures
References in corpus (19)
- Multi-particle entanglement of hot trapped ions
- Boson Sampling on a Photonic Chip
- Non-local propagation of correlations in long-range interacting quantum systems
- Demonstration of a small programmable quantum computer with atomic qubits
- Experimental Boson Sampling
- Experimental boson sampling in arbitrary integrated photonic circuits
- Photonic Boson Sampling in a Tunable Circuit
- Quantum spin dynamics and entanglement generation with hundreds of trapped ions
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Quantum Simulation of Spin Models on an Arbitrary Lattice with Trapped Ions
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- A Linear-Optical Proof that the Permanent is #P-Hard
- Non-equilibrium dynamics of Ising models with decoherence: an exact solution
- General rules for bosonic bunching in multimode interferometers
- Relaxation timescales and decay of correlations in a long-range interacting quantum simulator
- BosonSampling with Lost Photons
- Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states---The quantum-classical divide and computational-complexity transitions in linear optics
- Power of one non-clean qubit
- Spin models and boson sampling
Cited by in corpus (8)
- Dynamical phase transitions in sampling complexity
- Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
- Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
- On the sampling complexity of open quantum systems
- Entanglement and complexity of interacting qubits subject to asymmetric noise
- Boson Sampling for Generalized Bosons
- Quantum estimation bound of Gaussian matrix permanent
- Doubling Qubits in a Trapped-Ion System via Vibrational Dual-Rail Encoding