Exact sampling hardness of Ising spin models

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 boson sampling, 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 boson sampling, 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. The latter is most likely necessary to enable a convincing experimental demonstration of quantum supremacy. As referenced in a recent paper [A. Bouland, L. Mancinska, and X. Zhang, in Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2016)], our result completes the sampling hardness classification of two-qubit commuting Hamiltonians.

Figure 1

Schematic of the model. Spins in sublattice $\mathcal{A}$ (red, ${\widehat{\sigma }}_i$) are coupled to spins in sublattice $\mathcal{B}$ (blue, ${\widehat{\tau }}_j$) via Ising couplings ${\widehat{\sigma }}_i^x{\widehat{\tau }}_j^x$ and all of them start off in $|\downarrow \rangle$. To lowest order in time, the matrix element of the time-evolution operator between an initial state with all spins initialized in $|\downarrow \rangle$ and a final state with all qubits in $|\uparrow \rangle$ receives contributions in which each spin is flipped precisely once (one such contributing term, between the spin on the second site of $\mathcal{A}$ and the spin on the first site of $\mathcal{B}$, is shown).

Figure 2

Example of a single term contributing to the matrix element $M_t$ at lowest order in time ($t^N$, here with $N=3$). Here, all spins are flipped from down to up by a particular pairing off of the spins between the $\mathcal{A}$ and $\mathcal{B}$ sublattices. The depicted process contributes a term $(J_{1,2}\times J_{3,1}\times J_{2,3})\times (t^3/3!)$ to $M_t$. The set of all possible ways to pair the spins in sublattice $\mathcal{A}$ with the spins in sublattice $\mathcal{B}$ is in one-to-one correspondence with terms in the permanent of the matrix $J_{i,j}$ and thus $M_t$ is proportional to this permanent.