It's an interesting theoretical result but not at all practical. Sort of like the n lg n multiplication algorithm: it's nice that we can do it in principle, but you'd never actually use it.
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.
Not necessarily, no - the "perfectly efficient" algorithms often have prohibitively high constants in front of the theoretically perfect big-O, making them only useful/faster for numbers with so many digits that you can't realistically represent a lot of them, even on modern super computers. On top of that, caching effects and different implementations can make algorithmically "worse" code perform better for longer than naively assumed when comparing their big-O.
The Schönhage–Strassen algorithm is O(n*log(n)*log(log(n))) time algorithm. Fürer's algorithm is better (& impractical) but still worse than O(n*log(n)). Harvey and van der Hoeven's algorithm is conjectured to be O(n*log(n)) but not yet proven. No idea if it is practical!
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!
The author is not saying that they don't know how to prove rigorously that their algorithm is O(n log(n)). They have rigorously proven that.
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.
Are you sure you're using this algorithm [1] in your daily work and not a different one? It's the only known O(n log n) multiplication algorithm AFAIK.
And if so, can I ask what it's useful for? I thought it was a galactic algorithm.
sure, my coefficients are just floating-point numbers. I work in signal processing and when the OP said "multiplication" I could only think about applying a linear filter to a signal.
It's unknown whether it is a galactic algorithm (with some minor tweaks). According to the author, the version they published is optimized for simplicity and paper length rather than speed, but he thinks a lot of the constants can be made much lower. It's still quite likely galactic, but with some tweaks, it might not be. Also, in practice, I think their first algorithm that is nlogn subject to unproven (but likely) conjectures about the distribution of primes is more likely to be good computationally, but I am way out of my depth here.
I maybe should have been more explicit: I was referring to the bit-operation cost of big integer multiplication. The only claimed O(n lg n) algorithm for this task [1] notes:
> 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.
the point is that most people doing MM aren't doing theoretically optimal (for large N) algorithms, there are more practical algorithms with a higher computational cost that finish faster, for reasonable engineering reasons.
As I read the introduction of both the linked article and the cited paper, the result is mostly of importance to complexity theory, and the intention is not to actually apply this procedure to actual quantum algorithms.
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.
>> These features of quantum algorithms — that measurements can be delayed without affecting the answer or the runtime — came to be called the principle of deferred measurement.
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?
21 comments
[ 0.17 ms ] story [ 57.1 ms ] threadThere 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.
https://hal.archives-ouvertes.fr/hal-02070778v2/document
> 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.
[1] https://hal.archives-ouvertes.fr/hal-02070778/document
> 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?