Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model

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.

Figure 1

(a) The brickwork state. Each circle represents a $|+⟩$ state and each line denotes a cz operation. (b) Propagation of the gate by measuring a qubit. (c) Each white circle with varying rotation angles is replaced by seven physical qubits with fixed rotation angles. The variation in the overall angle is encoded into different measurement outcomes.

Figure 2

Break and bridge operations. Qubit 0 is first rotated by $R_z(\pi /2)$ before measured in the $Z$ and $X$ basis, respectively, to perform the break and bridge operations.