3 ms·

OK, yes. This builds on the parts of my intuition that already exist. It's about building a system (from combinations of quantum operators) that maximizes the p

OK, yes. This builds on the parts of my intuition that already exist. It's about building a system (from combinations of quantum operators) that maximizes the probability distribution of the result you want. I'm still unsure of the timeline of any quantum operator, and the "finding the interference" seems equivalent to saying something like "find the function" or something more classical.

msclrhd 8y ago
With Shor's algorithm, the quantum part of the algorithm comes down to finding the period of 'a mod N' where N is the prime number you have, and a is a number less than N that is not a factor of N. Here, the period is the smallest value of x where 'a^x mod N = 1'. This is done applying the Quantum Fourier Tranform on each 'a^x mod N' using x+1 complex roots of unity for that value of x. You can visualise this as x+1 arrows from the centre of a unit circle with an angle 2pi/(x+1). So, for x=3 you have 4 arrows pointing up, down, left, and right. When you stack the arrows end to end, they will loop back to their starting point (3 will form a triangle, 4 a square, etc.). The key is that when multiplting this quantum fourier transform with the value of 'a^x mod N', the 1s (at the period) will occur at the same point around the unit circle only for the cases where the number of complex roots is a multiple of the period. This has the effect that for the correct answer, the arrows are lined up together in a single direction, amplifying the number and thus the probability of selecting that number. For the others, the arrows cycle and loop back on each other, so stay fairly small, decreasing the probability they will be selected.
The_rationalist 8y ago
Yes I would really like to understand if this is different than curve fitting. How isn't that classical ? What about causality ? Quantum mechanics to me are just an effective model for dealing with uncertainty AKA probabilistic/meta probabilistic reasoning. But it is about statistically predicting the state of a particle/particles (position, spin, mass, momentum, etc). How can this model uncertainety in algorithms is something I don't understand at all. My brain is very tempted to claim that quantum computing is bullshit and that is what it seems to a layman like me because i've never read a great explanation. Even if quantum computing worked it would be soft computing ? By having a set of probabilities as results, that would be an approximation thus effectively allowing to be less than exponential for np hard and less correct. How does that differ from classical heuristics algorithms that already have massive Speed like SAT solvers ?
- maththrowawtays 8y ago
  Firstly, you're going to run into walls if you try to fully understand why the mathematics of quantum mechanics are how they are. Physicists have been going at it for decades and from what I can tell the picture is not so clear yet. What has been done though is many thousands of experiments showing that the predictions the mathematical theory makes (even the wild, unintuitive ones) are correct. Secondly, I think you're going too deep on this whole 'prediction' thing. The algorithms in quantum computing aren't trying to model something any more than a classical algorithm does. Currently, the notion of a quantum algorithm is just a series of special logic gates that act on qubits instead of bits. What the previous poster said above is correct. Quantum computers are like classical computers with randomization except instead of real probabilities it has what are called complex amplitudes. The way the complex amplitudes behave allow for the states to interact slightly different since they can now 'interfere' with each other to cancel each other out in very specific situations. This power gives quantum computers only slightly more power the classical ones (with randomization). (Most) experts don't think quantum computers can solve NP-hard problems. This power from the interference only helps in very specific problems.

msclrhd 8y ago

With Shor's algorithm, the quantum part of the algorithm comes down to finding the period of 'a mod N' where N is the prime number you have, and a is a number less than N that is not a factor of N. Here, the period is the smallest value of x where 'a^x mod N = 1'. This is done applying the Quantum Fourier Tranform on each 'a^x mod N' using x+1 complex roots of unity for that value of x. You can visualise this as x+1 arrows from the centre of a unit circle with an angle 2pi/(x+1). So, for x=3 you have 4 arrows pointing up, down, left, and right. When you stack the arrows end to end, they will loop back to their starting point (3 will form a triangle, 4 a square, etc.). The key is that when multiplting this quantum fourier transform with the value of 'a^x mod N', the 1s (at the period) will occur at the same point around the unit circle only for the cases where the number of complex roots is a multiple of the period. This has the effect that for the correct answer, the arrows are lined up together in a single direction, amplifying the number and thus the probability of selecting that number. For the others, the arrows cycle and loop back on each other, so stay fairly small, decreasing the probability they will be selected.

The_rationalist 8y ago

Yes I would really like to understand if this is different than curve fitting. How isn't that classical ? What about causality ? Quantum mechanics to me are just an effective model for dealing with uncertainty AKA probabilistic/meta probabilistic reasoning. But it is about statistically predicting the state of a particle/particles (position, spin, mass, momentum, etc). How can this model uncertainety in algorithms is something I don't understand at all. My brain is very tempted to claim that quantum computing is bullshit and that is what it seems to a layman like me because i've never read a great explanation. Even if quantum computing worked it would be soft computing ? By having a set of probabilities as results, that would be an approximation thus effectively allowing to be less than exponential for np hard and less correct. How does that differ from classical heuristics algorithms that already have massive Speed like SAT solvers ?

maththrowawtays 8y ago
Firstly, you're going to run into walls if you try to fully understand why the mathematics of quantum mechanics are how they are. Physicists have been going at it for decades and from what I can tell the picture is not so clear yet. What has been done though is many thousands of experiments showing that the predictions the mathematical theory makes (even the wild, unintuitive ones) are correct. Secondly, I think you're going too deep on this whole 'prediction' thing. The algorithms in quantum computing aren't trying to model something any more than a classical algorithm does. Currently, the notion of a quantum algorithm is just a series of special logic gates that act on qubits instead of bits. What the previous poster said above is correct. Quantum computers are like classical computers with randomization except instead of real probabilities it has what are called complex amplitudes. The way the complex amplitudes behave allow for the states to interact slightly different since they can now 'interfere' with each other to cancel each other out in very specific situations. This power gives quantum computers only slightly more power the classical ones (with randomization). (Most) experts don't think quantum computers can solve NP-hard problems. This power from the interference only helps in very specific problems.