KREQC (pronounced "creek") is Kentucky's Rotationally Emulated Quantum Computer. It is a quantum computer that works at room temperature -- and it is an open source design, so you can build your own for under $100. It's not useful as a computer, but it makes a great demonstration of how quantum computation works.
You've probably heard quite a lot about quantum computing... and understand just a little. Us too. That's because most of the presentations of it are more about the interesting physics than how these devices function as computers. Well, KREQC is a 6-Qubit quantum computer that implements Einstein's spooky action at a distance using conventionally-controlled servos rather than interesting phenomena that happen in physics experiments cooled to nearly absolute zero. This makes the processing much more observable, and we've even created a WWW interface that lets you run quantum programs on KREQC (server is currently disabled), not only producing complete results, but also returning a video of the hardware actually doing the computation. However, before you rush off to run stuff on KREQC, you should read the following explanation of how this stuff works.
Before proceeding to explain this, let me appologize to any physicists in the audience. You're not going to see any mention of Bloch spheres, quantum-mechanical properties like spin, nor even matrix math, here; our explanation does not even use complex numbers (i components). Why not? Because they aren't needed to explain the higher-level behaviors of a quantum system as a computer. Despite the fact that "real" quantum computers are built very differently, KREQC's "emulation" just implements a nice physical display of what's happening inside a strange type of parallel computation using reversible logic.
Instead of storing values as bits that each hold either a 0 or 1, quantum computers store values using qubits that each can hold a value that is 0, 1, or indeterminate (commonly called the superposition state). Multiple entangled qubits have the rather useful property that their indeterminate values can simultaneously cover all possible combinations of bit values. Six bits can have any one value from 0 to 63 (i.e., 2^6), but KREQC's six qubits can have an indeterminate value which is simultaneously all values from 0 to 63 with a potentially different probability associated with each possible value. When the value of a qubit is read, the values of it and all qubits entangled with it become determined, with the single bit value read for each qubit being randomly selected in accordance with the probabilities. For example, if the indeterminate value is 75% 42 and 25% 0, then approximately three out of every four times the quantum computation is performed, the result will be 42 and the other times it will be 0. The power lies in the fact that with just 6 fully-entangled qubits, a quantum computer evaluates all 64 values simultaneously. You'd need a conventional computer with 64 parallel 6-bit compute engines to do the same... and that's essentially how KREQC emulates it.
Each of KREQC's physical qubits can have a rotational value that is 0, 1, or something in-between: indeterminate. An equiprobable indeterminate value is represented by a qubit in the horizontal position. As a quantum computation proceeds, probabilities of different values change -- represented in KREQC by the individual qubits "wobbling" and assuming statistical positions reflecting the probabilities of specific values. Eventually, the quantum computation is terminated by measuring the entangled qubits, which collapses the indeterminate value into a fully determined sequence of 0s and 1s. In KREQC, the least-significant qubit is in the front right and the most-significant qubit is in the rear left; in other words, 42, which in binary is 101010, would be shown as 101 in the back row of qubits and 010 in the front.
Of course, there are problems with using quantum computers. Two quantum problems KREQC doesn't suffer are corruption of values by noise and limited coherence time; KREQC's qubits can stay uncorrupted by noise and entangled for as many gate-level operations as you wish. However, KREQC does suffer from other problems associated with quantum computing. An obvious one is that we really want millions of qubits, not just 6. However, it's also important to note that quantum computers only implement combinatorial logic -- as opposed to what we computer engineers call a state machine. This is why I don't like calling indeterminate values a "superposition state" -- it's not actually a state in the usual sense. Basically, despite what some folks claim, a quantum machine by itself is less capable than a Turing machine or a conventional computer. Of course, there is no reason we can't use a conventional computer to control a quantum machine. Thus, a state machine is implemented using a sequence of quantum computations, one per state-visit in the state machine's execution. Just keep in mind that the magical properties of qubits are not preserved across multiple quantum computations: only bit values can be copied from one state to the next, not entangled qubit values.
Fundamentally, one of the biggest issues with programming quantum computers is that there really isn't complete agreement on what the basic operations should be, nor is there agreement on what different types of operations cost to implement (especially in terms of execution time). The obviously most commercially-successful quantum computer maker thus far is D-Wave, which implements a computational model known as quantum annealing -- basically casting each computation as solving a minimization problem. Most other quantum computers implement a set of quantum gates. For example, Google and IBM both implement a variety of types of quantum gates, and it seems that's the way most people think things should work... although it's harder to get to useful numbers of qubits that way.
Quantum gates come in quite a few flavors, very few of which are familiar to computer engineers. The key concept is that none of the gates support fanout: the number of inputs is the same as the number of outputs. KREQC is programmed by initializing qubits and then applying a sequence of any of the supported gate types to the defined qubit names.
Bits are initialized by what look like simple assignments. For example, a=0; will make the least-significant available qubit be called a and have an initial value of 0. Similarly, space2001=1 would make the next available qubit be named space2001 and have the initial value 1. The more interesting initial value is ?, which quantum computing folk tend to think of as an H gate, applying a Hadamard transform. What's a Fourier transform doing here? Relax. It just means the qubit is initialized to the indeterminate equiprobable value -- 50% 0 and 50% 1. All qubits initialized to ? are not just individually equiprobably 0 or 1, but are equiprobably all combinations of 0s and 1s. Thus, q0=?; q1=?; means q1 and q0 are 25% 00, 25% 01, 25% 10, and 25% 11.
Ok, so you've initialized all your qubits... what next? Well, you specify a sequence of gates to apply to them. Each gate can operate on any of the qubits you've defined, but remember that there is no fanout allowed, so no two inputs to a gate can come from the same qubit, and the output values essentially update the input qubits. Here are the basic gates supported by KREQC:
QUBIT q
0 |
NOT +
64 |
QUBIT q1 q0
32 | 0 |
CNOT @-------+
32 | 32 |
QUBIT q1 q0
32 | 0 |
SWAP x-------x
0 | 32 |
QUBIT q2 q1 q0
0 | 32 | 64 |
CCNOT +-------@-------@
32 | 32 | 64 |
QUBIT q2 q1 q0
32 | 64 | 0 |
CSWAP @-------x-------x
32 | 32 | 32 |
Now that you understand the notation, let's make a simple program that does something vaguely useful: a 1-bit full adder. Here's a simple design using five Fredkin (CSWAP) gates:
There is a little problem here in that some of the qubits have two different names, one as an input and another as an output. KREQC doesn't allow that, so we'll just use the output names. This also doesn't specify what the initial values of p, q, and r are supposed to be, so we'll let them literally be all possible values. With those tweaks, the quantum program is:
p=?; q=?; carry=?; parity=0; g=1; CSWAP(p, parity, g); CSWAP(q, parity, g); CSWAP(carry, parity, g); CSWAP(parity, carry, g); CSWAP(q, carry, g);
Running this on the KREQC simulator produces a two-part textual output. The first part is the "lane diagram" structure that was described above, showing how the values of the qubits pass through the sequence of gates:
QUBIT g parity carry q p
32 | 64 | 0 | 32 | 32 | 32 |
CSWAP | x-------x-------|-------|-------@
32 | 32 | 32 | 32 | 32 | 32 |
CSWAP | x-------x-------|-------@ |
32 | 32 | 32 | 32 | 32 | 32 |
CSWAP | x-------x-------@ | |
32 | 32 | 32 | 32 | 32 | 32 |
CSWAP | x-------@-------x | |
32 | 48 | 32 | 16 | 32 | 32 |
CSWAP | x-------|-------x-------@ |
32 | 32 | 32 | 32 | 32 | 32 |
0 0 1 1 1 1
Note that the 6th bit was never named, so it is essentially unbound. The 001111 pattern in the last line of that output is the result of reading (randomly sampling) the qubits, and that value can be different from run to run. For example, the very next run gave 110101.
For a real quantum computer, one set of qubit values is all you can read from one run, but we're talking about KREQC's simulator, and it can do better. The simulator actually knows the probability of each set of qubit values. Thus, that's the second part of the textual output:
g parity carry q p
8/64 0 0 1 1 1
8/64 0 1 0 0 1
8/64 0 1 0 1 0
8/64 0 1 1 1 1
8/64 1 0 0 0 0
8/64 1 0 1 0 1
8/64 1 0 1 1 0
8/64 1 1 0 0 0
This part of the output ignores the qubit that wasn't explicitly used. In most quantum computing systems, you have to specify which qubits you want to measure (read). Here, there is no explicit specification, so the system assumes all that you named are potentially significant to you. The 8/64 simply gives the probability that each of these value sets is read; here, each value set would be returned 12.5% of the time.
One of the little problems associated with quantum computing is that those lovely superposition values, and everything entangled with them, collapse into a single value when you look at (measure) them. Various quantum operators have been suggested that could perform operations effectively testing the superposed values without collapsing the state -- essentially using some type of wave function interference. Unfortunately, actual implementations of such functions are elusive and the models are awkwardly directly involving the wave functions rather than working as conventional gates. Thus, in addition to the basic gates above, we've created our own gate-like non-collapsing tests: ANYSWAP and ALLSWAP.
QUBIT q2 q1 q0
32 | 64 | 0 |
CSWAP ?-------x-------x
32 | 0 | 64 |
On the other hand, q0=0; q1=1; q2=0; ANYSWAP(q2,q1,q0);
would result in 100% 010.
QUBIT q2 q1 q0
0 | 64 | 0 |
CSWAP ?-------x-------x
0 | 64 | 0 |
QUBIT q2 q1 q0
32 | 64 | 0 |
CSWAP *-------x-------x
32 | 64 | 0 |
On the other hand, q0=0; q1=1; q2=1; ALLSWAP(q2,q1,q0);
would result in 100% 001.
QUBIT q2 q1 q0
0 | 64 | 0 |
CSWAP *-------x-------x
0 | 0 | 64 |
ANYSWAP and ALLSWAP can thus be used to implement a wide variety of powerful operations. For example, to compute the maximum value of a:
// maximum value of a a = ?; max = 0; one = 1; ANYSWAP(a, max, one);
The KREQC hardware is now housed in our 108A Marksbury machine room at the University of Kentucky:
Of course, it is a bit of a joke for it to be in an air-conditioned machine room among our cluster supercomputers. Although we haven't measured power drawn by KREQC, it is reliably powered by a 2.5 amp 5 volt supply, and it really doesn't generate significant heat. It also is rather tiny compared to even the single-rack cluster that is sitting beside it. Then again, why not house it there?
One of the PCs racked next to KREQC acts as KREQC's head node, providing control of the hardware via a USB connection to a Pololu Micro Maestro 6-Channel USB Servo Controller. That head node also provides a quantum computing batch job scheduler accessed via a TCP server. Like most quantum computers, KREQC is not inherently sharable, so one job runs at a time. The system is capable of performing a modest combinatorial logic computation in 1/2s or less, but the speed of operation has been deliberately slowed to about 1/5s per gate so that the operations are more visible to a human observer. Although a maximum time limit is enforced on each quantum program, the system may become quite slow to respond if many requests are enqueued, perhaps taking minutes before your program has its turn to run.
To run your quantum program on KREQC, use this WWW interface. In addition to directly producing simulation output, that interface can emulate your program on the six qubits of the actual KREQC hardware while capturing a video of the computation. The video is directly returned and viewable via the WWW form. However, videos are not cached on the server, so requesting the video again will actually re-execute the program and return a new video. The final value displayed may be different on different runs because it is statistically selected from the set of possible results, just as it would be using other quantum computers. Here's a sample video -- execution of the full adder example given above:
In the video, KREQC initially shows all six qubits having equiprobable indeterminate values -- every qubit is precisely half-way between 0 and 1. As the initial conditions of your program are imposed, some qubits may be set to determinate 0 or 1 values. For the full adder, qubit 4 (parity) is initialized to 0 and qubit 5 (g) is initialized to 1. As the computation progresses, the average position of each qubit tracks the probability that its value is 0 or 1. Thus, when g has a probability of 48/64 of being a 1, qubit 5 has an average position of 48/64 of the way between 0 and 1. You might also notice a tiny amount of noise in the positions as the computation progresses, which serves three purposes: (1) it models noise in other quantum computers, (2) keeping the qubits moving ensures KREQC's servos experience dynamic friction rather than the larger static friction thus improving reliability, and (3) it looks cool. At the end of the sequence of gate operations, a randomly-selected result is latched to read out (measure). After measurement, KREQC is returned to displaying equiprobable indeterminate values.
The video above looks just as one would hope -- everything worked. Does KREQC always work perfectly? Well, when we brought it to demonstrate live at our SC18 research exhibit, it worked with an essentially zero error rate. However, it came back to Lexington, KY on our pallet, and during its travels, was literally skewered by a forklift. Two of the 3D-printed qubits were broken and had to be welded back together, which was easier than it sounds. However, the forklift incident seems to have damaged qubit 4 (the rear right one) in some way that causes it to occasionally miss showing an operation. At this writing, the error rate even for qubit 4 is well under 1%, but be warned that KREQC is no longer 100% reliable. If KREQC sees significant use and the error rate worsens, we'll probably repair/upgrade it.
The only thing set in stone is our name.