There's a lot of misinformation in this space, so be careful who you listen to. I hope to say as few false things as possible, but I can offer no guarantees. O

There's a lot of misinformation in this space, so be careful who you listen to. I hope to say as few false things as possible, but I can offer no guarantees. One source of confusion is that there are different types of proposed quantum computers. Some, like the D-wave machines, use stochastic measurement processes to arrive at probably-correct solutions. This is called "annealing", and it's a lot like what many machine learning algorithms do to try and find global minima in error function spaces, only the quantum mechanics gives it an edge in not getting stuck in local minima for various reasons. These aren't universal computers - they only implement very specialized algorithms in a kind of abstract sense. It's sort of like how if you take a box of different sized rocks and shake it for a while, you'll eventually find that the small rocks have made their way to the bottom and the bigger rocks have drifted to the top (this is called granular convection). There's a sense in which this is like a search algorithm that helps you find the biggest rocks. The quantum version of this (very loosely speaking) would be if the rocks sorted themselves faster because the small rocks would sometimes just tunnel through the big rocks. Using quantum effects to speed up annealing lets you do annealing faster than a classical simulation - but most problems aren't annealing problems. So present day quantum computers are specialized machines that do a kind of computation using quantum effects, but they can't run general purpose quantum algorithms. Think of them like co-processor chips that aren't quite CPUS. That said, it's sort of hard to define what a general purpose quantum computer would even be (for various reasons), so maybe that's unfair. Anyway, D-wave machines can't run Shor's algorithm, which is one of the examples of the "exponential speedup" over classical computation. The (claimed) algorithmic efficiency of quantum computing as it applies to quantum algorithms has to do with how much computation is done in each step. We represent information in physical systems and process that information by making those physical systems interact in a way that affects a state space transformation. The amount of processing we can do in "one step" depends on the size of the state space of our data representation and the kinds of operations we can affect via physical interactions. Conventional computation involves a bunch of parallel systems that have 2 distinguishable states interacting pairwise through networks of logic gates that perform a limited number of transformations. Systems of qubits have many more than 2^N distinguishable states (technically, an infinite number), and operations on them can be arbitrary linear transformations. So each quantum logic gate can do a lot more computation than a classical binary gate. Quantum algorithms basically translate information in the limited classical state space to the bigger quantum state space, do fancy operations, then project back into the classical space. It's sort of like data parallelism in the sense that if you can do a series of small operations or one big SIMD operation, the latter will generally be faster. Operations on qubits make use of physical parallelism that's only possible in the much bigger non-classical state space.