Is it true that if $U$ sends computational basis states to product states, then it sends product states to product states?

Question

Let $U$ be a unitary such that for all $n$-qubit computational basis states $|x\rangle$, the state $U |x\rangle$ is a product state. I am trying to prove that for all $n$-qubit product states $|w\rangle = |w_1\rangle \otimes \cdots \otimes |w_n\rangle$, the state $U|w\rangle$ is also a product state.

Is there a slick way to solve this problem? My approach involved expanding each $|w_i\rangle$ into the computational basis as $\alpha_i|0\rangle + \beta_i|1\rangle$, and then multiplying out all the states, but this gets messy fast.

Answer 1

TL;DR: The claim is false, i.e. it is not true that if $U|x\rangle$ is a product state for all computational basis states $|x\rangle$, then $U$ sends product states to product states. Counterexamples include the Quantum Fourier Transform (QFT) and the controlled NOT gate.

In fact, the failure of the claim is central to some of the most impressive examples of quantum advantage. On one hand, the fact that QFT sends computational basis states to product states is the key observation behind the construction of an efficient quantum circuit for it. On the other hand, the fact that QFT sends some product states to entangled states appears to prevent us from constructing an efficient classical circuit for it.

Anyway, suppose that $U$ is the QFT on $n$ qubits. By definition $$ U|x\rangle=\frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}\omega^{xy}|y\rangle\tag1 $$ where $\omega=e^{2\pi i/2^n}$ is a primitive $2^n$th root of unity. The amplitudes of $U|x\rangle$ written in the natural order implied by the computational basis form a geometric progression. Therefore, $U|x\rangle$ is a product state for every $x\in\{0,1\}^n$ (see for example this answer for a proof). However, QFT is known to generate entanglement for some inputs. For example, suppose $U$ is the QFT on two qubits $$ U=\frac{1}{2}\begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i & -1 & i \end{bmatrix}.\tag2 $$ The columns of the matrix are product states $|+\rangle|+\rangle$, $|-\rangle|{+i}\rangle$, $|+\rangle|-\rangle$ and $|-\rangle|{-i}\rangle$. However, $U|0\rangle|+\rangle$ is the state $\frac{1}{\sqrt{8}}[2,1+i,0\,1-i]^T$ which is entangled, as can be checked by for example writing it as a $2\times 2$ matrix and verifying that its determinant is non-zero.

An even simpler counterexample is the controlled NOT gate which permutes the computational basis, but sends $|+\rangle|0\rangle$ to a Bell state.

Answer 2

No - the CNOT gate is a simple counterexample. It maps computational basis states to computational basis states, but it can be used to create entangled states (e.g. when acting on $|+\rangle|0\rangle$).