Skip to main content
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
Source Link

Let $\{v_1, \dotsc, v_m\} \in \mathbb{C}^{2^n}$ be a set of orthonormal vectors. Define a map $R_m$ from $2^n \times 2^n$ to $m \times m$ matrices as follows: $$R_m(M) := \sum_{i,j=1}^m (v_i^*M v_j) E_{ij}$$ where $E_{ij} := e_i e_j^*$ is the all-zeroes matrix with entry 1 at position $(i,j)$. In other words, $R_m$ performs a unitary change of basis and then takes the top-left $3 \times 3$ block of the resulting matrix.

For any $n \geq 2$, show that no matter how the vectors $\{v_i\}$ are chosen, $$\mathrm{U}(3) \not\subseteq \bigl\{ R_3(U_1 \otimes \dotsb \otimes U_n) : U_i \in \mathrm{U}(2) \bigr\}.$$ That is, as matrices $U_i$ range over all possible $2 \times 2$ unitaries, their tensor product will never contain the set of all $3 \times 3$ unitaries in some basis.

More generally, this should hold even if $2 \times 2$ unitaries are replaced by $d \times d$ unitaries and $m = 3$ is replaced by any $m > d$. The motivation for this question comes from "encoded universality" in quantum computing.

Note: I originally asked this question on math.stackexchangemath.stackexchange but did not receive any answer.

Let $\{v_1, \dotsc, v_m\} \in \mathbb{C}^{2^n}$ be a set of orthonormal vectors. Define a map $R_m$ from $2^n \times 2^n$ to $m \times m$ matrices as follows: $$R_m(M) := \sum_{i,j=1}^m (v_i^*M v_j) E_{ij}$$ where $E_{ij} := e_i e_j^*$ is the all-zeroes matrix with entry 1 at position $(i,j)$. In other words, $R_m$ performs a unitary change of basis and then takes the top-left $3 \times 3$ block of the resulting matrix.

For any $n \geq 2$, show that no matter how the vectors $\{v_i\}$ are chosen, $$\mathrm{U}(3) \not\subseteq \bigl\{ R_3(U_1 \otimes \dotsb \otimes U_n) : U_i \in \mathrm{U}(2) \bigr\}.$$ That is, as matrices $U_i$ range over all possible $2 \times 2$ unitaries, their tensor product will never contain the set of all $3 \times 3$ unitaries in some basis.

More generally, this should hold even if $2 \times 2$ unitaries are replaced by $d \times d$ unitaries and $m = 3$ is replaced by any $m > d$. The motivation for this question comes from "encoded universality" in quantum computing.

Note: I originally asked this question on math.stackexchange but did not receive any answer.

Let $\{v_1, \dotsc, v_m\} \in \mathbb{C}^{2^n}$ be a set of orthonormal vectors. Define a map $R_m$ from $2^n \times 2^n$ to $m \times m$ matrices as follows: $$R_m(M) := \sum_{i,j=1}^m (v_i^*M v_j) E_{ij}$$ where $E_{ij} := e_i e_j^*$ is the all-zeroes matrix with entry 1 at position $(i,j)$. In other words, $R_m$ performs a unitary change of basis and then takes the top-left $3 \times 3$ block of the resulting matrix.

For any $n \geq 2$, show that no matter how the vectors $\{v_i\}$ are chosen, $$\mathrm{U}(3) \not\subseteq \bigl\{ R_3(U_1 \otimes \dotsb \otimes U_n) : U_i \in \mathrm{U}(2) \bigr\}.$$ That is, as matrices $U_i$ range over all possible $2 \times 2$ unitaries, their tensor product will never contain the set of all $3 \times 3$ unitaries in some basis.

More generally, this should hold even if $2 \times 2$ unitaries are replaced by $d \times d$ unitaries and $m = 3$ is replaced by any $m > d$. The motivation for this question comes from "encoded universality" in quantum computing.

Note: I originally asked this question on math.stackexchange but did not receive any answer.

Source Link

Why a tensor product of $2\times 2$ unitaries cannot implement a $3\times 3$ unitary?

Let $\{v_1, \dotsc, v_m\} \in \mathbb{C}^{2^n}$ be a set of orthonormal vectors. Define a map $R_m$ from $2^n \times 2^n$ to $m \times m$ matrices as follows: $$R_m(M) := \sum_{i,j=1}^m (v_i^*M v_j) E_{ij}$$ where $E_{ij} := e_i e_j^*$ is the all-zeroes matrix with entry 1 at position $(i,j)$. In other words, $R_m$ performs a unitary change of basis and then takes the top-left $3 \times 3$ block of the resulting matrix.

For any $n \geq 2$, show that no matter how the vectors $\{v_i\}$ are chosen, $$\mathrm{U}(3) \not\subseteq \bigl\{ R_3(U_1 \otimes \dotsb \otimes U_n) : U_i \in \mathrm{U}(2) \bigr\}.$$ That is, as matrices $U_i$ range over all possible $2 \times 2$ unitaries, their tensor product will never contain the set of all $3 \times 3$ unitaries in some basis.

More generally, this should hold even if $2 \times 2$ unitaries are replaced by $d \times d$ unitaries and $m = 3$ is replaced by any $m > d$. The motivation for this question comes from "encoded universality" in quantum computing.

Note: I originally asked this question on math.stackexchange but did not receive any answer.