5
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – chrysaor4
    Nov 9, 2021 at 14:33
  • 2
    $\begingroup$ How do you define "interesting"? I can immediately think of one example: creation of a graph state (e.g. GHZ state). $\endgroup$
    – DaftWullie
    Nov 9, 2021 at 14:54
  • $\begingroup$ 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. $\endgroup$
    – Daniele Cuomo
    Nov 9, 2021 at 16:34

2 Answers 2

Reset to default
4
$\begingroup$

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$).

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Daniele Cuomo
    Nov 10, 2021 at 10:56
  • $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Nov 10, 2021 at 11:33
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – DaftWullie
    Nov 10, 2021 at 12:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Nov 10, 2021 at 12:18
  • 1
    $\begingroup$ Yes, in the commuting case, the Hamiltonian is trivial to work out, and has all the same properties as the constituent terms. $\endgroup$
    – DaftWullie
    Nov 10, 2021 at 12:54
3
$\begingroup$

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):

enter image description here

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.