How many matrices do you need to generate a dense subset of $U(n)$?

153 Views Asked by At

In quantum computing, people talk about universal gates, which are a finite collection of matrices $\{U_1,\dots,U_k\}$ that generate a dense subset of $U(n)$. The wiki gives various examples of collections of $\sim \log(n)$ operators that generate $U(n)$.

In the physics literature however, there is a focus on considering unitary matrices that only act on a finite (usually one, two, or three) qubits, so I wouldn't be surprised if you could actually generate $U(n)$ with less (maybe even $O(1)$?) number of operators. Is there an example of this, or a proof that this is impossible?

1

There are 1 best solutions below

0
On BEST ANSWER

The answer is two.

Choose a graph $X$ such that $X$ is controllable, that is, no eigenvector of $X$ is orthogonal to the all-ones vector. Assume $n=|V(X)|$, let $J$ be $n\times n$ matrix of ones, and let $A$ be the adjacency matrix of $X$. Then by Theorem 2 in https://arxiv.org/pdf/0910.5397.pdf (Severini et al), the 1-parameter subgroups $$ \{ \exp(is J): s\in\mathbb{R}\},\ \{\exp(it A): t\in \mathbb{R}\} $$ together generate a dense subgroup of $U(n)$. Since each of these subgroups is isomorphic to $\mathbb{R}/\mathbb{Z}$, they each have a dense subgroup generated by a single element.

By a result of O'Rourke and Touri https://arxiv.org/abs/1511.05080, the proportion of graphs on $n$ vertices that are controllable tends to $1$ as $n\to\infty$.

If fewer examples are needed, we may take the adjacency matrix of the path $P_n$ on $n$ vertices for $A$ and use $e_1e_1^T$ in place of $J$ ($e_1$ is a standard basis vector), and appeal to Corollary 3 in the first cited paper.