One of the critical arguments in the Eastin-Knill Theorem is that a finite set of gates cannot be universal since "a finite number of unitary operators cannot approximate infinitely many to arbitrary precision". However, we know from Shi's paper that just Hadamard and CCZ are sufficient for quantum computation. How can these two facts be reconciled?
1
-
2$\begingroup$ You can have a finite set of gates but still can generate all the other gates (unitaries). A universal set of gates $S$, for example $S = \{H, S, CNOT\}$, and there are many many others, have finite number of gates in it but you can place them in different order to generate any unitary you want... $\endgroup$– KAJ226Commented Apr 20, 2022 at 3:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
$\{H,CCZ\}$ is just the generating set. The set of gates it generates, i.e. $\langle H, CCZ \rangle$, has an infinite number of gates so it could be universal. The argument in Eastin-Knill says the entire group of transversal gates is finite not just its generating set.
