Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model

Abstract

We introduce an intermediate quantum computing model built from translation-invariant Ising-interacting spins. Despite being non-universal, the model cannot be classically efficiently simulated unless the polynomial hierarchy collapses. Equipped with the intrinsic single-instance-hardness property, a single fixed unitary evolution in our model is sufficient to produce classically intractable results, compared to several other models that rely on implementation of an ensemble of different unitaries (instances). We propose a feasible experimental scheme to implement our Hamiltonian model using cold atoms trapped in a square optical lattice. We formulate a procedure to certify the correct functioning of this quantum machine. The certification requires only a polynomial number of local measurements assuming measurement imperfections are sufficiently small.

Phys. Rev. Lett.(2017, in press), "one-instance" is replaced by "single-instance-hardness", references added, "Simulation with variation Distance Errors" in Supplemental Material is rewritten in a clearer way

References in corpus (17)

• Quantum Computing
• Quantum algorithm for solving linear systems of equations
• Measurement-based quantum computation with cluster states
• Single-Atom Resolved Fluorescence Imaging of an Atomic Mott Insulator
• Measurement-based quantum computation
• Boson Sampling on a Photonic Chip
• Probing the Superfluid to Mott Insulator Transition at the Single Atom Level
• Entanglement of atoms via cold controlled collisions
• Controlled Collisions for Multiparticle Entanglement of Optically Trapped Atoms
• Single-Spin Addressing in an Atomic Mott Insulator
• Efficient quantum state tomography
• Photonic Boson Sampling in a Tunable Circuit
• A fault-tolerant one-way quantum computer
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Ultra-precise holographic beam shaping for microscopic quantum control
• On the hardness of classically simulating the one clean qubit model

Cited by in corpus (67)

• Quantum Computational Supremacy
• Quantum advantage with shallow circuits
• Efficient Representation of Quantum Many-body States with Deep Neural Networks
• Rényi Entropies from Random Quenches in Atomic Hubbard and Spin Models
• Stochastic gradient descent for hybrid quantum-classical optimization
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Nearly optimal lattice simulation by product formulas
• Verification of quantum computation: An overview of existing approaches
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Theory of quantum system certification: a tutorial
• Quantum Neural Network States: A Brief Review of Methods and Applications
• Architectures for quantum simulation showing a quantum speedup
• On the Quantum versus Classical Learnability of Discrete Distributions
• Verification of Many-Qubit States
• Enhancing Generative Models via Quantum Correlations
• Temperature scaling law for quantum annealing optimizers
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Quantum approximate optimization with Gaussian boson sampling
• Anticoncentration theorems for schemes showing a quantum speedup
• From estimation of quantum probabilities to simulation of quantum circuits
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Dynamical phase transitions in sampling complexity
• Pattern recognition techniques for Boson Sampling validation
• Sample complexity of device-independently certified "quantum supremacy"
• Experimental quantum advantage with quantum coupon collector
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Quantum fluctuation theorem to benchmark quantum annealers
• Expressibility and trainability of parameterized analog quantum systems for machine learning applications
• Analog Errors in Ising Machines
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Accrediting outputs of noisy intermediate-scale quantum computing devices
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Learning shallow quantum circuits
• A quantum hamiltonian simulation benchmark
• Experimental demonstration of quantum advantage for one-way communication complexity
• Experimental demonstration of quantum advantage for NP verification with limited information
• Distinguishing noisy boson sampling from classical simulations
• Certified variational quantum algorithms for eigenstate preparation
• Nonadaptive fault-tolerant verification of quantum supremacy with noise
• Magnetic phase diagram and quantum phase transitions in a two-species boson model
• Quantum superiority for verifying NP-complete problems with linear optics
• Exact sampling hardness of Ising spin models
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
• Quantum computational advantage with constant-temperature Gibbs sampling
• Quantum supremacy and quantum phase transitions
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Faster Born probability estimation via gate merging and frame optimisation
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Quantum supremacy in driven quantum many-body systems
• Verifiable measurement-based quantum random sampling with trapped ions
• Quantum advantage from energy measurements of many-body quantum systems
• In situ characterization of linear-optical networks in randomized boson sampling
• Boson Sampling for Generalized Bosons
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Quantum supremacy with analog quantum processors for material science and machine learning
• Learning quantum states prepared by shallow circuits in polynomial time
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• High-performance parallel classical scheme for simulating shallow quantum circuits
• Hardness of efficiently generating ground states in postselected quantum computation
• Certification of spin-based quantum simulators