How does non-commutativity of observables lead to quantum speedup in solving algorithms in quantum computing?

Question

The question might be misleading, but I'd like to understand a thing. By reading this really interesting question, one realises that the relevant thing in quantum mechanics and not reproducible in classical mechanics is that operator that realise observable quantities do not commute.

Now, how is this connected with quantum computing, i.e., quantum speedup in solving algorithms by using a quantum computing device?

Another way to see it is the following: how does the non-commuting of observable (which is the thing that makes a theory quantum) enter the quantum speedup?

Am I wrong to say that if the non-commutative of observable does not explain this quantum speedup, then it is not a real "quantum" speedup?

Answer 1

tl;dr It's not just about observables not commuting. That states can be superposed, entangled etc. is also crucial.

Some computational problems can exist at different scales, such as sorting $n$ items, or choosing which path between $n$ cities is quickest. Given any such task, and a way of solving it called an algorithm, the time complexity of that algorithm quantifies how much it slows down as $n$ increases. For example, some ways of sorting take what we call $O(n^2)$ time, and doubling large $n$ quadruples the sort time, whereas otherwise only take $O(n\log n)$ time, and doubling $n$ barely doubles the timescale (were it not for the pesky $\log n$ factor, it would be mere doubling). Either way, it's not that expensive to sort a list. By contrast, the other problem I mentioned takes ages unless $n$ is very small, although just how much expensive a larger $n$ is depends on the algorithm used.

Quantum computing is known to allow us to reduce the time complexity of some problems by making available algorithms that classical computers cannot use. This is not known to be a general speed-up property of quantum computers.

Here's one example. Given a list of $n$ items, we're guaranteed exactly one has a desired property, and we can check each one. How do we find which it is? Classically, all we can do is go through them one by one, and that takes $O(n)$ time. Amazingly, quantum computers need only $O(\sqrt{n})$ time! Why?

The full details are here, but the gist is this: we prepare a superposition of all candidate answers in which they each have the same complex-valued coefficient, then we keep applying what can be thought of as rotations and reflections that shift the state by $2\arcsin\frac{1}{\sqrt{n}}$ radians, and once the overall shift approximates $\pi/2$ a measurement will almost certainly identify the correct candidate.

Superposition per se isn't always the crux of it, though: one possible outcome of it, entanglement, can also be crucial. A much harder example I won't discuss in detail is that exploiting entangled states allows quantum computers to factorize large positive integers faster than any known classical algorithm.

Answer 2

A few thoughts:

1. The "non-commuting observables" aspect of quantum mechanics is essentially equivalent to the possibility of having superpositions, and therefore interference effects etc. Saying that two observables commute amounts to the fact that measuring their respective eigenbases gives "incompatible information", i.e. knowing the result of one measurement reduces knowledge about the result of the other.

2. In turn, the incompatibility of different measurement bases amounts to the possibility of measuring in superposition bases. This is the property of quantum systems of being able to hold information in the coherences between different constituents. By this I mean that a quantum system can be such that its individual components hold no information at all, and the only way to access its information is measuring in non-local bases.

3. There is no definite satisfactory answer, to the best of my knowledge, to the question: what properties of quantum mechanics lead to quantum speed-up in a given algorithm? You can find some relevant discussion e.g. here. Sure, you can say that faster-than-classical quantum algorithms are those that exploit intereference effects in a smart way, but imo that essentially amounts to saying that what makes the algorithms faster is quantum mechanics. Interference effects are so fundamental and intrinsic to quantum mechanics that saying "X is faster because of interference" is kinda the same as saying "X is faster because quantum mechanics". It certainly doesn't help much in figuring out which algorithms do actually provide a quantum advantage.