[signalsmith]

I thought the whole magic of quantum-computing was that instead of just having individual bits in an uncertain/random state, you entangled a whole bunch of bits together, meaning you can meaningfully talk about the probability distribution of an 8-bit value, that's different from 8 independent 1-bit distributions.

Then, you perform operations where the value interacts with alternate values for itself (i.e. the full wave-function) - a bit like the double-slit experiment. For example, you can end up with a new 8-bit value where the probability distribution is the Fourier transform of the previous one's distribution.

So, if you can engineer the initial probability distribution to be "interesting", you can then sample its Fourier transform - using only the 8-qubit values, and not storing 2^8-point distribution in an array. Scale that up, and you could calculate a useful 2048-bit Fourier transform (or more accurately: observe a random sample from the result) with a 2048-qubit system, instead of a 2^2048-point array.

It's not obvious to me how stochastically-changing bits of state can get anywhere close to self-interacting (double-slit-like) calculations.

[DennisP]

They used 8 p-bits and could factor numbers up to 950, which took about 15 seconds. They say "it's possible that a larger number of p-bits will mean a significantly larger sampling time." That seems likely to be a drastic understatement.

[aflag]

Funny that's what a human takes to factor 950 with pen and paper