Return to Answer

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. Quantum Fourier Transform (QFT) provides a counterexample.

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.

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.

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. Quantum Fourier Transform (QFT) provides a counterexample.

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 a very concrete counterexample, 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.

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. Quantum Fourier Transform (QFT) provides a counterexample.

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.

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. Quantum Fourier Transform (QFT) provides a counterexample.

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.

Suppose that $U$ is QFT. By definition $$ U|x\rangle=\frac{1}{\sqrt{d}}\sum_{k=0}^{d-1}\omega^{xk}|k\rangle\tag1 $$ where $\omega=e^{2\pi i/d}$ is a primitive $d$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\}^d$ (see for example this answer for a proof). However, $U$ is known to generate entanglement for some inputs.

For a very concrete counterexample, 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.

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. Quantum Fourier Transform (QFT) provides a counterexample.

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 a very concrete counterexample, 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.