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, 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:

`NOT(`*q*`);`-
This operation, also known as the Pauli X gate, simply flips the value of qubit
*q*. Thus, a 0 becomes a 1 and vice-versa. Of course, for indeterminate values it does the same thing, flipping that particular bit within every possible multi-bit indeterminate value. The circuit diagram representation of a NOT operation is a circle with a "+" in it; in the textual output of KREQC's simulator, we use "+". For example,`q=0; NOT(q);`is shown as:QUBIT q 0 | NOT + 64 |

The`0`signifies that none of the 64 potentially-unique indeterminate values in KREQC's 6 qubits has qubit`q`'s value as 1. Of course, after the NOT, all`64`values do. `CNOT(`*c*`,`*t*`);`-
The "controlled not" (or conditional not) always leaves the
control qubit
*c*unchanged, but flips the value of*t*if*c*is 1. Simple enough... except maybe for indeterminate values. They conditionally flip too. For example,`q0=0; q1=?; CNOT(q1,q0);`will result in 50% 00 and 50% 11, in other words, this particular example makes`q0`a copy of`q1`. The circuit diagram representation of a CNOT operation uses a solid circle to represent the control input, which the KREQC simulator displays textually using "@":QUBIT q1 q0 32 | 0 | CNOT @-------+ 32 | 32 |

`SWAP(`*i0*`,`*i1*`);`-
This operation simply swaps the values of
`i0`and`i1`. For example,`q0=0; q1=?; SWAP(q1,q0);`will result in 50% 00 and 50% 01. KREQC's text display uses an "x" to indicate a swap:QUBIT q1 q0 32 | 0 | SWAP x-------x 0 | 32 |

`CCNOT(`*a*`,`*b*`,`*c*`);`-
The "controlled-controlled-not" gate is perhaps better known as
the Toffoli gate, after its inventor. If the first two inputs
are both 1, it inverts the third input. Equivalently, this maps
*a*,*b*,*c*into*a*,*b*,*c^(a&b)*. For example,`q0=1; q1=?; q2=0; CCNOT(q0,q1,q2);`would result in 50% 001 and 50% 111. CCNOT is a universal reversible logic gate; any reversible circuit can be built using only this type of gate.QUBIT q2 q1 q0 0 | 32 | 64 | CCNOT +-------@-------@ 32 | 32 | 64 |

`CSWAP(`*c*`,`*i0*`,`*i1*`);`-
The "controlled swap" gate is also known by the name of its
inventor, Edward Fredkin. If the first input is 1, then the second
and third inputs are swapped. Equivalently, this maps
*c*,*i0*,*i1*into*c*,*((!c)&i0)|(c&i1)*,*(c&i0)|((!c)&i1)*. It is a universal gate and has the additional unusual property that the number of 1s and 0s passing through the gate are conserved -- a feature sometimes called*billiard ball conservancy*. For example,`q0=0; q1=1; q2=?; CSWAP(q2,q1,q0);`would result in 50% 010 and 50% 101.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.

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.