3 ms·
Theoretically none. Quantum computers are universal Turing machines. The main advantage of quantum computers is speedup. 5 years ago (when I took a couple of c
by rdtsc 17y ago
Theoretically none. Quantum computers are universal Turing machines. The main advantage of quantum computers is speedup.
5 years ago (when I took a couple of courses in QC) there were basically 2 quantum algorithms -- Shor's factorization and Grover's search. The former speeds up integer factorization (and discrete logarithm) and brings it to polynomial time, and the later speeds up search from O(n) to O(sqrt(n)).
So just being able to quickly factor integers breaks a lot of encryption algorithms, and a faster search would really help with data processing.
One of the main difficulty with quantum computers is quantum de-coherence. Qubits when they are entangled must be isolated from the outside environment until the final result measurement is taken. That is what is preventing the creation of large, multi-qubit computers. For example, it would be useful to have a 1024 qubit machine to simultaneously represent all 1024 bit states.
Quantum error correction might solve the problem, but we are yet to see practical quantum computers.
- amichail 17y agoWhere does quantum cryptography fit into this? http://en.wikipedia.org/wiki/Quantum_cryptography http://en.wikipedia.org/wiki/Quantum_cryptography Does this have anything to do with quantum computing?
- rdtsc 17y agoYou are right, thank you. I embarrassingly forgot quantum cryptography.
- amichail 17y agoBut it seems that quantum cryptography allows you to do more than what is possible with classical computing: namely, to detect someone listening in on your communication. What is the relationship between quantum cryptography and quantum computing?
- enki 17y agoyou were right to leave it out - quantum cryptography and quantum computing have only the quantum in common. (i've published on quantum cryptography protocols)
- amichail 17y agoCould you elaborate on this? Classical encryption can be done on a classical computer. Is it the case that (some) quantum encryption cannot be done on a quantum computer?
- enki 17y agoquantum cryptography isn't "encryption" in the sense that crypto algorithms are involved. the encryption part is just XOR with a random one-use string (the key). the hard part is distributing that key. a better name is quantum key distribution. entangled photons are used to get the random data to both parties in a way that eavesdroppers would introduce error (because of something called quantum indeterminancy). since no computation is involved, there's not a lot relation to quantum computing. wikipedia's got the details!
- amichail 17y agoThis isn't something that a Turing machine can do. Why not make this part of a quantum computational model that goes beyond Turing-completeness?
- smanek 17y agoBecause it isn't a computation (in the 'transform data' or 'answer question' sense).
- jerf 17y agoDisclaimer: I'm not quantum-anything researcher. But: Based on the description of how "quantum encryption" works, I prefer to call it "quantum intrusion detection". It allows you to verify that the channel is free of eavesdroppers and get a stream of random bits that are guaranteed to only be agreed upon by the two ends of the connection, which can then be used for any other purpose that a stream of random bits only known by two parties can be used for. Using it for a one-time pad is the easiest thing from a theoretical point of view, but you can use it to feed a conventional encryption algorithm, too. The real key isn't the "random", which is easily obtained from a wide variety of other sources, including fully unpredictable ones like decay sources, nor is it the "encryption" which is merely one application (though easily the "killer app") of the system. The real key is the part where you can detect any intrusion into the connection. (Obviously, you, enki, know this, well, unless I'm wrong. I'm just elaborating.)
- sp332 17y agoActually, because of the inherent uncertainty, most computations are exponentially slower on a quantum computer. There are a few algorithms that manage to take advantage of entanglement and superposition to be faster, but quantum computers are not inherently faster than classical computers.