title: 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 nonuniversal, 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.
authors.affiliation: Center for Quantum Information, Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, China.
authors.forename: Xun
authors.initials: X
authors.lastname: Gao
authors.affiliation: Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA.
authors.forename: Sheng-Tao
authors.initials: ST
authors.lastname: Wang
authors.affiliation: Center for Quantum Information, Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, China.|Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA.
authors.forename: L-M
authors.initials: LM
authors.lastname: Duan