×

Universality in quantum computation. (English) Zbl 1099.68030

Díaz, Josep (ed.) et al., Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12–16, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22849-7/pbk). Lecture Notes in Computer Science 3142, 793-804 (2004).
Summary: We introduce several new definitions of universality for sets of quantum gates, and prove separation results for these definitions. In particular, we prove that realisability with ancillas is different from the classical notion of completeness. We give a polynomial time algorithm of independent interest which decides if a subgroup of a classical group \((\mathbf {SO}_n, \mathbf {SU}_n, \mathbf {SL}_n \dots)\) is Zariski dense, thus solving the decision problem for the completeness. We also present partial methods for the realisability with ancillas.
For the entire collection see [Zbl 1056.68007].

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
81P68 Quantum computation
20G15 Linear algebraic groups over arbitrary fields
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI