Comment by jcranmer | Hacker News Reader

Comment by jcranmer | Hacker News Reader

Parent Full thread

I'm going to butcher a lot of the physics here, but here's the gist of it that should avoid some quantum myths:

The quantum state of a system is not described by a simple real probability but by a complex number. This means that there is an additional degree of freedom that you can adjust in a quantum state that doesn't change its probability of occurring. The nature of entanglement means that there is constructive and destructive interference when you go through certain quantum operations.

Traditionally, a quantum word can be thought of as being a probability distribution over the various possible values of the word. You can build quantum gates that act like classical gates on the binary values, and it's this property that often causes people to describe a quantum computer as executing every possibility in parallel. The difficulty is that the result you get is sampled by the probability distribution, which means you need some sort of interference between the results to allow you to boost the probability of picking the answer you want. A quantum speedup is only possible when you can find the interference. In the case of Shor's algorithm (for factoring), the interference is basically a quantum variant on FFT; in the case of Grover's algorithm (finding x such that f(x) = y), the interference is something that redistributes the probabilities among a plane of the sphere.

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.

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 ?

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.

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.

> This means that there is an additional degree of freedom that you can adjust in a quantum state that doesn't change its probability of occurring.

This gave me a real 'aha' moment - I've been trying to get an intuition for complex numbers for years, thanks.

Reply on news.ycombinator.com