Quantum computers - hypercomputers?

Horizon has just been on British TV and they’ve had some guy from MIT on with his quantum computers making some pretty spurious claims. One of his claims was that a quantum computer can solve problems that no conventional computer can solve, even if the conventional computer is the size of the universe. I got the impression that he was trying to claim that quantum computers were capable of hypercomputation without coming right out and saying it.

Just what are the true computational powers of quantum computers? Is this guy full of it?

Some information from Wikipedia (beware):

Nothing as dramatic as the eample the MIT guy, but it seems like it would have some huge advantages in limited cases.

I really hope somebody is along to give the right answer on this, it’s really interesting to me and I feel that QC will be a really important development once the bugs are worked out. My very little grasp on what Quantum Computers do is they compute all the answers at the same time and the correct answer pops out. Good for certain types of calculations, cryptography for instance, but very poor for things that rely on user input like games. I’ve heard that the instant QCs become remotely feasible, every single cryptographic code or cypher will be obsolete.

Nope, this is completely correct, at least in theory. E.g., It would take a conventional supercomputer longer than the lifetime of the universe to factor a 1000 digit number, but this is theoretically trivial with a quantum computer.

Note the repeated use of “theory.” Nobody has shown that a quantum computer of any size can exist, and there may be theoretical, again, reasons for thinking it can’t. I have a feeling that quantum computing will come around at the same time as fusion power, i.e. always be 25 years off. I don’t trust anyone making huge claims right at the moment.

But the Board has some real experts on the subject, and I’m sure they’ll be around shortly.

Perhaps quantum computers will help me by pressing preview…

There are at least a couple of related questions here. One is whether a quantum computer can solve problems that a classical computer cannot solve, even in principle. The answer to this question, at least for quantum computers using standard quantum-mechanical models, is No. Anything you can do on a quantum computer you can simulate on a classical computer; in fact, you can simulate it in polynomial space. Formally, BQP, the set of problems solvable by a quantum computer in polynomial time (with bounded error probability), is a subset of PSPACE and is therefore certainly computable.

The second question is how much faster you can solve a problem using a quantum computer. The answer to this question is not fully known. As mentioned, quantum computers (if nothing prevents them from existing) are very good at factoring; they have an (almost) exponential time advantage over the best classical algorithm currently known. However, FACTORING has not been proved to be hard (it might be in P–i.e., solvable in polynomial time), so this is not a complete proof that quantum computers are exponentially faster. No one has found a polynomial-time quantum algorithm for a problem known not to be in P, so it’s possible (though it seems unlikely to me) that BQP=P. (Very little is known in general about inequality of complexity classes; it’s not even ruled out that P=NP.)

I think that’s a little too strong. Last I heard (a few years ago), a (very small) quantum computer had, in fact, been built, and had successfully factored the number 15. OK, so that’s not very impressive, but it serves as a proof of concept. Now, practical quantum computers, which can actually solve problems which are infeasible for classical computers, those are rather more sizzle than steak, and probably further away than fusion power plants. But we know that they can, in principle, work, since we’ve seen them, in principle, work.

But if we assume, as the MIT guy was doing, the existence of a practical quantum computer, his claims are correct. It isn’t too hard to construct a factoring problem so hard that a classical computer the size of the known Universe couldn’t solve it, using any known or suspected algorithm, in the lifetime of the Universe. But a much-smaller quantum computer could, in fact, solve that same problem in a practical time (seconds, or fractions of a second).

Following up on ** Omphaloskeptic’s** post, P = BQP would be the worst possible result for quantum computing: it would mean that a quantum computer could not solve anything that we cannot already solve on a “regular” computer. As he says, that remains a possibility. At this point the strongest thing that can be said about quantum computers over digital computers is that they can factor efficiently while digital computers cannot… but it has not been proven that factoring is definitely a “hard” problem. Personally, I suspect an efficient classical algorithm for factoring will be found someday.

The best possible result for quantum computing would be finding an efficient algorithm for a known hard (i.e. NP-Hard) problem. That would put NP inside BQP, and make NP-complete problems efficiently solvable in principle. I suspect this will not happen and that BQP is in NP instead.

Nope. One time pads are still going to be as secure as ever. Things like public key systems would be in danger though. In fact, quantum cryptography would still be secure.

Note that there has been some research that shows that quantum computing won’t “scale well,” to say they least. I consider it just another flavor of the month in Computer Science. I.e., 5 years from now, no one will be talking about it.

Quantum cryptography is still vulnerable to man-in-the-middle attacks, and is therefore only as strong as its validation scheme. So you need to either use an inefficient one-time-pad for validation, or accept a validation scheme based on “fragile” classical encryption.

Sounds like it will be hell to program for.

In the end it could end up being like a lot of hardware, where a lot of potential optimizations end up being most often never used because it can only be done at the assembler level. (Of course, if you’re working for the NSA and portability isn’t an issue, I guess that doesn’t so much.) It would be interesting though if it ended up spawning some language-additions that assumed a multistate int.

If you mean this definition of hypercomputation, which is the ability to solve problems that Turing Machines can’t solve, then as Omphaloskeptic has noted, the answer is no.

Isn’t one of the advantages of quantum cryptography that the system can be designed such that any attempt to eavesdrop on, or intercept, the message along the way will invariably reveal itself (i.e. disturb the quantum state)?

I am not an expert in any way on this, but I just recently completed reading a book on cryptography, and, as I understood it, you’re correct in your statement. Perhaps Chronos can expound.

Yes, but in a man-in-the-middle attack, the attacker intercepts the original message and replaces it with his own. So the message that the intended recipient looks fine, but it’s not coming from the right person.

There’s also the disctinction between quantum computers, which are still very rudimentary, and quantum computational techniques, some of which are in active use. There are at least two systems on the market today which implement quantum cryptography, and just the other day a European team quantum-teleported a mesoscopic amount of information.

Right-- With quantum encryption, you can be certain that only one person is receiving your transmission, but you can’t be certain of who that one person is. So you need some other method of verifying who you’re talking to, and that verification method can then be attacked. I worry that the hype about quantum cryptography might give its users a false sense of security, and lead to folks overlooking very real threats like this.

OK, I know nothing, really nothing about this, so please don’t laugh (too hard). Still, let me ask - couldn’t you (sender) provide in advance a unique collection of “correlated particles” to each of your potential recipients? When a real recipient gets your message, could he not then confirm his identity by demonstrating to you that he possesses particles with the expected properties? (And, if that info was intercepted and then sent on to you by the interceptor, the correlation would no longer hold?) I suppose you might even do it more simply using a one-time pad strictly for ID purposes, but we are talking quantum aren’t we? :slight_smile:

The man-in-the-middle attack is a problem with quantum cryptography, but it’s a problem with any encryption scheme that has sender and recipient separated. Even if Alice sends a one-time pad by courier to Bob, she has to worry that Eve has surreptitiously replaced the pad with her own one-time pad and is now intercepting all messages from Alice. Unless Alice and Bob have met at some time in the past and shared some secret that they can use for later verification (as, for example, KarlGauss proposes) there’s clearly no way to prevent this.

But this is probably not a big deal in practice. In order for Eve to succeed with a man-in-the-middle attack she has to be able to intercept and replace all communications between Alice and Bob. This is probably not realistic in most situations. It’s pretty hard, for example, to surreptitiously intercept all radio communications. With quantum cryptography Alice and Bob can send messages over a public channel (e.g., transmitting them in the clear, or putting them in a personal ad) which allow them to verify the security of the quantum channel, essentially using up some of their key bits to test for eavesdroppers. (The technique also works for classical OTPs and similar key-generation schemes. Basically, Alice chooses a random subset of n key bits and publishes their values. Unless Eve has been very lucky in choosing exactly that one of 2[sup]n[/sup] possible values for her substitute OTP, Bob knows something’s up. Of course these key bits are then discarded.)