Rod Van Meter (here) and I are
going to take a whack at a blog-based Dialog.
Well, two, actually. I'm going to post
some ideas about Systems and OS Architecture
for Quantum Computing Systems,
and Rod is going to post stuff about CG Visualization of same.
Hopefully we'll neither bore each other to death, or over-expose
our respective ignorances.
This evening during dinner, Tom, Harold, and I were making some guesses
at gate counts required to make interesting QC Systems. We've posited
about 100k gates builds a system of (traditionally) 8008/6502 complexity.
This is about the complexity that really starts to benefit from the presence
of an OS. By comparison, a PDP-8 can probably be built in about 10k (or
less) gates, and the operating system (OS/8) provided probably 1/4 of the
functionality of a contemporary BIOS.
So, I guess my first question is what does a QC gate simulator have
to provide to start building 'interesting' configurations?
Dexter
1 week ago
2 comments:
Mmm, I know where you're coming from. That's exactly the way I approached the thoughts at the beginning, and I wanted to do a "quantum operating system" for my thesis.
But, that way of thinking represents a fundamental misconception of how quantum computing systems are going to work for the foreseeable future. They will not be standalone machines; a quantum computer will be, effectively, a coprocessor to a classical machine. An array processor, perhaps; it will be a LOONG time yet before they are as powerful as, say, a Connection Machine 2, in terms of programmability.
You should, perhaps, think of a quantum computer as a Harvard architecture, in the original sense: separate memories for program and data. The program is held in a classical machine, and the data is held in a separate quantum memory (and in classical memory -- you need that to implement quantum error correction and other things).
When you get to really thinking about what it would mean to have a program stored in a quantum memory, your brain begins to really hurt. Imagine a program that is a *superposition* of many different programs, operating on a superposition of data, and branches going in different directions...ouch.
Keeping it simple, image a one-bit (one qubit) quantum program. It selects one gate to apply to a separate quantum data bit (qubit). There have been some studies of this. Apparently, it's tricky; since quantum gates can be represented as arbitrary rotations on a unit sphere, representing exactly which rotation you want could, in theory, require infinite resources (on either the quantum or classical side) to represent the analog rotation to infinite precision. In practice, of course, we keep it much simpler, using a set of gates that can approximate any arbitrary rotation in a reasonable polynomial time. One paper (by Hillery, Buzek, and Ziman) on this topic is at http://arXiv.org/quant-ph/0106088 (you may have to cut and paste, I don't know how do links in blog comments yet). That paper is pretty dense math, as are most of them on this particular topic.
A related topic might be Quantum Turing Machines (QTMs). I think Paul Benioff gets credit for inventing them, and David Deutsch contributed, as well. More on them some other time, but googling that will turn up useful stuff if you're interested.
For more on the current state of quantum computer architecture, you can read some of the papers list on my Aqua project recommendations page,
http://www.tera.ics.keio.ac.jp/person/rdv/quantum/recommendations.html
Oh, yeah, two tidbits...
First, if you're really interested in quantum computer architecture, I have a paper that's not online that you might be interested in; send me email. It's submitted to a conference, should hear back around the end of January whether or not it's accepted.
You can't "simulate" a quantum computer with 100k qubits. You might be able to figure out how to program it, learn a few things about its error characteristics, etc., but no way you're going do a real simulation of the quantum state evolution.
Naively, an N-qubit quantum computer has 2^N possible states, each of which needs to be represented by a complex (floating point) number in a simulation. So, if you assume 64 bit FP numbers, two per coefficient (complex number), 2^N coefficients, then 1GB of RAM is good to hold the coefficients for 26 qubits. And the RAM size doubles for every qubit you add. Doing 30 qubits would take 16GB.
And like I said, that's actually an excessively naive take on this; when the physicists do simulations, they carry around a lot more information than that. The above would be for a "state vector" representation of the machine, which is for pure states, unentangled with the outside world. The physicists are usually after something more like the "density operator" representation, which is a square array of the above -- that is, a 2^N by 2^N array. Yowza! The density operator tells them more about problems keeping the state of the system clean, errors in measurement, etc. There are lots of people working on various simulations; one such person is Cyrus Master, who is a student of Yoshi Yamamoto's at Stanford. I think he told me (working from memory from several months ago) that he uses O(6^N) bytes in his simulation.
Bottom line: full physics simulation of more than 12-14 qubits will require heroic effort. It will require a much better physical understanding of error processes for a given technology, too. But, it's clearly a necessary area, and one where I think computer systems folks have things to contribute.
Post a Comment