characterization of non-entangling gates

Question

I suspect the following is true and "well-known" but I cannot find any reference for it. Can anyone help?

Let $U$ be a unitary quantum gate acting on a pair of $d$-dimensional qudits. Suppose $U$ is non-entangling. That is, for any two-qudit tensor product state $| \psi \rangle \otimes | \phi \rangle$, the state $U | \psi \rangle \otimes | \phi \rangle$ is also a tensor product state. Then $U$ must be expressible in one of the two following forms:

1) $U = F \otimes G$, i.e. $U$ is just a pair of single-qudit gates

2) $U = \mathrm{SWAP} (F \otimes G)$, i.e. $U$ is a SWAP gate followed by a pair of single-qudit gates.

Answer 1

I have recently found a reference proving the statement from my question. It is:

Universal quantum gates
Jean-Luc Brylinski and Ranee Brylinski
In Mathematics of Quantum Computation, Chapman & Hall (2002)
arXiv:quant-ph/0108062
Theorem 1.4, proven in section 8.

Answer 2

I do know something about the history of the problem, but I don't know the answer. The first reference is

1. S. Lloyd, Almost any quantum logic gate is universal, Phys. Rev. Lett. 10, 346–349 (1995).

which gives a "proof" of this... but it isn't strictly correct. I don't know what exactly was wrong with it, because I never looked at it in detail. It doesn't seem to be on the arxiv, either. The qubit case was actually proven in this paper:

2. D. Deutsch, A. Barenco and A. Ekert, Universality in quantum computation, Proc. Roy. Soc. London A, 449, 669-677 (1995). arXiv:quant-ph/9505018

Looking through it, they seem to write what you say as a conjecture on p 6. It's the "canonical" universality reference AFAIK.

This next paper discusses the qudit case, but from the perspective of Hamiltonians (generators of the unitary group). I think it might contain the statement that you're after, but don't see the paper on the arxiv (annoying), so I can't check at the moment.

3. N. Weaver, On the universality of almost every quantum logic gate, J. Math. Phys. 41, 240 (2000).

Also, this next paper is at least related (though it is again about Hamiltonians), so the background section might contain a reference to the theorem that you want.

4. A. M. Childs, D. Leung, L. Mancinska, M. Ozols, Characterization of universal two-qubit Hamiltonians, Quant. Inf. Comp. 11, 19-39 (2011). arXiv:1004.1645

Off the top of my head, I don't see any reason why the Hamiltonian case should be very different from the unitary case, but I suspect this is the trouble with the Lloyd paper, so I would tread carefully if I were you.