Bruce Schneier's latest blog entry points out an interesting analysis of how quantum computing will affect public encryption. The author takes a look at some of the mathematics involved with using a quantum computer to run a factoring algorithm, and makes some reasonable assumptions about the technological constraints faced by the developers of the technology. He concludes that while quantum computing could be a threat to modern encryption, it is not the dire emergency some researchers suggest.
While I'm critical of Schneier's work in general security consulting, he is still a god in the cryptography world. His book Practical Cryptography [amazon.com] is a friendly guide to encryption that doesn't assume too much knowledge of the heady math involved. Plus, the man invented Blowfish, one of the most popular and fast algorithms around.
Perhaps you would like to read again what NP-complete [wikipedia.org] means: being able to quickly check (read: in polynomial time) whether a solution is right or not by using a deterministic algorithm. Quantum computers are non-deterministic, and that's why they can be used to factor large integers. "Check all periods of r so a^r=1 (mod N) at the same time" certainly isn't deterministic.
The darned things would be like oracles, just ask them any super hard question, like how to prove Fermat's Last Theorem, and they'd just spit out the answer. The things would be like talking directly to God. Is that even remotely possible? I don't think so. Factoring numbers is just not as hard as any NP complete problem.
You might as well conclude that grass is purple, for all the sense that paragraph makes.
I think you are mistaken. It has been a while, but I remember NP like this:
What you described is the property "NP-hard". For a problem to qualify as NP-complete, it is also neccessary that an algorithm that can solve this problem can also be used to solve every other NP-hard problem, with only an additional transformation of its input and output in polynomial time.
Prime factoring is not NP-complete. There is as far as I know no transformation for the input and output of a prime-factoring algorithm, that would allow it to solve other np-hard problems as well.
If prime factoring was np-complete, then since a quantum algorithm is known for it, it would be certain that a quantum computer could also solve all other np-hard problems.
As far as I know, no quantum algorithm with polynomial time has been found for any NP-complete problem. So we do not know whether a quantum computer could do this
Parent post is absolutely correct; grandparent is absolutely wrong. Read Scott Aaronson's blog [scottaaronson.com] to get a clue about quantum computing.
Also read about Schor's algorithm, which is the known algorithm to factor large numbers in log(n) time *if your quantum computer has enough entangled qubits to represent the number*. Again, though, remember that FACTORING IS NOT NP COMPLETE, only NP hard. Other NP hard problems are harder than factoring (for example, any NP complete problem;-).
Again, though, remember that FACTORING IS NOT NP COMPLETE, only NP hard.
Wrong (emphasis mine). Factoring is in NP but not (known to be) NP complete. Which means that factoring is not (known to be) NP-Hard. (The only NP-hard problems in NP are NP-Complete problems) A more colloquial way to explain it is that NP-hard problems are at least as hard as NP-complete problems, yet factoring is "easier" than NP-complete problems.
Also read about Grover's algorithm, which is a general algorithm to solve NP complete problems, and which HAS BEEN PROVEN TO BE THE FASTEST way to solve the NP complete problem of lookup in an unordered dictionary. Grover's algorithm finds the answer in n^1/2. Obviously if the fastest algorithm to solve a specific NP complete problem is n^1/2, you cannot have a way to solve all NP complete problems in log(n).
Do you even know what you are talking about? Grover's algorithm is not used to solve NP complete problems!! You've already said it -- it's a way to look up an
Actually, quantum computers don't work quite like that. The result of a quantum computer computation is the superposition of all the possible results. At the end, you have to collapse the wave function, and you wind up with a specific result, randomly from all the possible results. To factor large integers, you have to rotate the cubits 90 degrees after doing the computation, and somehow that's similar to doing an FFT. If you run the computation many times, statistically you get results bunched into clu
I think the other posters don't seem to understand the difference between NP and NP-complete. NP complete means that in addition to the answer being verifiable in polynomial time, solving *any* NP-complete problem in polynomial time would provide a polynomial-time solution to all other NP-complete problems. Factoring is in NP, but nobody has yet proven that it is NP-complete. Thus, traveling salesmen and knapsack packers won't be putting quantum computers on their wish lists...
Bruce didn't actually write that article. He only linked to it on his blog, which isn't particularly relevant. And, although Bruce is a brilliant cryptographer, he doesn't know squat about quantum computers, nor does the person that wrote that article. One of the most glaring errors is corrected in comment posted on the article page. Besides that, his argument isn't completely sound. The biggest problem with quantum computers isn't managing to build one with a tons of quantum gates, it's getting the error rate down on the components. If you do that, you ought to be able to build as many gates as you want with enough effort and money. The author's argument seems akin to saying we couldn't possibly build a 100-billion transistor count processor today. We could, its just going to be very expensive and you're not going to mass-produce it.
Right now a lot of people working in the field say quantum computers are about 40 years off. The scary thing though is how its likely to play out. For a few decades quantum computers will likely remain "40 years off" (in the fusion sense), but then someone is going to figure out how to get the error rates below threshold, and then quantum computers will be only 10 years away. That doesn't give us much time to stop using our favorite public key algorithms. That's too bad for nTru; (they have a public key system that is likely resistant to quantum computers), their patents will be long expired.
Please mod parent up. He makes two excellent points: 1st that Schneier did not write the essay and basically has nothing to do with it. And 2nd, that the essay is completely wrong, as pointed out by the 1st comment replying on the essay page. Shor's algorithm will not take 72*k^3 qubits or gates, it takes about k qubits and then goes through O(k^3) steps to get the answer. Everything about the posting is wrong.
It should be noted that this is not Schneier's writing, this is just a blog post that he posted about in his blog. He may find it interesting and noteworthy, but it is not his material.
Your data is both encrypted and unencrypted at the same time, only reverting to one state or the other when you observe it and collapse the waveform. There is also, if I read this correctly, some chance that it will turn into a cat.
... more like guaranteed employment for security experts everywhere!
The day PKIs that use factoring or discrete logs become easy to crack is
the day when there's going to be a lot of tremendous amount of money
spent on stop-gap security measures until someone figures out something
new...
The day PKIs that use factoring or discrete logs become easy to crack is the day when there's going to be a lot of tremendous amount of money spent on stop-gap security measures until someone figures out something new...
The day PKIs that use factoring or discrete logs become easy to crack is the day when there's going to be a lot of tremendous amount of money spent on stop-gap security measures until someone figures out something new...
I imagine one-time pads will come back in style.
One time pads are replacements for symmetric encryption (both sides use the same key), not asymmetric encryption. You cannot authenticate a server to multiple clients using one time pads for instance. Everybody would have the one time pad, so everybody could pose as the server. Anyway, there *are* asymmetric algorithms that should be safe against crypto analysis using quantum computing. There is no need to go distributing Blu-Ray disks filled with random valued bits (one disk per application and user) just yet.
There's certainly no reason to go back to one-time pads. Basically all of the symmetric encryption algorithms are (mostly) quantum resistant. But, you do get a square root speed-up for attacking symmetric systems by using Grover's algorithm on a quantum computer. So, if you want to make sure you're still safe, you have to double your key length. That's not so bad, and certainly much better than using one-time pads.
And, as you said, there are asymmetric algorithms that should be resistant to quantum co
I am crypto-tech naive. What's the problem with using one-time pads and having every "relationship" share a pad? (ie: When I open an account with my bank they give me a key-fob with my one time pad on it. When I log into the bank website it uses the pad to authenticate me.) Of course, setting up a relationship will be a bit more expensive...
The problem is all the legacy data drifting around out there on old machines that use crypto systems that can be trivially broken. If you can find a dump of old hard drives that weren't very carefully wiped because "all the data was encrypted," you might have a gold mine.
"I am crypto-tech naive. What's the problem with using one-time pads and having every "relationship" share a pad?" Well, just think about all the SSL enabled sites out there, and remember you will now have a N * N (client * server) number of relations that need to setup a symmetric key (which is what a one time pad is, basically). Also note that you don't have a certificate infrastructure, so you cannot just go to VeriSign or any other trusted third party and buy a certificate from there. You cannot download
No, this is why you don't use secret key system like 3DES or AES. Essentially, the number of keys you need to distribute scales with the number of pairs of communicating parties. If you have N parties all wanting to communicate with each other, that's O(N^2) keys. This is fairly unlikely, though. If you have, say, S servers (banks, etc.) and C clients, it's more like O(S*C) -- though a client-server pair may separate keys for different tasks. One-time pads cannot be reused. That's why they're called one-time
Every bit of traffic needs a bit from your one time pad. That limits how long the pad lasts. Yes there are storage solutions that store gigabytes but if you're using it for a lot of data it's used up fast. An OTP has to be one time use or you might as well use billboards. Both parties need the same pad. You need to be able to ship that pad to them or hand it to them and be sure no one snooped or snoops the OTP. If the pad is compromised how do you inform the other party it has been tainted? Unless you go tal
Public key crypto solves the main key distribution problem of symmetric crypto. One time pads have the worst key distribution issues of all crypto! So, no, one time pads won't be making any kind of come back due to this.
quantum computers fail at NP-hard problems. But no one has made a cryptosystem for which breaking is NP-hard. So the eventual transition is going to be a bit tricky.
As far as I know, it is not known whether quantum computers can solve NP-hard problems in polynomial time. To say that they fail at NP-problems may be premature.
As far as I know, it is not known whether quantum computers can solve NP-hard problems in polynomial time. To say that they fail at NP-problems may be premature.
Seeing as it hasn't even been proven that P != NP for ordinary computers, it's very premature.
Well, it is conceivable that NP is solvable using quantum computers in poly time, while pretty much everyone believes that P!=NP for ordinary computors.
I mispoke. No current algorithms are known for solving NP problems fast with a quantum machine, and it is suspected none exist.But no proof of the converse exists. However, using a nonlinear operator permits NP complete problems to be solved in polynomial time with small error. So it's more pessimistic then I thought.
I think the fear is that by the time we get around to having decent PKI for stuff like credit cards etc, quantum computing will bust everything wide open. PKI is the only practical method of identity management these days, and while algorithms in the PKI are being tweaked, they are all pretty much based on the same principals, which quantum computing is a real threat too.
This calculation illustrates a good point about the difference between asymptotic analysis of algorithms and real-world implementation of the same algorithsm. Computer science defines "efficient" as "bounded polynomially in terms of the input size". In practice, even if polynomial has a small degree (like a cubic) it already means that the resource rquirements are very large. Theory and practice are only the same in theory.
It's way too early to make predictions based on trends. Quantum computing is in its infancy. We haven't even built anything that could/should really be called a working quantum computer (yes, I know we factored 15). We're going to see revolutionary changes to the field, not just evolutionary. So, every once in a while we're going to see great leaps forward, followed by a period where people just improve upon that idea. Its going to take a lot of revolutionary ideas to get a practical quantum computer,
I tend to agree. When promising new technologies take too long to develop, by the time they become practical they are often supplanted by something else. We will have both, since our civilization's need for both more energy and more processing power is going continue unabated for a long time.
We may never have either nuclear fusion or quantum computing, as currently envisioned. As you say, it's impossible to predict. All we can say with some assurance is that we'll probably figure out something that will
Well, even if it were to be true that quantum computing algos can break the existing encryption algos, I think it is being paranoid for two reasons: (1) Quantum computing is not yet mainstream and I doubt if mischief mongers (aka thieves who wish to break into financial sustems) have the wherewithal today to work with quantum computing algos, and (2) By the time QC moves to anywhere near mainstream, I have little doubt that encryption methods would have handsomely moved along too.
Presumably the article is alluding to Shor's Alorithm [wikipedia.org], which is a a method to factorize integers which uses quantum computation to yield a worst-case complexity significantly better than any existing deterministic methods.
If that's the case, it's probably worthwhile to discuss Pollard's Rho algorithm [wikipedia.org], which has a poorly understood worst-case complexity (as a Monte Carlo method), but has a potential average case complexity that is comparable to the quantum.
What I get out of the article is that he seems to be saying that quantum encryption technology that could effectively factor numbers of the size we use for effective public key cryptography is far enough off that it isn't going to be a problem anytime soon. But isn't that reasoning just postponing, rather than actually dealing with the problem?
It appears from the first comment on the post that it's likely that this post isn't really accurate. Shor's factoring algorithm is O(k) in number of qbits and O(k^3) in number of operations. This doesn't mean that the number of gates in the quantum computer is O(k^3), it means that the time it takes to execute the algorithm is O(k^3). It appears this discrepancy may be a result of not agreeing on terminology. I haven't checked this out thoroughly, but glancing at my copy of Mermin's "Quantum Computer Scienc
If we can use quantum computers to decrypt.. Why can't we use them to come up with an equally mind-blowing way of encrypting? I don't mean single photon secure fibre channel stuff. That seems fairly impractical to deploy to the whole internet.
I mean, why can't some mathematical genius come up with a new encryption algorithm that you can only implement on a quantum computer, and which produces a cipher text so random that it can't be decrypted even by another quantum computer unless it knows the secret.
Since the Sci Am article is subscription-only, you may want to check the complete draft-version of Scott Aaronsons article for Scientific American (before editors changes) here:
(The blog is often quite technical as you can expect but funny and worth following just for its non-techical bits. Circumcision and Australian models are also discussed on frequent basis.)
Heavier-than-air flight is impossible; a train will never go faster than a person can run or the passengers will asphyxiate; there is no reason why anyone would want a computer in the home; etc. [wilk4.com]
It's a bad idea to discount future technological advances wholesale.
In what ways is this a problem? I'm not knowledgeable about cryptography. My only knowledge and understanding (due to complex math involved) is Simon Singh's Code Book. I would consider that if Quantum computers exist, it would pose a serious threat to security and military applications as your enemy would always be listening. I don't know if E-Commerce would grind to a halt, since governments would initially be the only ones to afford it. I would think that instead of hitting e-commerce the better thing to
He makes an extremely cogent argument, but it is hampered by the lack of information we have about the state of the art in quantum computers.
Domestic spying is massively popular with western governments right now, and if you think that the NSA and GCHQ aren't doing secret research into quantum computers you are out of your mind. Furthermore, it is a commandment of signals intelligence that you do not let the enemy know you have broken his code - and in this case the enemy is us. We have no idea how far along they are. We have no idea what the generational length is for the quantum computers that are certainly being developed in secret.
Basically, this essay could be published and make just as much sense either before or after a critical breakthrough had been made by one of the aforementioned agencies and they hadn't told anyone. Thus, we have no way of knowing if we are already past that point or not.
Given that it has already been shown that quantum computers are not infallible, would it not make sense now to start working on encryption methods designed to flummox them?
It's just a matter of changing the whole infrastructure to something else, not the end of the world.
Yes, but what about the matters you've already encrypted? Early buzz around PGP was that it would supposedly take millions of years to decrypt even a single message. For those people who encrypted their private communications, it is a big shock that all your secrets may be read in just a few years.
you disconnect it. First posts are encrypted by mod down, taken out of sight.
The best encryption is disconnection. Its unbreakable even by quantum computers to the nth power.
the next best is perhaps a sequence of seemingly unrelated actions followed by a false positive... or other such use of seemingly unrelated data/actions.
A few might remember the seemingly different things you could do to cause a developer hidden message to come up on the Amiga.
I'm afraid you'll have to look those physics books back up.
Although QM computers do use basic entanglement for creating superpositions, understanding Shor's algorithm (the one everyone is concerned about since it's factoring in polynomial time) is mostly just understanding QM superposition. Entanglement gives generic QM computers great parallel processing power by superposition by explaining how QM probability wave combine under superposition, but Heisenberg limits the computing power of a QM computer in a non-trivial way as well because after you collapse the wave functions by measurement you give up the parallel processing enabled by Entanglement (e.g., if you peek inside the oven, it stops working, if some of the heat leaks out of the oven even with the door closed, it doesn't work as efficiently, the oven being the QM computer).
FWIW, Shor's algorithm essentially converts factoring into a sequence period finding exercise. You might imagine that that's something easy to do if you had a machine which given a bunch of superimposed waves with a certain modulo structure could tell you the period (hint the ones that don't modulo with a specific period with self interfere and measure as zero, where the one with that period with self-reinforce). With a QM computer you do this all in parallel with superimposed probability waves and when you measure it, the highest probability one you measure is the one that doesn't self-interfere (the ones that self-interfere has probability near zero). Basically this measurement is wave function collapse which doesn't actually depend on entanglement or heisenberg to understand (although it does require you to believe in QM wave functions and measurement operators).
Entanglement is really a strange artifact of QM that explains probability correlations that you see in QM experiments that can't be explained classically. It's really more of an artifact of the existance of probability amplitude waves (the QM wave function) rather than an effect that directly enables the QM computer. Of course if you didn't have QM wave functions you wouldn't have a QM computer so I guess that's a chicken and egg scenario. Entanglement is like the "carburator" function of the QM computer. The QM computer uses superposition of QM wave functions to work and when you have more than one QM wave function, they get entangled when you start superimposing wave functions and the way the waves entangle helps you compute in parallel so it's important to understand how these waves entangle.
Heisenberg's principle is a consequence of wave function collapse (measurement) which also limits the QM computer (this limiting effect is often called QM de-coherence). Heisenberg isn't required by a QM computer when it's computing, but you need to see the result somehow so when you measure the result, one of the side effects is the Heisenberg principle (although that's also a chicken-egg problem, since HP is a consequence of QM wave function collapse and w/o QM there's no superposition computing). The closest explanation I can think of is that Heisenberg's principle is the "heat" caused by friction of the QM computer. You need friction to stop the computer to read out the result, but at the same time you can't get rid of a little friction while it's running either (causing de-coherence). The side effect of this friction is heat.
You may have a personal opinion that superposition is a "nice way of doing statistics using discrete values for covering the not so discrete results of experiments", but there is experimental evidence that your personal opinions is at odds with physical reality. As QM computers that do QM computing (including IBM's NMR experiment which implemented shor's algorithm) have already been implemented it's hard to refute that something non-classical is going on.
It may be that in the end, QM is total malarky and there's some other weird unexpected thing going on, but there are mountains of evidence that whatever is going on, it isn't as simple as "hidden variables"
1. Entanglement. Is this a fact or a theory? Looking on web I found only few experiments with some possible loopholes. I found the principle hard to grok.
2. Heisenberg principle. It mainly states that observing an object you are changing the state of the object. The Heisenberg example from wikipedia is using a photon for measuring the position of an electron and the photon is changing the position of electron. What is happening if you are using a smaller particle that is not impacting the electron so much? Are you going to change the constant? Looks mostly like a limitation from a time when the atom was considered to be indivisible.
The Wikipedia entries are written from the perspective of a physicist, so they aren't going to be much use to laypeople.
1. Entanglement: It is fact. If you send a photon through a certain type of non-linear crystal, two photons will emerge that are entangled quantum mechanically. To truly understand this requires some knowledge of quantum mechanics, a basic introduction to QM and entanglement can be found here [ipod.org.uk] and here [davidjarvis.ca] if you care to learn more.
2. Heisenberg principle: You inadvertently stumbled onto the problem yourself, kinda. When trying to measure the position of the electron, you use a high energy photon and this photon. When this high energy photon interacts with the electron it alters the velocity of the electron, so you know less about the velocity of the electron. When trying to measure the velocity of the electron, you use a low energy photon. This low energy photon measures the velocity well, but it moves the electron a little bit, so you don't know its position. This issue is the essence of the Heisenberg uncertainty principle.
2. Heisenberg principle: You inadvertently stumbled onto the problem yourself, kinda. When trying to measure the position of the electron, you use a high energy photon and this photon. When this high energy photon interacts with the electron it alters the velocity of the electron, so you know less about the velocity of the electron. When trying to measure the velocity of the electron, you use a low energy photon. This low energy photon measures the velocity well, but it moves the electron a little bit, so y
Schneier knows his stuff (Score:4, Informative)
Re:Schneier knows his stuff (Score:5, Informative)
Parent
Re:Schneier knows his stuff (Score:5, Insightful)
The darned things would be like oracles, just ask them any super hard question, like how to prove Fermat's Last Theorem, and they'd just spit out the answer. The things would be like talking directly to God. Is that even remotely possible? I don't think so. Factoring numbers is just not as hard as any NP complete problem.
You might as well conclude that grass is purple, for all the sense that paragraph makes.
Parent
Re:Schneier knows his stuff (Score:4, Informative)
What you described is the property "NP-hard".
For a problem to qualify as NP-complete, it is also neccessary that an algorithm that can solve this problem can also be used to solve every other NP-hard problem, with only an additional transformation of its input and output in polynomial time.
Prime factoring is not NP-complete. There is as far as I know no transformation for the input and output of a prime-factoring algorithm, that would allow it to solve other np-hard problems as well.
If prime factoring was np-complete, then since a quantum algorithm is known for it, it would be certain that a quantum computer could also solve all other np-hard problems.
As far as I know, no quantum algorithm with polynomial time has been found for any NP-complete problem. So we do not know whether a quantum computer could do this
Parent
Factoring IS NOT NP COMPLETE (Score:3, Informative)
Read Scott Aaronson's blog [scottaaronson.com] to get a clue about quantum computing.
Also read about Schor's algorithm, which is the known algorithm to factor large numbers in log(n) time *if your quantum computer has enough entangled qubits to represent the number*. Again, though, remember that FACTORING IS NOT NP COMPLETE, only NP hard. Other NP hard problems are harder than factoring (for example, any NP complete problem
Also read about Grover's algori
Re: (Score:3, Informative)
Again, though, remember that FACTORING IS NOT NP COMPLETE, only NP hard.
Wrong (emphasis mine). Factoring is in NP but not (known to be) NP complete. Which means that factoring is not (known to be) NP-Hard. (The only NP-hard problems in NP are NP-Complete problems) A more colloquial way to explain it is that NP-hard problems are at least as hard as NP-complete problems, yet factoring is "easier" than NP-complete problems.
Also read about Grover's algorithm, which is a general algorithm to solve NP complete problems, and which HAS BEEN PROVEN TO BE THE FASTEST way to solve the NP complete problem of lookup in an unordered dictionary. Grover's algorithm finds the answer in n^1/2. Obviously if the fastest algorithm to solve a specific NP complete problem is n^1/2, you cannot have a way to solve all NP complete problems in log(n).
Do you even know what you are talking about? Grover's algorithm is not used to solve NP complete problems!! You've already said it -- it's a way to look up an
Re: (Score:3, Informative)
Re: (Score:3, Interesting)
While solving NP-complete i
Re:Schneier knows his stuff (Score:5, Interesting)
Right now a lot of people working in the field say quantum computers are about 40 years off. The scary thing though is how its likely to play out. For a few decades quantum computers will likely remain "40 years off" (in the fusion sense), but then someone is going to figure out how to get the error rates below threshold, and then quantum computers will be only 10 years away. That doesn't give us much time to stop using our favorite public key algorithms. That's too bad for nTru; (they have a public key system that is likely resistant to quantum computers), their patents will be long expired.
Parent
Re: (Score:3, Informative)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3, Insightful)
Re:Schneier knows his stuff (Score:5, Funny)
Hope that clears it up for you...
Parent
Re: (Score:2)
But you won't know if it's alive or not until you look inside the box.
not exactly a "threat" (Score:4, Insightful)
The day PKIs that use factoring or discrete logs become easy to crack is the day when there's going to be a lot of tremendous amount of money spent on stop-gap security measures until someone figures out something new...
Re: (Score:2)
I imagine one-time pads will come back in style.
Re:not exactly a "threat" (Score:4, Insightful)
I imagine one-time pads will come back in style.
Parent
Re: (Score:3, Informative)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3, Insightful)
Well, just think about all the SSL enabled sites out there, and remember you will now have a N * N (client * server) number of relations that need to setup a symmetric key (which is what a one time pad is, basically). Also note that you don't have a certificate infrastructure, so you cannot just go to VeriSign or any other trusted third party and buy a certificate from there. You cannot download
Re: (Score:3, Informative)
One-time pads cannot be reused. That's why they're called one-time
You have to get the pads to the other person... (Score:3, Insightful)
If you have a way of transmitting the pads securely then you could just use the same system to transmit the messages - no encryption needed!
Re: (Score:3, Informative)
Both parties need the same pad. You need to be able to ship that pad to them or hand it to them and be sure no one snooped or snoops the OTP. If the pad is compromised how do you inform the other party it has been tainted? Unless you go tal
Re: (Score:3, Informative)
Well, lucky for us (Score:2)
Re: (Score:3, Interesting)
As far as I know, it is not known whether quantum computers can solve NP-hard problems in polynomial time. To say that they fail at NP-problems may be premature.
Re:Well, lucky for us (Score:5, Informative)
Parent
Re: (Score:2)
Well, it is conceivable that NP is solvable using quantum computers in poly time, while pretty much everyone believes that P!=NP for ordinary computors.
Re: (Score:3, Interesting)
the fear (Score:2, Insightful)
"polynomial time" (Score:4, Informative)
Quantum computing is no threat because... (Score:3, Informative)
Re: (Score:2, Interesting)
Re: (Score:3, Informative)
We may never have either nuclear fusion or quantum computing, as currently envisioned. As you say, it's impossible to predict. All we can say with some assurance is that we'll probably figure out something that will
Encryption will move on, too (Score:2, Interesting)
Shor's Algorithm (Score:4, Interesting)
If that's the case, it's probably worthwhile to discuss Pollard's Rho algorithm [wikipedia.org], which has a poorly understood worst-case complexity (as a Monte Carlo method), but has a potential average case complexity that is comparable to the quantum.
Am I missing something? (Score:2)
Incorrect interpretation? (Score:2, Informative)
Use quantum computers to ENCRYPT (Score:2)
Why can't we use them to come up with an equally mind-blowing way of encrypting?
I don't mean single photon secure fibre channel stuff. That seems fairly impractical to deploy to the whole internet.
I mean, why can't some mathematical genius come up with a new encryption algorithm that you
can only implement on a quantum computer, and which produces a cipher text so random that it
can't be decrypted even by another quantum computer unless it knows the secret.
Does anyo
Complete article (without subscription) (Score:3, Informative)
http://www.scottaaronson.com/writings/limitsqc-draft.pdf [scottaaronson.com]
Scott posted it on his blog on 2/18, see http://www.scottaaronson.com/blog/ [scottaaronson.com]
(The blog is often quite technical as you can expect but funny and worth following just for its non-techical bits. Circumcision and Australian models are also discussed on frequent basis.)
Part of a long lineage of naysayers (Score:2)
It's a bad idea to discount future technological advances wholesale.
In what ways is this a problem? (Score:2)
I would consider that if Quantum computers exist, it would pose a serious threat to security and military applications as your enemy would always be listening. I don't know if E-Commerce would grind to a halt, since governments would initially be the only ones to afford it. I would think that instead of hitting e-commerce the better thing to
There is a problem with this (Score:5, Interesting)
He makes an extremely cogent argument, but it is hampered by the lack of information we have about the state of the art in quantum computers.
Domestic spying is massively popular with western governments right now, and if you think that the NSA and GCHQ aren't doing secret research into quantum computers you are out of your mind. Furthermore, it is a commandment of signals intelligence that you do not let the enemy know you have broken his code - and in this case the enemy is us. We have no idea how far along they are. We have no idea what the generational length is for the quantum computers that are certainly being developed in secret.
Basically, this essay could be published and make just as much sense either before or after a critical breakthrough had been made by one of the aforementioned agencies and they hadn't told anyone. Thus, we have no way of knowing if we are already past that point or not.
Given that it has already been shown that quantum computers are not infallible, would it not make sense now to start working on encryption methods designed to flummox them?
Re: (Score:3, Insightful)
Yes, but what about the matters you've already encrypted? Early buzz around PGP was that it would supposedly take millions of years to decrypt even a single message. For those people who encrypted their private communications, it is a big shock that all your secrets may be read in just a few years.
And the answer is ..Re:So how do you encript ..... (Score:3, Funny)
The best encryption is disconnection. Its unbreakable even by quantum computers to the nth power.
the next best is perhaps a sequence of seemingly unrelated actions followed by a false positive... or other such use of seemingly unrelated data/actions.
A few might remember the seemingly different things you could do to cause a developer hidden message to come up on the Amiga.
Re:Does exist any quantum computer proven to work? (Score:5, Informative)
Although QM computers do use basic entanglement for creating superpositions, understanding Shor's algorithm (the one everyone is concerned about since it's factoring in polynomial time) is mostly just understanding QM superposition. Entanglement gives generic QM computers great parallel processing power by superposition by explaining how QM probability wave combine under superposition, but Heisenberg limits the computing power of a QM computer in a non-trivial way as well because after you collapse the wave functions by measurement you give up the parallel processing enabled by Entanglement (e.g., if you peek inside the oven, it stops working, if some of the heat leaks out of the oven even with the door closed, it doesn't work as efficiently, the oven being the QM computer).
FWIW, Shor's algorithm essentially converts factoring into a sequence period finding exercise. You might imagine that that's something easy to do if you had a machine which given a bunch of superimposed waves with a certain modulo structure could tell you the period (hint the ones that don't modulo with a specific period with self interfere and measure as zero, where the one with that period with self-reinforce). With a QM computer you do this all in parallel with superimposed probability waves and when you measure it, the highest probability one you measure is the one that doesn't self-interfere (the ones that self-interfere has probability near zero). Basically this measurement is wave function collapse which doesn't actually depend on entanglement or heisenberg to understand (although it does require you to believe in QM wave functions and measurement operators).
Entanglement is really a strange artifact of QM that explains probability correlations that you see in QM experiments that can't be explained classically. It's really more of an artifact of the existance of probability amplitude waves (the QM wave function) rather than an effect that directly enables the QM computer. Of course if you didn't have QM wave functions you wouldn't have a QM computer so I guess that's a chicken and egg scenario. Entanglement is like the "carburator" function of the QM computer. The QM computer uses superposition of QM wave functions to work and when you have more than one QM wave function, they get entangled when you start superimposing wave functions and the way the waves entangle helps you compute in parallel so it's important to understand how these waves entangle.
Heisenberg's principle is a consequence of wave function collapse (measurement) which also limits the QM computer (this limiting effect is often called QM de-coherence). Heisenberg isn't required by a QM computer when it's computing, but you need to see the result somehow so when you measure the result, one of the side effects is the Heisenberg principle (although that's also a chicken-egg problem, since HP is a consequence of QM wave function collapse and w/o QM there's no superposition computing). The closest explanation I can think of is that Heisenberg's principle is the "heat" caused by friction of the QM computer. You need friction to stop the computer to read out the result, but at the same time you can't get rid of a little friction while it's running either (causing de-coherence). The side effect of this friction is heat.
You may have a personal opinion that superposition is a "nice way of doing statistics using discrete values for covering the not so discrete results of experiments", but there is experimental evidence that your personal opinions is at odds with physical reality. As QM computers that do QM computing (including IBM's NMR experiment which implemented shor's algorithm) have already been implemented it's hard to refute that something non-classical is going on.
It may be that in the end, QM is total malarky and there's some other weird unexpected thing going on, but there are mountains of evidence that whatever is going on, it isn't as simple as "hidden variables"
Parent
Re:Does exist any quantum computer proven to work? (Score:4, Informative)
1. Entanglement: It is fact. If you send a photon through a certain type of non-linear crystal, two photons will emerge that are entangled quantum mechanically. To truly understand this requires some knowledge of quantum mechanics, a basic introduction to QM and entanglement can be found here [ipod.org.uk] and here [davidjarvis.ca] if you care to learn more.
2. Heisenberg principle: You inadvertently stumbled onto the problem yourself, kinda. When trying to measure the position of the electron, you use a high energy photon and this photon. When this high energy photon interacts with the electron it alters the velocity of the electron, so you know less about the velocity of the electron. When trying to measure the velocity of the electron, you use a low energy photon. This low energy photon measures the velocity well, but it moves the electron a little bit, so you don't know its position. This issue is the essence of the Heisenberg uncertainty principle.
Parent
Re: (Score:3, Informative)