Submitted by “Scientists from Oxford University have made a significant step towards an ultrafast quantum computer by successfully generating 10 billion bits of quantum entanglement in silicon for the first time — entanglement is the key ingredient that promises to make quantum computers far more powerful than conventional computing devices.”
It’s my understanding that the applications for quantum computing are pretty specific, and it’s unlikely we will have these machines in our homes? And our cryptography will be woefully broken?
In short, quantum computers are very good for solving problems which have lots of possible solutions through brute force, because they can test all possible solutions at once.
I don’t see them replacing current desktop computers, at least not in the upcoming years. It’s much harder to produce and program a quantum computer for a small benefit on everyday tasks (where for most people today’s processors are already good enough). But there are several areas of computing which would benefit from those. Consider looking for something in a database, as an example…
A lost of current cryptography algorithms (like RSA) are going to be totally broken, because they are vulnerable to brute force attacks. Their authors did not expect that one day, computers would be able to test every single possible private key *at once*.
On the other hand, quantum mechanics have also major potential benefits in the information concealing area, because quantum information cannot be copied (to the best of physicists’ knowledge at least), which means that communications based on quantum objects cannot be looked upon or otherwise altered without both parties knowing about it. That’s the principle behind quantum cryptography.
Edited 2011-01-23 18:20 UTC
In this way, quantum computing (which is a completely different computing paradigm) would allow NP problems to be solved in P time on a quantum computing device. In order to confuse symbolic logicians everywhere, I propose P time on a quantum computing machine be cannonicly called QP (or maybe C3PO).
Not really.
The proof of P=NP does not depend on the speed or parallelism of the computer. Today, you can solve some NP problems very fast, esp. using FPGAs, with careful mapping. It is the “careful mapping” part which is also pertinent to quantum computers, and which makes the proof still elusive.
It’s not a matter of speed, but of complexity. If it is always O(1) to look at all branches of a solution path simultaneously (as it is in theory with a quantum computing device), then NP problems can be solved in P time on a quantum computing device. In essence, quantum computing simulates non-determinacy in that instead of an oracle function revealing the correct path, all paths are considered simultaneously (without increasing the complexity).
It may take O(1) (not really but I will play along) to “solve” a single problem instance after it has been mapped, but you still need to MAP the problem to the quantum solver for each instance. And the mapping process/problem is definitively not O(1), or even P for that matter, in terms of complexity. There are 3-sat solvers for example which compute solutions in P time, as long as the mapping process is ignored.
Which is why I said that the speed of the computer is irrelevant when trying to prove that P=NP.
Edited 2011-01-23 21:15 UTC
I think that quantum computing cannot ever apply to proving P=NP or P!=NP because complexity theory is predicated on running programs on deterministic machines. Quantum machines would be non-deterministic.
Also, just for fun, check this out (if you haven’t already):
http://science.slashdot.org/story/11/01/21/2047229/Eulers-Partition…
But by proving that NP=P is the only way you can substantiate claims that an NP problem can be solved in P time using Quantum computers. Which was the gist of the discussion we’ve been having.
Quantum computer may help make part of an NP computation deterministic, but that does not mean that NP problems become deterministic in the least.
P time is not the same as the class P.
P time means solvable in polynomial time.
The class P is the set of problems solvable in polynomial time on a deterministic machine. The class NP is the set of problems solvable in polynomial time on a non-deterministic machine.
NP problems are often O(N!) or O(N^N) or worse on deterministic machines. However, they most likely are solvable in P time on quantum computing machines. This does NOT mean that P=NP because quantum computing machines are NOT deterministic.
This is a common misunderstanding about the power of quantum computers.
When you talk about problems solvable in P time on quantum computers, I guess you mean the complexity class BQP. However, today the question of weather BQP=NP is as open as the P=NP question.
Or to quote Scott Aaronsson “Quantum computers are not known to be able to solve NP-complete problems in polynomial time.”
A lost of current cryptography algorithms (like RSA) are going to be totally broken, because they are vulnerable to brute force attacks. Their authors did not expect that one day, computers would be able to test every single possible private key *at once*.
This is indeed REALLY scary. If you know the hash to someone’s password it’ll be a matter of seconds to find it out. And you can’t really sign your applications or anything anymore since it’s again just a matter of seconds of finding out the original key. The same goes for WPA2-PSK: no matter what kind of password you use, it’ll be broken in seconds.
What’s even worse though is that encrypting your files, using compressed, encrypted files, or even encrypting the whole filesystem will become useless if the algorithm is known! Basically, protecting your files will become almost impossible if the attacker has access to a quantum computer, and we can bet that there will be Amazon EC2-like service available sooner or later.
That’ll be why we have quantum home computers. You get a quantum machine to generate every possible alternate password and have them used AND changed all at the same time, at once, in a single instance.
Like anytime I try to understand quantum computing and its implications for more than a few seconds, my head hurts ^^
‘Quantum computing’ really just means following all possible paths in a branch simultaneously. So for example:
We’re writing a program to search a binary tree for a value:
– In a ‘standard’ program, each step involves deciding whether to look at the right or left half of the current tree.
– In a ‘quantum’ program, we always look at both halves simultaneously.
I agree that this is the basic principle. Since we can now be in a superposition of a |O> and a |1> state (no matter how we have defined them), we are able to explore several paths in a binary tree at once, and thus to reach extreme degrees of parallelism.
The problem is when I try to go beyond that basic principle…
Apparently, the simple fact that most classical operations like NAND, OR, and XOR are irreversible makes them unsuitable for quantum computing. Thus, we need to re-think computing in terms of fully reversible operations like the ones at http://en.wikipedia.org/wiki/Quantum_gate . This is where things start to feel strange.
Moreover, extreme parallelism is more the realm of computers than it is the one of human minds. Trying to picture oneself what “You get a quantum machine to generate every possible alternate password and have them used AND changed all at the same time, at once, in a single instance.” means in practice is difficult. How exactly could I be using several passwords at once ? I mean, as soon as an intruder measures my stored data, I have only used one single password on it, right ?
Guessing a password is not a computational problem, but decryption is. Suppose that your data is encrypted with a really really really hard to determine password. Also, suppose that there is a reasonably reliable test to determine when data is decrypted successfully.
With conventional computing devices, an attacker must try to guess your password. For every guess, he/she must attempt to decrypt your data and determine if the decryption is successful. This takes a lot of time and computing resources (this is essentially the justification for password encryption – decryption without knowing the password is too much trouble to be worth the time of an attacker).
A possible fear (and a valid one, IMHO) is that an attacker with a quantum computing device can skip the step of guessing your password. He/she can attempt decryption by all password possibilities simultaneously.
In this way, a whole level of complexity (and a whole order of magnitude) would be removed.
Make more sense?
I think that’s not what he was talking about when he said “You get a quantum machine to generate every possible alternate password and have them used AND changed all at the same time, at once, in a single instance.”
That’ll be why we have quantum home computers. You get a quantum machine to generate every possible alternate password and have them used AND changed all at the same time, at once, in a single instance.
I hope that’s a joke, hard to tell from a simple comment. If not then you haven’t understood much about quantum computing.
The actual implementations will have to revolve around human programming abilities, so an order of events will prevail due to higher level mathematical restrictions / presumptions.
Primarily the use in computing will be limited to the primary effect of entanglement: instant communication of state.
We will debase the features to binary in one way or another, using the ability to hold multiple states for compression – or letting it go to waste entirely except for a few special applications.
At the low level ( quantum ) it seems odd and fanciful, but when we come back up we fall back into normal mathematical realities for many reasons. So we will be running a normal brute-force routine just like you would on a modern computer, except you would pre-program a qubit array to behave in such a way as to permit an instant answer – so you wouldn’t have to wait for the next clock cycle or until the CPU registers the answer.
The result is that performance becomes limited by the attached electronics. CPUs will have qubit arrays for integer & floating point math, and to replace internal (possibly even external) busses.
The attached electronics will be capable of only accessing a qubit array at the rate which we can measure and store the state of the array, thereby limiting performance.
In time the hybrid approach will fade into a memory and we will have true quantum computing, where we can selectively entangle qubits remotely within a system, or even globally or beyond, so as to have instant storage of solutions.
The only limitation at that point comes to ensuring the proper ordering of events. I suspect we will always have a timer going, even though that timer will itself be a qubit array swapping from one state to another, thereby triggering the next load stage, then its next swap triggers the receive state. At that level, we may find a perceptible delay between load and answer ( the only two stages in a qubit array ).
My thoughts, anyway…
–The loon
“A lost of current cryptography algorithms (like RSA) are going to be totally broken, because they are vulnerable to brute force attacks. Their authors did not expect that one day, computers would be able to test every single possible private key *at once*.”
This is completely wrong. RSA and ECC will be broken due to Shor’s algorithm, not due to instantaneous brute force attacks. Brute force approaches only get a O(n^2) speedup on quantum computers due to Grover’s algorithm.
That’s why hash functions, block ciphers and all the other primitives will still be secure (if we double their key/internal state sizes).
Fortunately, research in Cryptography already is studying problems which seem to be resistant to quantum computing power. The whole area is called Post-quantum Cryptography and they already have a stable conference. The primitives are normally built on top of NP-hard problems (which up to now only receive a quadratic speedup in a quantum computer).
Availability of quantum computing power does not imply that P = NP because until now no one could map any NP-hard problem for an efficient (polynomial) solution in a quantum computer.
What you’re saying is that current algorithms (like Shor’s algorithm) cannot actually check all possible passwords at once, and that they have thus not yet broken all current cryptographic systems.
Alright.
First, remember that we are talking about what’s possible *in principle*, no what’s implemented yet. Otherwise, we wouldn’t even be talking about quantum computers breaking ciphers.
In principle, a quantum algorithm may be executed with all its possible input parameters at once.
What does this mean ?
Most current cryptographic systems have the following feature : if I type a wrong password whey I try to decrypt something, they tell me after a very reasonable time (a few seconds at best) that I was wrong.
It means that a password can be checked for validity in a few seconds.
So if we can implement the algorithm which checks a password for validity in a quantum form, we can check all passwords for validity at once, with exactly the same complexity as checking a password for validity on a classical computer, and the whole encryption algorithm has just blown up.
Two things can prevent this from happening :
-> The ability for the user to quickly check a password for validity is removed from newer versions of the encryption system, in a tragic example of usability being sacrificed for the sake of safety.
-> This check cannot be implemented in a quantum form for some mysterious reason, which essentially means the same thing but only for quantum computer users.
Edited 2011-01-24 08:35 UTC
Shor’s algorithm is an integer factorization algorithm, not a “password checking” algorithm.
I’m talking about the state-of-the-art on quantum computers. The only types of problems which can be efficiently solved (polynomial time) in a quantum computer are in the class BQP. Problems requiring strict brute force are in EXPTIME. Quantum computers only allow a quadratic speedup to EXP problems.
Indeed, a quantum computer has 2^n simultaneous states and can apply the same computation to all of them in parallel. However, to obtain the result of the computation, the observer needs to collapse all these results, losing a whole lot of information. It’s very hard to employ this property in a way that a quantum algorithm gives a speedup over a classical algorithm. As you said in a previous message, first you have to be able to “map” the problems to a quantum instance.
You can check all the 2^n possibilities, but only recovering a collapsed version of the results, that its, you would only know that one of the key is correct (but we already now this by definition).
A brute force algorithm in a quantum computer needs a search algorithm. Grover’s algorithm has complexity of O(n^1/2) and it’s already proven optimal, so it cannot get any faster.
True. I would just add one further point: all encryption methods are, from a mathematical point of view, vulnerable to brute force attack since they cannot use a key of infinite length. In practice this is less true due to implementations restricting how a user can determine if a key is valid or not.
With quantum cryptography the uncrackable one-time pad would still be secure. Even if you generated a complete super-key you have no way of knowing if its valid until you compared against all sub-keys. And since these are never reused, you could never know its valid until all the sub-keys were used up.
Using quantum cryptography to securely (as in it is impossible for 3rd parties to read the key without us knowing) transmit a one-time pad key, would still be 100% secure.
The current method used by financial companies that trade on the stock market is to transport a very large key (gigabytes in size) physically using a flash drive with security guards. This is the one-time pad, and each time a transaction is a made a piece of it is used as the key. This is also still 100% secure with quantum cryptography, because how can you ever know a quantum generated one-time pad is valid if the parts of it are never reused?
Edited 2011-01-24 09:41 UTC
I agree. If you can’t easily check a key for validity (which is, if I remember well, the case for a one-time pad, where we can only use a simple addition+modulo algorithm since each byte of the encoded message is encrypted using a different, fully random byte of the key), quantum computers are useless, because all possible keys are equally valid — they’ll just result in a garbled output after some long decryption time.
As I said above, the ability to (relatively) quickly check one single key for validity in current cryptographic systems is a major vulnerability which makes quantum computers suitable for breaking most existing ciphers. If you remove it, quantum computer’s job will be made harder.
And quantum cryptography has the potential to make communications physically impossible to spy on. Though it is vulnerable to other attacks (like Eve cutting the optical fiber between Alice and Bob, plugging it in her own computer, and pretending that she’s Bob), which require additional care.
I wouldn’t worry about the future of cryptography and communications. Quantum information also has the potential to make them even more secure than they have ever been before. And faster, too (since one-time pads, which are computationally much less intensive than the current mess, can be used. These only require some storage space for the key). Since quantum cryptography is way closer to maturation than quantum computers, the transition to quantum systems will probably be smooth.
Edited 2011-01-24 10:05 UTC
This is not critical, please refer to my other message. You are oversimplifying things and propagating misleading info.
Availability of quantum computing power does not make the one-time-pad useful in practice. If it was really useful, we would be using it already with classical systems. Tell me how you can negotiate massive amounts of key size in a secure way with every HTTPS website out there.
Quantum cryptography is just a fancier way to do key agreements and the initial bootstrap, shockingly, still depends on a traditional PKI certificate. How can we trust the authenticity of a digital signature in a certificate if you conjectured that all crypto can be broken by instantaneous brute force searches in a quantum computer?
Edited 2011-01-24 17:01 UTC
It can also be used for nearly instantaneous communications of virtually unlimited data. I foresee entangled quantum arrays of even a small size ( even just a few dozen qubits ) being design to reflect a ‘streaming’ data stream from a given source.
Imagine TV signals without the need for transmission lines. Networking would become very quick, indeed.
To transmit data a group of qubits which are entangled with the master set are read at a specific rate. The master set is modified at the same specific rate, with a given duration per state held.
I do not see much in the way of providing master sets to the home user unless the entanglement can be dynamically altered on the silicon without fancy equipment. Which I am certain will be a goal.
A few qubits on a normal CPU will also permit massive gains in memory performance.
Unless I’m just missing something…
–The loon
Quantum entanglement does not work that way. You cannot use it to transmit information.
Although qubits can be in a lot of possible different states, those states cannot actually be read separately, even though they may affect intermediate computations. At best superdense coding ( https://secure.wikimedia.org/wikipedia/en/wiki/Superdense_coding ) can be used to get two bits out of a qubit.
The main advantage I see in quantum entanglement is the lack of spatial limitations. This should mean ( unless I’m missing something – which is highly probable ) that you could have entangled quantum ‘objects’ far removed from each other ( as in miles / planets ) and you can manipulate one part of the entanglement to set a desired state in another part for the purposes of communication.
I must admit I have only a very limited exposure to the concept, mainly from documentaries
And some very light reading on Wikipedia…
For now my time is spent on currently ‘appliable’ knowledge.
–The loon
I hear these computers are so fast that OpenOffice.org startup times are barely perceptible.
Writer only takes a fraction of a second to load on my laptop (Fedora 14 x64 on a core i5 M430 + 4GB RAM + 5400 RPM HDD). It’s opening Office files which can be dead slow (PPTX especially).
Edited 2011-01-23 20:28 UTC