MIT And HP Announce Joint Quantum Computer Project

MetaCow writes: "CNN is running this article which describes a joint effort between MIT and HP to build a quantum computer. Nothing expected any time soon, though: 'Quantum computing research is farsighted, and it may take 10 years to develop a fully operational quantum computer ...'"

Correction needed...

[RyanFenton]

Alright, a little 'bit picky', but

"While the classical bit can store any number between 0 and 255 on each of its eight bytes, ..."

Byte and bit should be reversed in this sentence fragment.

:^)

Ryan Fenton

Re:Correction needed...

[IvyMike]

Actually, that still doesn't make sense. Perhaps, "While the classical byte can store any number between 0 and 255 using all of its eight bits"?

Wait, wait.. a "computer"?

[mcc]

I am really curious as to what they mean by a "computer" in this specific case. I mean, i have heard that they've done quantum computers capable of picking phone numbers out of a list of four, and such. Which while a HUGE accomplishment is still rather primitive.. Is this just going to be another one of those? A simplistic test machine?

Or is this going to be, like, you know, a real *computer*? Something that can be given general calcuations and work through them? By using the word "computer", are they thinking that what they make is actually going to be something turing-complete, or at least comparable to ENIAC, or maybe even one of the bethemoths that used to sit in the basement of a college (where the computer science students would sign up for a block of time, then come by, drop off large stacks of punchcards, and then wander by the next day to collect the results of the program)?

More importantly, though-- and this is what i'm really wondering about-- if they actually are building a quantum computer that is capable of going into the realm of *running actual programs of some sort*.. what programming language will be used? How will these programs be written? What will the "machine code" look like, and how possible will it be to write software for this in high level languages? (I.e. will it be possible to do HLL abstractions as we do with current computers, at least at first, or will hand-optimisation be too necessary to allow things like "compiling"? I am not 100% sure what a "von neumann" architecture is, but as far as i understand things there are some implicit assumptions in the way that things like C work that kind of only make sense if computers are designed at least generally the way they are now. How different would the architecture of a quantum computer be in a general sense, and how much would current programming languages have to change to make sense in that architecture? Which language is in its current state closest to something that would make sense for the creation of programs on a quantum computer architecture-- C, Python/java, LISP/scheme, Haskell/ML, or APL/Mercury? Or something i've never heard of?

Or is it that special boards or setups whatever will have to be hardwired and specially set up for each specific task (although it will do those tasks really quickly), and this will not be a general-purpose computer capable of doing things like loading and executing an arbitrary written-as-software program?

And to get into the complete castles-in-the-air-speculation realm.. if it is a true general-purpose computer, are they going to try to give it, like, you know, an operating system with things like a kernel and process manager and networking capabilities? Are they going to just stick with letting programs be fed in manualy, or is the thing that they say will take ten years something that is at least realistic to think that you could build one, set it in the basement of a college, and let all the students telnet to it and build and run programs while using some equivilent of unix talk/write to message each other and tyrannical sysadmins constantly watch to see if anyone is playing quantum games so they can kill those processes? (I don't care if they acctually *do* that. Just if that's realistic, my mind is totally blown. I doubt it's realistic.)

Or is anything that may be completed so far in the future they can't really say what it will look like at this point?

I am deathly curious. I desire explanations, or at least links to academic webpages explaining, what sorts of things this computer would do and in what way we would go about giving it its programmatical instructions. Pleasepleaseplease i thank you in advance?

-mcc
If It Can't Process Church Numerals Then What Good Is It

Re:Interesting Implications

[arasinen]

All three points are more or less incorrect. Quantum computing does not necessarily improve every aspect of classical computing. The main difference is that classical computers are dead-on deterministic, while quantum computers are more of a probabilistic sort.

Claim #1: No encryption.

There is a quantum algorithm for factoring large numbers (Shor's algorithm). It will break RSA... but so what? There are elliptic curves and countless other methods of cryptography still available. Quantum computing might or might not be able to break these.

And then there is quantum encryption, ...

Claim #2: Improved compression

The concept of compression is a complex issue of information/communicaton theory. It applies to information, not to computing. Quantum computing is basically just computing; you might find be able to compute the compressed file faster, but no computational method can squeeze information beyond the theoretic limit.

The pi scheme mentioned here is totally unusable: it takes as much bits to represent the index as it takes to represent the data itself.

Claim #3: Faster computing

This too is slightly incorrect. There are some things that are faster to implement with quantum computing. Some things, like adding two to two are suitable for classical computers. Even the Shor's algorithm uses classical FFT at one step. I don't think it's certain that a quantum computer can solve NP-complete problems faster than classical computers.

Besides, for some things *the* optimal solution simply can't be expressed in any computer, quantum or classical. (Think for example the equation x^2 = 2. The answer can't be represented numerically in a computer; however, it can be approximated to as many digits as is necessary.)

Quantum computing does not necessarily imply massive parallel computing. For some applications something like this happens, but it's not the same as having n different computations running simultaniously; more like the the same computation running over with some variation.

Last of all, we don't get full certainty. The Shor's algorithm (IIRC) can give us an answer with very high probability, but that probability isn't 100%. (99.999% perhaps)

Re:Interesting Implications

[Insount]

Wrong on all three accounts, I'm afraid.

1. There are algorithms for efficient factoring and discrete log, so many public-key cryptosystems are can indeed be broken by a quantum computer. However, there is no known quantum algorithm for lattice-based cryptosystems such as NTRU. Moreover, for private-key cryptosystems all we have is a generic search algorithm that finds the key in time SQRT(2^n) where n is the key length, instead of 2^n for a brute force classical search. Thus by doubling the key length of the cipher, you make the work as hard for a quantum computer as the original cipher was for a classical computer.

2. As pointed out in previous replies, the offset will usually be longer than the data. This follows from a simple counting argument.

3. There is no evidnence that quantum computer can efficiently solve NP-complete problems. In fact, many quantum computing researchers believe there isn't one.

The current quantum algorithms are very tantalizing, but restricted in applicability. We really don't know yet what types of problems will benefit from quantum computing beyond the few known classes.