4
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\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$
    – KAJ226
    Apr 20, 2022 at 3:01

1 Answer 1

5
$\begingroup$

$\{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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.