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

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.

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.

• "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" our of curiosity: are you saying that any unitary with this property has an efficient circuit decomposition? Or just that the decomposition of the QFT you're referring to is a standard step in the derivation of the decomposition for the QFT?
– glS
Commented Apr 16, 2023 at 15:06
• I don't know if this is true for all such unitaries, but it is true for many more than just the QFT. We can certainly say the following: if $$U|x\rangle=|f_1(x_1,\dots,x_n)\rangle\otimes|f_2(x_2,\dots,x_n)\rangle\otimes\dots\otimes|f_n(x_n)\rangle$$ and if each factor $|f_k(x_k,\dots,x_n)\rangle$ can be implemented efficiently by a circuit which uses $x_{k+1}\dots x_n$ as controls (and hence doesn't disturb computational basis states on qubits $k+1$ to $n$) then we can implement $U$ efficiently, too (by essentially following the recursive construction of the standard QFT circuit). Commented Apr 16, 2023 at 17:23

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