I agree that there is no classification of the nonuniversal 2-qubit unitaries and that this seems too basic a question to be left unresolved. However, one of the things I was trying to point out in my previous comment is that we do have such a classification for 2-qubit Hamiltonians at least in regards to “in place” universality. In particular, H is nonuniversal iff 1) H is traceless or 2) H shares an eigenvector with the swap gate or 3) H is similar* to a local Hamiltonian (*some details missing). Unfortunately we could not resolve which non-universal Hamiltonians become universal in the presence of ancilla, which perhaps is a more natural scenario.

I haven’t thought about the universality problem for a while now, but I’ll make sure to email you and Adam if anything useful comes to mind. I am looking forward to the developments to come š

]]>By analogy, relatively early in my, Daniel Grier, and Luke Schaeffer’s classification project, we had managed to classify “almost all” n-bit classical reversible gates (i.e., 100% of them, in the limit as n goes to infinity). But handling the remaining 0% then took us several more months. š

]]>Based on the very hazy terms in which I understand quantum computing, it would surprise me if those two classes were incomparable. QM is an “island in theory-space”, right? So BQP should be hard to extend in an interesting way. But here we have two purportedly distinct, natural, not-too-powerful extensions? How many such extensions could there possibly be?

]]>- Iām confused, I thought part of the point of PDQP was that it was contained in DQP?

No, the point is that it’s a variation on DQP that captures many of the same intuitions—e.g., both classes contain SZK and BQP and probably fail to contain NP for very similar reasons—while also being easier to reason about. If it were also contained in DQP, that would be a further nice property, but now that I’ve (belatedly!) explicitly considered that question, I don’t see how to prove it.

]]>There are actually some pretty interesting recent results (typically involving algebraic number theory) about *exact* synthesis of unitary transformations; see for example here. A major reason for the interest is that, for the special quantum gate sets for which you can use algebraic number theory to understand which unitaries can and can’t be represented exactly, you can use more algebraic number theory to get procedures for approximating *arbitrary* unitaries that blow the parameters of the Solovay-Kitaev Theorem out of the water. (Specifically, you can get within an additive constant of the information-theoretic limit of log(1/ε) gates, as compared to the Solovay-Kitaev bound, which was log^{3.97}(1/ε)—a huge difference in practice.) See here for example.

So I wouldn’t say that the exact classification problem is “absurd”—I would merely say that it seems way more complicated even than the approximate classification problem, making the latter a very obvious place to start!

]]>