Computer scientists eliminate pesky quantum computations
quantamagazine.org
quantamagazine.org
There are several reasons it's not practical.
First, their construction turns a t time, s space algorithm into a t*2^s time, s space, no-intermediate-measurement algorithm. That is a horrendous time overhead.
Second, although the article kind of plays it up like measurement is bad, it's actually one of the most useful tools in your quantum computing playbook.
Any kind of error correction is going to require constant measurement of parity checks to catch errors before they spread. If you don't do this, you're just not going to be able to do a large computation like factoring. The machines are just too noisy.
Another very common thing to have to do in a quantum computation is to compute an intermediate value, do something with it, then uncompute it. Without measurement, the uncomputation is just as expensive as the computation. With measurement, the uncomputation is often cheaper. Sometimes half as expensive. Sometimes quadratically less expensive.
So, like I said, very interesting from a theory perspective but I suspect actively harmful as a practical technique. But you never know; maybe this is the first step leading to something that really would be used during a computation.
As a regular user of O(n*log(n)) multiplication algorithms in my daily work, I find your comment amusing.
> There is an integer multiplication algorithm achieving M(n) = O(n log n).
You don't call something a theorem if it's a conjecture.
Where one of the authors says "So in this sense, our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously.”
Though I confess I am not up on the latest happenings in this area!
What they are saying is that they don't know how to prove that you can't do better than O(n log(n)).
Schönhage and Strassen conjectured that O(n log(n)) was the lower limit for this problem, and it seems that most experts believe they were right abut that. Hence, the expectation that with the discovery of an actual O(n log(n)) algorithm we are at the end of the road for this problem.
And if so, can I ask what it's useful for? I thought it was a galactic algorithm.
> Let n_0 = 2^(d^12) >= 2^4096 and suppose we wish to multiply numbers with n bits. [...] For n > n_0 we will describe a recursive algorithm [...]
2^4096 bits is enormous. That's way way way past the point where you could fit the numbers into the observable universe. Past the point where the expansion of space has become a real problem. You really should just use the O(n lg n lglg n) algorithm instead [2].
Your other comments indicate you work with polynomials with floating point coefficients. Yes, there are O(n lg n) algorithms for that case. And they are very practical.
1: https://hal.archives-ouvertes.fr/hal-02070778v2/document
2: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
For quantum complexity theory, the result is significant, as it shows that there is no need to distinguish between algorithms with and without intermediate measurement when comparing complexity.
Are there implications for measurements in physics experiments? What about the multiverse? If all measurements can be deferred to the end of time and get the same result, what does that mean in real terms?