Universal gate sets

   Now that we have examined all the basic gates used in quantum computing (plus a few others that simplify how we think about quantum circuits), it is natural to wonder whether we need to know how to create all of them or just a subset. Such subsets exist and are called a universal set of gates: a set of gates that can, alone, duplicate the effects of all other gates needed for computation. In the case of quantum computation, if there were clearly a set of gates that were easiest to build, experimental physicists could built just those (comparatively few) gates and theorists could design a quantum computer based on it (by reducing the needed gate to one of the universal gates already built).
   Initially, the existence of a set of gates like this was proven with the Fredkin gate [7] but, as it was found that a three qubit gate are nearly impossible to control [3], this discovery was quickly superseded by the proof that almost any two-bit gate is universal [1]. For example, you can quickly verify (based on results from classical logic) that Toffili gates (assuming that we donŐt need to control/manipulate the third bit and can use the NAND function) or CNOT gates (each in conjunction with the one qubit Hadamard gate to create superpositions) constitute universal gates. Mathematically, the most elegant choice is that of a Hadamard gate and a controlled-V gate where a V gate is defined below [3].

   One innovative perspective is that a Hadamard gate combined with phase gate to create the most general pure state so, based on the value of Ż used by the phase gate, any single qubit quantum gate should be produceable (see diagram below) [8].

   So, given all these options, what universal set of gates is the ŇbestÓ one? Well, that depends on both which are easiest (or possible) to build given current technologies and what algorithms are useful. Theoretically, a completely universal set of gates would not be needed if we were just interested in building a computer to run ShorŐs algorithm (for factoring large composite numbers) and the algorithm used only a small subset of gates outlined above. However, it turns out that all of the useful functions that quantum computers can do faster than classical computers requires a universal set of gates.
   Given the requirements of possibility and effectiveness, universal sets of gates still are investigated as useful in analyzing the complexity of quantum algorithms [3]. If a single operation can be used to construct any quantum computer, we can measure (in some sense) the complexity of a given algorithm by counting how many times this basic gate is used.
   Another purpose to having many universal sets is for reasoning similar to the creation of programming languages in classical computer science: while we want to be able to run quantum computers with the simplest set of quantum gates, the ability to abstract the functions of combinations of those simple gates into a more complex set of gates is useful to programmers [3]. This is analogous to the way that, while the most efficient way to get a classical computer to run is to give is instructions in machine code, other languages (such as C++) have evolved so that programmers donŐt have to deal with all of the details of machine code. Thus, one algorithm for future exploration may be a compiler to convert complex quantum systems into their simple analogues (of course, this can be done on a classical computer fairly efficiently).

Return to Introduction

Created by Brian Patterson
Last Modified 11/22/00