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 ...'"

Comments

They may or may not succeed.

[SpanishInquisition]

Someone will have to observe them to get a definitive answer.

Some real info...article lacks it

[akiaki007]

Quite a lame article, IMO.

The article fails to make any real points. It's merely a PR article for HP and MIT.

Unlike classical bits, the qubit can be not just 0 or 1 but a superposition of both, in differing proportions.

Um...wrong. The qubit can be in the 0 or 1 state, but can also be both at the same time, and have varying rotations. Which is what makes it immpossible for us to decode them. It is the multiple state position that is what is interesting to us, and what does the parallel computing. We just don't know how to utilize it just yet. There have been various articles. Quibit.org is a great place to start reading up on this stuff. The IBM Almaden has a nice article that will actually tell you something useful.

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"?

DMCA vs Quantum computers

[roman_mir]

I wonder if DMCA would render building, selling and using such machines illegal, since quantum computers can be used to compute securitykeys for any encryption algorithms in a feasible amount of time?

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:Wait, wait.. a "computer"?

[Insount]

These are excellent questions. I'll try to answer them as far as my knowledge of the field allows, but please bear in mind that a good answer to some of the issues you raised would significantly enhance our state of knowledge.

First, two key facts.

• A quantum computer can run any classical algorithm. There is some overhead due the reversibility constraint and due to the practical need for error correction, but it's probably a low-order polynomial overhead at worst. In particular, a quantum computer can run a Universal Turing Machine. So, it's fully programmable in respect to classical programs.
• There exists a Universal Quantum Turing Machine that acts analogously to a classical Universal Turing Machine, i.e., lets a fixed quantum computer simulate run any quantum algorithm given a description of that algorithm as additional input. (It does so to finite accuracy, but the error can be made arbitrarily small)

So yes, we're talking about a fully programmable computer. However, this universaily means an increase in the computer size, so for practical reasons you'll see two shortcuts that undermine this universatily.

First, everything that can be done classically is done outside the quantum computer -- a quantum-classical dualism, if you wish. Suppose you have an algorithm that performs operation Q on some register, and applies it 200 times in a loop. You could put the loop counter as part of the quantum computer and program it to do an increment+test+Q operation. However, currently it's much cheaper to put the loop counter outside the quantum computer and simply tell it 200 times to apply a Q operation.

Second, the hardware is made as simple and specialized as possible, and optimized for a specific algorithm.

Now, these shortcuts are clearly present in the tiny quantum computers built so far (latest is IBM's, featuring 8 qubits), and will probably be used for quite some time. But that's mere practice, not theory.

OK, so how do you program this things? All quantum algorithms to date have been expressed using one of two formalisms: either using algebra in the mathematical "Hilbert space" that represents all the states the computer can be in, or using a "quantum circuit" which is just like a normal logical circuit (with gates like AND and NOT), except the gates are different -- in fact the gates are expressed as operations in the Hilbert space, as in the first approach, but it's often easier to see the overall picture if you combine simple gates using the circuit formalism. To be truthful, there's also the "and then you do that N more times, and then you measure first register" type of formalism. :-)

So you see, currently researchers are working at a level way below assembly language, and they're pretty happy about it because the algorithms are very small too. But what about higher-level representations? All efforts I've seen so far use quantum-classical dualism: you write a classical program that manipulates a quantum register (data), but the logic is purely classical. Some do it with a dedicated programming language, some with a class library, but the idea is the same (see a comprehensive list; all of these are mere simulators for now, of course).

Now, this is a very reasonable approach, but it seems rather halfway-there -- wouldn't it beneficial to allow quantum operations in flow control, not only in data? Well, we don't know yet. Currently there are very few "patterns" used in quantum computing, and none of them seems to easier to represent that way. It's hard to design a paradigm, let alone a language, for solving problems that don't yet exist. On the other hand, if we invent such a paradigm it might help us find new quantum algorithms. This is a vast open research area.

As for your speculations on how quantum computers will be used, the answers is yet again that we don't know. Here are the two extreme cases, both easily imagined and consistent with current knowledge. First, it could be that quantum computers will be found to be good for nothing except a few very specialized tasks, and that only a few RSA-cracking devices will be built by intelligence agencies at a prohobitive cost. On the other hand, it could be that a new class of quantum algorithms will be discovered that address more common needs, leading first to something in the college basement and later to a chip in everybody's computer. No one currently knows such these chips can be good for, if at all, though there's some intuition about what's more likely. I do venture to say that which of these possibilities becomes reality depends primarly on usefulness, since long-term prospects for mass-producton seem quite real, given sufficient demand.

I hope this clears things up a bit. I wish I could be more concrete, but it really takes a few hours to get a rough grasp of how these things really work, and a full-semester course to understand the interesting algorithms. Please don't hesitate to e-mail me if you want to discuss this further.

Scheduling challenges

[isomeme]

The project, announced last week, is part of a $25 million, five-year alliance launched in June 2000.

Of course, we won't know if the project worked or not until someone looks inside the lab in 2005.

Some of the challenges

[JPMH]

The Economist had a good article back in May about the state of the art (7 qubits), and some of the practical difficilties facing quantum computing.

"Dr Cory says that the program for factorising large numbers [400 digits] will require about 1,000 qubits simply to store the problem. But each of these qubits will require dozens of extra qubits for error-checking. That means that a useful computer will need tens of thousands of qubits to come up with a reliable answer. At seven and counting, that goal is a long way off. "

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)