# Quantum computers - hypercomputers? **URL:** \ **Category:** Factual Questions\ **Created:** [October 24, 2006, 9:52pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766 "2006-10-24T21:52:45Z")\ **Posts on this page:** 19\ **Page:** 1
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [October 24, 2006, 9:52pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/1 "2006-10-24T21:52:45Z")
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? ---
**Author:** ![ted\_baskerville\_yahoo.com](https://avatars.discourse-cdn.com/v4/letter/t/ecd19e/32.png) [@ted\_baskerville\_yahoo.com](https://boards.straightdope.com/u/ted_baskerville_yahoo.com)\ **Post date:** [October 24, 2006, 10:00pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/2 "2006-10-24T22:00:33Z")
Some information from Wikipedia (beware): > [@](#): > > The power of quantum computers > > Integer factorization is believed to be computationally infeasible with an ordinary computer for large numbers that are the product of two prime numbers of roughly equal size (e.g., products of two 300-digit primes). By comparison, a quantum computer could solve this problem relatively easily. If a number has n bits (is n digits long when written in the binary numeral system), then a quantum computer with just over 2n qubits can use Shor’s algorithm to find its factors. It can also solve a related problem called the discrete logarithm problem. This ability would allow a quantum computer to “break” many of the cryptographic systems in use today, in the sense that there would be a relatively fast (polynomial time in n) algorithm for solving the problem. In particular, most of the popular public key ciphers could be much more quickly broken, including forms of RSA, ElGamal and Diffie-Hellman. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would have significant ramifications for electronic privacy and security. The only way to increase the security of an algorithm like RSA would be to increase the key size and hope that an adversary does not have the resources to build and use a powerful enough quantum computer. It seems plausible that it will always be possible to build classical computers that have more bits than the number of qubits in the largest quantum computer. If that’s true, then algorithms like RSA could be made secure by ensuring that keylengths exceed the storage capacities of quantum computers. > > There is one digital signature scheme that is secure against quantum computers: Lamport signatures. > > Perhaps not as surprisingly, quantum computers could also be useful for running simulations of quantum mechanics. This idea goes back to Richard Feynman (1982) who observed that there is no known algorithm for simulating quantum systems on a classical computer and suggested to study the use of quantum computer for this purpose. The speedup achieved by quantum computers could be just as large as for factoring. This could be a great boon to physics, chemistry, materials science, nanotechnology, biology and medicine, all of which are limited today by the slow speed of quantum mechanical simulations. For example, some modern simulations that are taking IBM’s Blue Gene supercomputer years would only take a quantum computer a matter of seconds. > > This dramatic advantage of quantum computers is currently known to exist for only those three problems: factoring, discrete logarithm, and quantum physics simulations. However, there is no proof that the advantage is real: an equally fast classical algorithm may still be discovered (though some consider this unlikely). There is one other problem where quantum computers have a smaller, though significant (quadratic) advantage. It is quantum database search, and can be solved by Grover’s algorithm. In this case the advantage is provable. This establishes beyond doubt that (ideal) quantum computers are superior to classical computers for at least one problem. > > Consider a problem that has these four properties: > > 1. The only way to solve it is to guess answers repeatedly and check them, > 2. There are n possible answers to check, > 3. Every possible answer takes the same amount of time to check, and > 4. There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order. > > An example of this is a password cracker that attempts to guess the password for an encrypted file (assuming that the password has a maximum possible length). > > For problems with all four properties, it will take an average of (n + 1)/2 guesses to find the answer using a classical computer. The time for a quantum computer to solve this will be proportional to the square root of n. That can be a very large speedup, reducing some problems from years to seconds. It can be used to attack symmetric ciphers such as Triple DES and AES by attempting to guess the secret key. But it is also easy to defend against, by doubling the size of this key. There are also more complicated methods for secure communication, such as using quantum cryptography. > > Regardless of whether any of these problems can be shown to have an advantage on a quantum computer, they nonetheless will always have the advantage of being an excellent tool for studying quantum mechanical interactions, which of itself is an enormous value to the scientific community. > > There are currently no other practical problems known where quantum computers give a large speedup over classical computers. Research is continuing, and more problems may yet be found. Nothing as dramatic as the eample the MIT guy, but it seems like it would have some huge advantages in limited cases. > **[Quantum computing](https://en.wikipedia.org/wiki/Quantum_computer)** > > A quantum computer is a computer that represents and processes information using quantum states. Quantum computations exploit phenomena such as superposition, interference, and entanglement. Quantum computers have the potential to complete some calculations exponentially faster than classical computers. For example, a large-scale quantum computer could break widely used encryption schemes and aid physicists in performing physical simulations. However, current hardware implementations of quantum... ---
**Author:** ![motomoon](https://avatars.discourse-cdn.com/v4/letter/m/a9adbd/32.png) [@motomoon](https://boards.straightdope.com/u/motomoon)\ **Post date:** [October 24, 2006, 10:01pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/3 "2006-10-24T22:01:59Z")
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. ---
**Author:** ![Exapno\_Mapcase](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/exapno_mapcase/32/1051_2.png) [@Exapno\_Mapcase](https://boards.straightdope.com/u/Exapno_Mapcase)\ **Post date:** [October 24, 2006, 10:02pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/4 "2006-10-24T22:02:30Z")
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. ---
**Author:** ![motomoon](https://avatars.discourse-cdn.com/v4/letter/m/a9adbd/32.png) [@motomoon](https://boards.straightdope.com/u/motomoon)\ **Post date:** [October 24, 2006, 10:03pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/5 "2006-10-24T22:03:46Z")
Perhaps quantum computers will help me by pressing preview… ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [October 24, 2006, 10:28pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/6 "2006-10-24T22:28:23Z")
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.) ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 24, 2006, 11:12pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/7 "2006-10-24T23:12:39Z")
> [@](#): > > 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. 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). ---
**Author:** ![carterba](https://avatars.discourse-cdn.com/v4/letter/c/85e7bf/32.png) [@carterba](https://boards.straightdope.com/u/carterba)\ **Post date:** [October 25, 2006, 12:37am UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/8 "2006-10-25T00:37:06Z")
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. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [October 25, 2006, 12:51am UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/9 "2006-10-25T00:51:28Z")
[QUOTE=motomoon] I’ve heard that the instant QCs become remotely feasible, every single cryptographic code or cypher will be obsolete. [/QUOTE] 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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 25, 2006, 8:00pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/10 "2006-10-25T20:00:17Z")
> [@](#): > > In fact, quantum cryptography would still be secure. 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. ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [October 25, 2006, 9:11pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/11 "2006-10-25T21:11:31Z")
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. ---
**Author:** ![Rysto](https://avatars.discourse-cdn.com/v4/letter/r/ecccb3/32.png) [@Rysto](https://boards.straightdope.com/u/Rysto)\ **Post date:** [October 25, 2006, 11:44pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/12 "2006-10-25T23:44:37Z")
[QUOTE=Dominic Mulligan] 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? [/QUOTE] If you mean this definition of [hypercomputation](http://en.wikipedia.org/wiki/Hypercomputation), which is the ability to solve problems that Turing Machines can’t solve, then as **Omphaloskeptic** has noted, the answer is no. ---
**Author:** ![KarlGauss](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/karlgauss/32/3713_2.png) [@KarlGauss](https://boards.straightdope.com/u/KarlGauss)\ **Post date:** [October 26, 2006, 3:01am UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/13 "2006-10-26T03:01:27Z")
[QUOTE=Chronos] 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. [/QUOTE] 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)? ---
**Author:** ![pulykamell](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/pulykamell/32/3166_2.png) [@pulykamell](https://boards.straightdope.com/u/pulykamell)\ **Post date:** [October 26, 2006, 8:01am UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/14 "2006-10-26T08:01:50Z")
[QUOTE=KarlGauss] 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)? [/QUOTE] 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. ---
**Author:** ![Rysto](https://avatars.discourse-cdn.com/v4/letter/r/ecccb3/32.png) [@Rysto](https://boards.straightdope.com/u/Rysto)\ **Post date:** [October 26, 2006, 1:32pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/15 "2006-10-26T13:32:52Z")
[QUOTE=KarlGauss] 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)? [/QUOTE] 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. ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [October 26, 2006, 3:18pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/16 "2006-10-26T15:18:52Z")
[QUOTE=Chronos] 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. [/QUOTE] 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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [October 26, 2006, 7:51pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/17 "2006-10-26T19:51:32Z")
> [@](#): > > 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. 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. ---
**Author:** ![KarlGauss](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/karlgauss/32/3713_2.png) [@KarlGauss](https://boards.straightdope.com/u/KarlGauss)\ **Post date:** [October 26, 2006, 8:10pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/18 "2006-10-26T20:10:37Z")
[QUOTE=Chronos] 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. [/QUOTE] 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? 🙂 ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [October 26, 2006, 8:28pm UTC](https://boards.straightdope.com/t/quantum-computers-hypercomputers/377766/19 "2006-10-26T20:28:52Z")
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.)