There are a ton of interesting thoughts in Wook's latest posting. I think we'll leave the bigger issues of quantum architecture for a later posting, though I'm looking forward to that. In the meantime I'll encourage you to Google on "quantum Turing machine" and noodle on which parts of the TM need to be quantum. For some concrete stuff on where we are with this, see the references from my Aqua recommendations page and my arithmetic page.
One bit of terminology we ought to straighten out. There are two types of qubits, "flying qubits" and static ones. Flying qubits are typically something like photons. They pass through devices that cause computation, something like data values pass through gates in a classical circuit. Many quantum computing technologies use static ones, such as quantum dots or the spin of atomic nuclei. In that case, a qubit is like a bit in a register, and the "gates" (often microwave pulses) feel more like instructions to a classical computer architect. The "program" is usually called a quantum circuit in either case.
So, rather than saying that a PDP-8 takes 10k gates for its CPU, the question is, how many bits of storage does it have? A machine that can run a program might want, say, a few kilobytes.
In most quantum computing proposals, an underlying assumption is that all qubits are equal; any qubit storage location can be manipulated in an arbitrary way. It's like they are all bits in a classical register; there is no RAM/register distinction and no "load" instruction. One of the few proposals that separates qubit storage from "action" locations is the scalable ion trap processor from the Wineland group at NIST. See http://qubit.nist.gov/ and the Kielpinski Nature paper. We in the Itoh group have been thinking about how to combine different storage technologies into a larger device, like the difference between cache and RAM. Haven't gotten very far yet.
This has already gotten long, so I'll leave simulation and the qubit flythrough for another posting.
So, I can tell where language is going to start screwing us:
ReplyDelete"something like data values pass through gates"
I'll talk for a second about PDP-8 architecture, just to
maintain my `old guy' cred:
each page consists of 128 (12 bit) words. These pages
interleaved program and data due to the addressing constraints
inherent in a 12 bit fixed word architecture. Off page
addressing was accomplished via indirection, ie: a fullword
(12 bit) pointer on the current page that pointed to something
in a 12 bit address space (absolute). So, the PDP-8
was limited to a total of 4k times 12 bits, or 48kbits
of total program and data space.
The PDP-8 is recognized as sort of a minimalist extension
of a classic Von Neumann architecture, featuring the
instructions ISZ (Increment, and Skip if result=0), and Jump.
A small number of additional operations compensated for the
lack of (infinite) address space and word length.
I looked at your animated GIFs, and while I found them
both lovely and cool, I admit to not following them.
Perhaps when the XFigs are present they will be easier to
track.
Extraneous Link: Python for POVRay
Okay, so we're looking for a quantum computer with application-level storage space of 48kilobits or less.
ReplyDeleteAt the moment, as I have said, the program is the classical portion of the machine, so we don't need to store that (yet).
Re: diagrams and animations -- I slightly updated the examples present on my arithmetic page, so that all of the filled-in cases have animations, GIFs of the circuit layout, XFIG, and Aqua source files.
Look first at the circuit GIF. Each horizontal line is a single qubit, and time flows left to right. Each vertical line segment is a gate. The small, dark dots indicate control lines, and the large, open circle is the target qubit.
If you look at the VBE adder, you can see that in the first time slot, a bunch of gates are executed concurrently on different qubits, then in later time slots only one or two are.
Compare this to the animation, in which each golden arch is a gate. At the beginning (of the VBE example), there is a lot of activity, then it dies down and you can see the carry ripple back and forth across the quantum register.
Now look at the Aqua source, and you'll see the gates, the CCNOTs (control-control-NOT) and the CNOTs (control-NOT). In my Aqua notation, the label at the beginning of a line of source is the time slot in which the gate is executed, and the time doesn't increment until you see the next such label.
Does this make any sense? Can you now mentally map the three representations of a quantum circuit to each other? If not, come back with more questions.