# Why does one need a non-commuting Hamiltonian for an algorithm to exhibit “quantumness”

In two places so far, I've heard statements of the sort "... and we need the Hamiltonian to be non-commuting. If not, the algorithm is classical, and we get no benefit from using a quantum computer."

So why is this the case? Looking for any good answers, but for me 1 to 3 intuitive "ways of looking at it" works best, even if they aren't airtight explanations.

First, a minor point: it doesn't make any sense to say that "a Hamiltonian commutes". You mean that the different terms in the Hamilonian commute. When it comes to commutation, it takes two (or more) to tango.

It is indeed often said that if all the terms of a Hamiltonian commute, then the Hamiltonian is classical. But that isn't really true in my opinion. It's true that if all the terms in the Hamiltonian commute, then there exists a basis of the Hilbert space that simultaneous diagonalizes every term. After you've found this basis and rotated into it, the Hamiltonian does indeed become effectively classical, because each term in the Hamiltonian just contributes a value (that term's eigenvalue) to the total energy, without changing the state at all. Since the Hamiltonian doesn't modify these basis states, its "operator" nature effectively falls away and it basically just becomes a scalar energy function.

But the energy eigenstates are typically complicated superpositions of computational basis states, so they can be nontrivial to calculate (and certainly to engineer experimentally). So the "quantum-ness" only vanishes after you've finished the highly quantum step of finding the simultaneous eigenstates of each term in the Hamiltonian.

For example, the toric code Hamiltonian has every term commuting, and you do sometimes hear the toric code described as "classical", but I personally would say that it's highly quantum.

Finally, saying that "all terms in the Hamiltonian commute" is somewhat ambiguous anyway, because you can sometimes group smaller non-commuting terms together into larger terms that do commute. There's no unambiguous definition of what counts as "a single term" in the Hamiltonian.

• Thanks a lot. Your last paragraph was banging away as a question mark at the back of my skull as I read everything preceding it. Just a few things to clarify - maybe you can confirm or correct me: (1) Even if the Hamiltonian has non-commuting terms, it still has eigenstates, so the last sentence of your para2 holds even in that case right? (2) If you start off in a state that's not an eigenstate, and use a time-independent Hamiltonian, you will never end up in an eigenstate, so whatever's happening to the state is very quantum. This again, is true regardless of terms commuting or not. – Alexander Soare Jun 9 '20 at 8:42
• @AlexanderSoare (1) Yes, that's true, but if the terms don't commute, then each individual term in the Hamiltonian doesn't necessarily have a well-defined energy in an energy eigenstate (even if the entire Hamiltonian as a whole does). So this is conceptually quite different from a classical energy function, where you're typically just adding together a bunch of scalar functions. You can't decompose the scalar energy function into a sum of simpler energy functions, as you can in a truly classical problem. – tparker Jun 9 '20 at 12:39
• @AlexanderSoare (2) Yes, that's exactly correct. For a quantum Hamiltonian with commuting terms, only the energy eigenstates can be even loosely thought of as "classical". – tparker Jun 9 '20 at 12:39

For all we know, it seems that fully-fledged quantum computations indeed require gates (and thus Hamiltonians generating those gates) which don't commute. (But this does not mean that we know this for sure!)

However, it is not true that otherwise, the system can be classically simulated (at least, again, there is strong evidence for that). That is, such a system might not constitute a fully-fledged quantum computer, yet it is more powerful than a classical device. A specific scheme is "instantaneous quantum computing", where all gates commute, yet where evidence has been given that it cannot be classically simulated.