QByte’s gate set
The thinking behind the choice of basic operations in QByte, the quantum computing project of SeeThrough Studios.
This blog post has three sections. The first section gives an introduction to the circuit model of quantum computing, which is the model underlying QByte. The second section discusses the choice of basic operations (a “gate set”) in the circuit model. The third and final section describes the design choices underlying QByte’s gate set.
The Circuit Model of Quantum Computing
Let me give a definition of a computer that looks circular but isn’t: a computer is a device that performs computations.
I agree that this definition is infuriating, because the definition lacks content unless I am prepared to define ‘computation’. You are likely to worry that I am going to define computation as the activity of a computer, and you would be justifiably infuriated if I define computation in that way.
Well, I’m going to define computation in almost exactly that way. #SorryNotSorry.
Computation is the activity of an abstract device that is called a model of computation. It is in defining these abstract devices that theoretical computer science starts looking like a worthwhile pursuit, and it is in looking into these models that you might possibly forgive me for being infuriating.
If you have encountered theoretical computer science before, you might be aware of one of the two oldest models of computation: the Turing machine. You may also be aware of the lambda calculus of Alonzo Church, which isn’t so much an abstract device as a notation for the activity of that abstract device.
The Turing machine and the lambda calculus are far too complicated and abstract for everyday use. I don’t know of anyone who uses the Turing machine model in any serious way, and the people I know who use lambda calculus are the people who can understand phrases like “natural transformation on a Cartesian closed category”. I am not one of those people.
We ordinary mortals prefer to focus on more easily understood models of computation. In quantum computing, we tend to focus only on a quantum version of the circuit model and leave other models of quantum computing to those who have more patience than us.
The circuit model is informed by the electronic circuits that are ubiquitous in our world. The idea, roughly, is that information flows along wires and is transformed by passing through gates. The wires merely transport information between gates; it is the gates that perform the computations.
The kinds of logic gates that one encounters in the circuit model are probably familiar to you. There are gates like AND, OR and NOT. If a and b are bits (meaning they can take either the value 0 or the value 1) then, in order,
- AND(a, b) returns 1 if a=1 and b=1 and returns 0 otherwise,
- OR(a, b) returns 0 if a=0 and b=0 and returns 1 otherwise, and
- NOT(0) returns 1 and NOT(1) returns 0.
The circuit model for quantum computing is, with one caveat, an extension of what we tend to call the classical circuit model. The way we extend the circuit model is by adding new gates that are only intelligible in a quantum paradigm.
The caveat is that every gate must be reversible, meaning that it is possible to undo the operation of the gate. NOT is reversible, and in fact undoes itself: NOT(NOT(a)) returns a, no matter the value of a. In contrast, AND and OR cannot be undone because they throw away information: we cannot be sure of the values of a or b if all we know is that AND(a, b) returns 0 or that OR(a, b) returns 1.
The reason why we demand reversibility is a bit subtle and I won’t attempt to explain properly here, except to say that our demand arises from the fact that Schrödinger’s equation is deterministic. Fortunately every irreversible computation can be made reversible with constant (I think) space overhead, so we lose nothing.
Choosing a Gate Set
Now that I have given some explanation of the circuit model of computing, observe that the model’s computational ability relies on the possible choices of gates. The point of a model of computing is mainly to assess the cost of computation, but we could assign a unit cost to every computation just by defining a gate that does exactly the computation we’re after! Instead of that, we start by listing all the basic gates we are allowed to perform and then we attempt to build our computation out of those gates. The list of basic gates is what I am calling a ‘gate set’.
We need to be careful when we choose a gate set. I could only allow one gate—NOT—and quickly learn to my dismay that there are many computations I cannot possibly perform using my gate set. In particular, I have no way to build AND gates or OR gates: I need some way of assessing two bits simultaneously, but NOT gates don’t let me do that.
It turns out that the gate set {AND, OR, NOT} is universal: I can build any computation at all from this gate set. It is complicated to do this in practice, of course. But it is possible.
I chose the gate set {AND, OR, NOT} in the previous section because each gate is simple to understand and I do not need to build any serious computations out of them. In other words, I made a choice about gate set that was informed by the goals of this blog post. More generally, any choice of gate set should be informed by the goals that the gate set is intended to serve.
From the point of view of gamifying quantum computing, I see the following goals.
- Each gate in the gate set should be (relatively) easy to understand.
- Interesting computations should be (relatively) straightforward to build.
- Mathematical subtleties should be avoided as much as possible.
These goals inform much more than the choice of gate set, but those other choices are a discussion for a different blog post. Here I aim only to explain the choices we have made for QByte.
QByte’s Gate Set
I hope that the previous discussion has set me up to explain the real point of this blog post: the choice of gate set underlying QByte.
I should begin this discussion by pointing out that the final choice of gate set is not yet made. Whereas we certainly have a minimal set of gates, I fully expect we will add new ones that conform to the principles I lay out below.
The principles underlying QByte’s gate set are:
- don’t use complex numbers,
- multi-qubit gates are much harder than single-qubit gates and
- adding multiple controls is about as easy as adding one control.
I’ll explain each principle in turn.
Complex Numbers
Phase is a core concept in quantum mechanics. You may have heard that Schrödinger’s cat is in a superposition of alive and dead, but you may not be aware that Schrödinger’s cat can be in two different kinds of superposition of alive and dead. To use the Dirac notation that is ubiquitous in quantum computing, Schrödinger’s cat can be |alive⟩+|dead⟩ or |alive⟩–|dead⟩. The distinction between these states is that the |alive⟩ and |dead⟩ possibilities can be ‘in phase’ or ‘out of phase’.
The full story is more complex (pardon the pun) than that. In the usual presentation of quantum mechanics, the phase can be 1 or -1 or anything in between. The definition of in-between phases involves complex numbers.
Complex numbers, as their name suggests, are complicated. We should avoid requiring the player to gain an appreciation for complex numbers. Fortunately, complex numbers are not needed for quantum computing because we can find universal quantum gate sets that do not need to be specified using complex numbers.
As an aside to the nerds, the startling implication is that complex numbers aren’t strictly necessary for quantum mechanics! They are a mathematical convenience.
Multi-Qubit Gates
Consider an important difference between the AND gate and the NOT gate. Whereas the NOT gate accepts only one bit, the AND gate accepts two. In order to specify the action of a 2-bit reversible gate, we need to account for 2²=4 possible inputs (two possibilities for each bit). For a 3-bit reversible gate, there are 2³=8 possible inputs. Four bits? 2⁴=16. Eight? 2⁸=256. Reversible gates that process many bits can get exponentially complicated.
Quantum gates have the same problem. We should avoid making gates too big and complicated, because these gates will confuse the player.
Control
The previous issue can be alleviated, however, if we have a way of extending a gate acting on a small number of (qu)bits to one that acts on a larger number of (qu)bits. And we do: the concept of a controlled operation.
Let me explain the concept of control by example. Consider the gate CNOT, which is like the NOT gate but it acts (reversibly) on two bits:
- CNOT(0, 0) returns (0, 0),
- CNOT(0, 1) returns (0, 1),
- CNOT(1, 0) returns (1, 1) and
- CNOT(1, 1) returns (1, 0).
Another way to express the CNOT: it executes a NOT on the second bit if the first bit is 1 and does nothing to the second bit if the first bit is 0. The first bit is called a ‘control’, and the second bit is called the ‘target’.
It is easy to imagine how this concept can be extended to multiple controls. The CCNOT, for example, accepts three bits: two controls and one target. If both controls are 1, the gate performs a NOT on the target. Otherwise, the gate does nothing.
Putting all of this together, the choice we have made with QByte is to allow a small set of single qubit gates together with the ability to make those gates controlled. Currently the only single qubit gates are the NOT gate (often represented as X) and the Hadamard gate (represented as H), though we are working on implementing rotation gates.
Together with the ability to add controls to gates, we have defined a universal gate set for quantum computation. Each basic gate (X and H now, rotation gates in progress) is relatively easy to understand and acts on only a single qubit. We avoid complicated multi-qubit gates by allowing gates to be controlled by other qubits.
Questions? Comments? We’d love to hear from you!
