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 (7)

• Quantum Computing
• Quantum algorithm for solving linear systems of equations
• Single-Atom Resolved Fluorescence Imaging of an Atomic Mott Insulator
• Single-Spin Addressing in an Atomic Mott Insulator
• Efficient quantum state tomography
• Photonic Boson Sampling in a Tunable Circuit
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy