Are there ''interesting'' examples of circuits where gates can all commute each other?

Are there ''interesting'' examples of circuits where gates can all commute each other?

More formally, there may be some group of circuits where gates and, particularly, CNOTs (as the only two-qubit gate in common universal sets), can all commute each other. Such a property is clearly useful because one doesn't have to worry about the order of occurrence.

• Two CNOTs who either share no controls or targets, or share identical controls and targets, always commute. Furthermore, if two CNOTs share controls only, or targets only, they commute. They only don't commute when the control of one is the target of the other. This is assuming no other single qubit gates occur in between the two CNOTs. Nov 9 '21 at 14:33
• How do you define "interesting"? I can immediately think of one example: creation of a graph state (e.g. GHZ state). Nov 9 '21 at 14:54
• I gave on purpose open interpretations of "interesting". Nevertheless, an ideally interesting circuit would be one with many CNOTs and with no efficient classical simulation (in terms of space and/or time). Of course the circuit should have applicability. Nov 9 '21 at 16:34

So, my understanding is that you're asking for a full computational protocol, with a classical answer, for which there is a separation in classical and quantum running times.

First off, we know that we cannot answer that question directly. Nobody has proved for any circuit (except with the help of an oracle) that there is an exponential quantum-classical separation. Let alone commuting circuits.

So, this next question is how strongly do we believe a separation exists, and are there any candidate problems for which there may be a separation? It seems that a separation probably does exist, as indicated by these two papers:

These papers, particularly the second, also give candidate problems to do with sampling particular probability distributions, one related to the Ising model, and one related to the "gap" of a degree 3 polynomial (the difference in the number of solutions to the two equations $$f(x)=0$$ and $$f(x)=1$$).

• Really interesting. I'm quite confused by the difference between "commuting computations" and "instantaneous" from IQP. They seem interchangeable, but instantaneous is a really strong word. Nov 10 '21 at 10:56
• I'm not an expert in this, but I imagine the point is that all the gates can be applied simultaneously. So the whole thing can be completed in one time step. Nov 10 '21 at 11:33
• You're possibly being a bit misled by the imagery invoked by the circuit model. Remember that, fundamentally, a gate is described by a Hamiltonian evolution. If you've got two gates $U_1=e^{iH_1t}$ and $U_2=e^{iH_2t}$, then because they commute, you can implement a single evolution $e^{i(H_1+H_2)t}$. Nov 10 '21 at 12:03
• Technically, yes, but it's non-trivial to work out what $H_3$ is, and you have to include that calculation in your running time evaluation. It might even be that although your constituent Hamiltonian terms are two-body (for example), and therefore corresponding to two-qubit gates, the $H_3$ may not have those properties, and might not be in the set of things that you can implement on your quantum computer. Nov 10 '21 at 12:18
• Yes, in the commuting case, the Hamiltonian is trivial to work out, and has all the same properties as the constituent terms. Nov 10 '21 at 12:54

QROM circuits, where you look up classical data using a quantum address ($$QROM_{\text{data}} = \sum_k |k,\text{data}_k\rangle\langle k|$$), have a natural decomposition where every gate commutes (controls-only on the address register and NOTs-only on the output register):

QROM circuits appear in a lot of algorithms, eg. they can be used to accelerate large multiplications. But you tend not to use this particular circuit decomposition since it's inefficient.