Computer scientists eliminate pesky quantum computations

https://www.quantamagazine.org/computer-scientists-eliminate-pesky-quantum-computations-20220119/

by nsoonhui • 5 years ago

46 21 5 years ago

Strilanc2• 5 years 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.

enriquto4• 5 years 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• 5 years ago

Isn't it part of just about every bignum library out there?

bakul3• 5 years ago

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!

https://hal.archives-ouvertes.fr/hal-02070778v2/document

dataflow2• 5 years ago

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.

[1] https://hal.archives-ouvertes.fr/hal-02070778/document

Strilanc2• 5 years ago

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.

1: https://hal.archives-ouvertes.fr/hal-02070778v2/document

2: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...

dekhn• 5 years ago

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.

japanuspus• 5 years ago

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.

pwdisswordfish9• 5 years ago

With that title, I expected a result of a calibre like P = BQP.

phkahler• 5 years ago

> 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?

Computer scientists eliminate pesky quantum computations

Related Stories