Consider a model of quantum computation in which you require all the gates in your quantum circuit to commute. This is an extremely weak model of computation, as it seems unlikely to be capable of even universal classical computation. Surprisingly, in 2012, Bremner, Jozsa, and Shepherd showed that certain commuting circuits are difficult to simulate classically unless the polynomial hierarchy collapses. A natural question is if this sort of hardness result holds for other, more general, commuting circuits.
In this work, we answer this question in the affirmative by showing that computations involving essentially *any* two-qubit commuting Hamiltonian are hard to simulate classically. Our proof makes use of Lie theory and properties of the exponential map on SL(2,C). This shows that generic commuting quantum circuits can perform computational tasks which are intractable for classical computers under plausible assumptions.
Based on joint work with Xue Zhang.
