Return to Answer

Corollary Let $f : \{ \pm 1\}^{n\times n} \to \{0, 1\}^m$ be an arbitrary encoding, and $d: \{0, 1\}^m \to \{ \pm 1\}^{n\times n}$ be a decoding, and $W$ be a symmetric Wiegner matrix with independent $\{ \pm 1\}$ entries (above diagonal). If $\|d(f(W)) - W \|_F \leq 2^{-4} n^2$ with probability at least $1/3$, then $m\geq n^2/4$.

Corollary Let $f : \{ \pm 1\}^{n\times n} \to \{0, 1\}^m$ be an arbitrary encoding, and $d: \{0, 1\}^m \to \{ \pm 1\}^{n\times n}$ be a decoding, and $W$ be a symmetric Wigner matrix with independent $\{ \pm 1\}$ entries (above diagonal). If $\|d(f(W)) - W \|_F \leq 2^{-4} n^2$ with probability at least $1/3$, then $m\geq n^2/4$.

It looks like that the second impossibility is the consequence of the first: if I could write $U=S_1 S_2 \ldots S_m$ for some sequence of $m$ simple unitary matrices $S_i$, we could approximate each $S_i$ by a $\tilde{S}_i$ up to small $\varepsilon \leq 2^{-10} / m$ Frobenius error, s.t. each of the matrices $\tilde{S}_i$ is described using only $O(\log(nm))$ bits. Then $\|U - \prod_i \tilde{S}_i\| \leq m \varepsilon \leq 2^{-10}$, and the total number of bits used to encode $U$ is $m \log(nm)$ --- implying $m \gtrsim \tilde{\Omega}(n^2)$ by the previous discussion.

It looks like that the second impossibility is the consequence of the first: if I could write $U=S_1 S_2 \ldots S_m$ for some sequence of $m$ simple unitary matrices $S_i$, we could approximate each $S_i$ by a $\tilde{S}_i$ up to small $\varepsilon \leq 2^{-10} / m$ Frobenius error, s.t. each of the matrices $\tilde{S}_i$ is described using only $O(\log(nm))$ bits. Then $\|U - \prod_i \tilde{S}_i\|_F \leq m \varepsilon \leq 2^{-10}$, and the total number of bits used to encode $U$ is $m \log(nm)$ --- implying $m \gtrsim n^2/\log n$ by the previous discussion.

Lemma Let $f: \{ \pm 1\}^n \to \{0, 1\}^m$ be an encoding function, and $d:\{0, 1\}^m \to \{\pm 1\}^n$ be decoding, s.t. with probability at least $1/3$ over random $x \in \{ \pm 1\}^n$ we have $d_H(d(e(x)), x) \leq 1/4$, where $d_H$ is the Hamming distance $d_H(x, y) = |\{k : x_k \not= y_k\}|$. Then $m \geq n/2$.

If we could find orthogonal $\tilde{U}$ s.t. with probability $1/3$ we had $\|\tilde{U} - U\|_F \leq 2^{-12} n$, and encode $\tilde{U}$ using $n^2/16$ bits, we can chose $\tilde{W}$ to be a Frobenius-norm projection of $\tilde{U} \tilde{D} \tilde{U}^T$ on symmetric $\{\pm 1\}^{n\times n}$ matrices.

Lemma Let $f: \{ \pm 1\}^n \to \{0, 1\}^m$ be an encoding function, and $g:\{0, 1\}^m \to \{\pm 1\}^n$ be decoding, s.t. with probability at least $1/3$ over random $x \in \{ \pm 1\}^n$ we have $d_H(g(f(x)), x) \leq 1/4$, where $d_H$ is the normalised Hamming distance $d_H(x, y) := |\{k : x_k \not= y_k\}|/n$. Then $m \geq n/2$.

If we could find orthogonal $\tilde{U}$ s.t. with probability $1/3$ we had $\|\tilde{U} - U\|_F \leq 2^{-12} n$, and encode $\tilde{U}$ using $n^2/16$ bits, we would chose $\tilde{W}$ to be the Frobenius-norm projection of $\tilde{U} \tilde{D} \tilde{U}^T$ on symmetric $\{\pm 1\}^{n\times n}$ matrices.