3 ms·

You should care about quantum computers because they can factor numbers in polynomial time, which breaks RSA public-key encryption. http://en.wikipedia.org/wik

You should care about quantum computers because they can factor numbers in polynomial time, which breaks RSA public-key encryption. http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Shor%27s_algorithm

younata 16y ago
Ok, forgive my ignorance, but why is it that quantum algorithms can ONLY run on quantum computers? Is it the fact that qubits can have three states? If that is the case (which it likely isn't), why is base 3 better for this work than base 2?
- deleted 16y ago
  [deleted]
- SoftwarePatent 16y ago
  Quantum computers make use of quantum mechanics. So things like entanglement and decoherence are essential to the algorithms. It has nothing to do with base 2.
- sgk284 16y ago
  It's not so much 3 states, as it is two states and a superposition of both states, meaning that the qubit is effectively both a 0 and a 1 at the same time.
- vmind 16y ago
  Basically: Qubits (sort of) encode all possible states that a standard string of bits can take at the same time as a superposition, such that when you measure them, you have a possibility of observing each possible setting of the bits. You can manipulate the possibility of observing certain states by performing operations on the bits (which are effectively interference). So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. In order to be sure of a result, you need to repeat the calculation to get a desired confidence (or just check the answer directly if that would be faster).
  - dcosson 16y ago
    > So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. Not necessarily, some quantum algorithms give an answer with 100% probability (like the Deutch-Josza algorithm). You're right in that the two most interesting ones (Grover's and Shor's algorithms) are probabilistic, though.
- devinj 16y ago
  No, they can run on quantum computers, but to properly simulate a quantum computer, you may need exponential space/time. Googling for supporting data brought up http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html which discusses simulating Shor's algorithm on a classical computer. The reason for the exponential is that the bits are all in a superposition of all possible states (so for a 14-bit register, that's a superposition of 2 to the 14 states), which operations all act on. Or something like that. I'm not really that clear on the details. :(
  - bdhe 16y ago
    > Or something like that. I'm not really that clear on the details. :( Your intuition is correct. Quantum algorithms seem to perform better than classic algorithms because there are certain operations (like fourier transforms) that can be performed exponentially faster (as of today) than classic algorithms. It is still unknown however whether or not we can simulate quantum computations classically without exponential blowup otherwise it would resolve major open questions in complexity theory.
- masterzora 16y ago
  Obviously that isn't the case; if it were we'd simply roll out ternary computers, which have been used before. I'm no physicist, and my knowledge of quantum is mostly memories of an intro course I took 5 years ago, so I hope someone with a bit more knowledge can come and fill in the gaps here. Nevertheless, the basic principle is that quantum superposition allows us to parallelise things with relatively reasonable space requirements.
cperciva 16y ago
I think 14 qubits is large enough to factor 21. Pretty sure it can't factor 35 yet, though.
procrastitron 16y ago
Restricting the problem to a fixed size input makes factoring an O(1) operation; so I still don't see what all the fuss is about. Unless you know a way of extending this to handle an arbitrary amount of I/O then it's just a way of implementing nondeterministic finite state machines; which are no more powerful than deterministic finite state machines.
- pmjordan 16y ago
  Rather than downvoting you to oblivion, I'll point out that "Restricting the problem to a fixed size input makes factoring an O(1) operation" makes no sense. Sorting an array of N items using a comparison sort has a lower complexity bound of O(N log(N)) in the worst case. Yes, of course that becomes O(1) if you say N is constant, but that's really not helpful at all.
qntm 16y ago
Which is why you should also care about post-quantum cryptography: http://en.wikipedia.org/wiki/Post-quantum_cryptography http://en.wikipedia.org/wiki/Post-quantum_cryptography

younata 16y ago

Ok, forgive my ignorance, but why is it that quantum algorithms can ONLY run on quantum computers? Is it the fact that qubits can have three states? If that is the case (which it likely isn't), why is base 3 better for this work than base 2?

deleted 16y ago
[deleted]
SoftwarePatent 16y ago
Quantum computers make use of quantum mechanics. So things like entanglement and decoherence are essential to the algorithms. It has nothing to do with base 2.
sgk284 16y ago
It's not so much 3 states, as it is two states and a superposition of both states, meaning that the qubit is effectively both a 0 and a 1 at the same time.
vmind 16y ago
Basically: Qubits (sort of) encode all possible states that a standard string of bits can take at the same time as a superposition, such that when you measure them, you have a possibility of observing each possible setting of the bits. You can manipulate the possibility of observing certain states by performing operations on the bits (which are effectively interference). So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. In order to be sure of a result, you need to repeat the calculation to get a desired confidence (or just check the answer directly if that would be faster).
- dcosson 16y ago
  > So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. Not necessarily, some quantum algorithms give an answer with 100% probability (like the Deutch-Josza algorithm). You're right in that the two most interesting ones (Grover's and Shor's algorithms) are probabilistic, though.
devinj 16y ago
No, they can run on quantum computers, but to properly simulate a quantum computer, you may need exponential space/time. Googling for supporting data brought up http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html which discusses simulating Shor's algorithm on a classical computer. The reason for the exponential is that the bits are all in a superposition of all possible states (so for a 14-bit register, that's a superposition of 2 to the 14 states), which operations all act on. Or something like that. I'm not really that clear on the details. :(
- bdhe 16y ago
  > Or something like that. I'm not really that clear on the details. :( Your intuition is correct. Quantum algorithms seem to perform better than classic algorithms because there are certain operations (like fourier transforms) that can be performed exponentially faster (as of today) than classic algorithms. It is still unknown however whether or not we can simulate quantum computations classically without exponential blowup otherwise it would resolve major open questions in complexity theory.
masterzora 16y ago
Obviously that isn't the case; if it were we'd simply roll out ternary computers, which have been used before. I'm no physicist, and my knowledge of quantum is mostly memories of an intro course I took 5 years ago, so I hope someone with a bit more knowledge can come and fill in the gaps here. Nevertheless, the basic principle is that quantum superposition allows us to parallelise things with relatively reasonable space requirements.

cperciva 16y ago

I think 14 qubits is large enough to factor 21. Pretty sure it can't factor 35 yet, though.

procrastitron 16y ago

Restricting the problem to a fixed size input makes factoring an O(1) operation; so I still don't see what all the fuss is about. Unless you know a way of extending this to handle an arbitrary amount of I/O then it's just a way of implementing nondeterministic finite state machines; which are no more powerful than deterministic finite state machines.

pmjordan 16y ago
Rather than downvoting you to oblivion, I'll point out that "Restricting the problem to a fixed size input makes factoring an O(1) operation" makes no sense. Sorting an array of N items using a comparison sort has a lower complexity bound of O(N log(N)) in the worst case. Yes, of course that becomes O(1) if you say N is constant, but that's really not helpful at all.

qntm 16y ago

Which is why you should also care about post-quantum cryptography: http://en.wikipedia.org/wiki/Post-quantum_cryptography http://en.wikipedia.org/wiki/Post-quantum_cryptography