4 ms·
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
by Strilanc 5y ago
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.
- enriquto 5y ago> 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. As a regular user of O(n*log(n)) multiplication algorithms in my daily work, I find your comment amusing.
- amelius 5y agoIsn't it part of just about every bignum library out there?
- enriquto 5y agoYes, I had not thought about that even.
- Sukera 5y agoNot 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.
- dataflow 5y agoAre 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. [1] https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document
- enriquto 5y agoNo, I don't multiply integers, but polynomials, where the standard "fast" algorithm is nlogn
- dataflow 5y agoOh. I think the comment you replied to was talking about integer multiplication, not polynomial.
- adgjlsfhk1 5y agoto be specific, this is nlogn arithmetic operations, which isn't nlogn if you are doing exact math.
- enriquto 5y agosure, 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.
- adgjlsfhk1 5y agoIt'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.
- bakul 5y agoThe 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! https://hal.archives-ouvertes.fr/hal-02070778v2/document https://hal.archives-ouvertes.fr/hal-02070778v2/document
- scapp 5y agoWait, is there something wrong with the paper you linked? Theorem 1.1 says > 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.
- bakul 5y agoSee this: https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problem https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-so... 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!
- tzs 5y agoThe 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.
- bakul 5y agoThanks for the correction. Should've read the paper when less tired!
- Strilanc 5y agoI 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. 1: https://hal.archives-ouvertes.fr/hal-02070778v2/document https://hal.archives-ouvertes.fr/hal-02070778v2/document 2: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
- dekhn 5y agothe 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.
- japanuspus 5y agoAs 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.