Hacker News Reader

Comment by adastra22 | Hacker News Reader

> In other cases, it found that existing circuits included costly components that were needed to handle only extremely rare inputs, and it redesigned them without those components.

So it’s not performing the same computation…

View on HN

Yes strictly speaking it's a different computation, but the differences are so small that it won't meaningfully affect the outcome of Shor's algorithm.

One of the most important things to realize when optimizing quantum algorithms is this: approximations are overpowered. The difference between 99.99999% accurate and 100% accurate can be a factor of 10 in cost. And there's lots of places where a 90% accurate algorithm is more than good enough.

Why the ellipses? It's not like they're sweeping this under the rug, it's pretty explicitly stated for which optimizations this applies. It's also a perfectly standard optimization strategy.

Their second example features it for example, but as an additional optimization that saves memory. The compute optimization part doesn't need this, and is what brings the little over an order of magnitude speedup.

We have excellent approximations of the full quantum chemistry that work really well, e.g. DFT. It's the gold standard for chemistry today. But these edge cases, although rare, do show up. They have a nasty tendency of showing up in biology especially, where reactions often happen on a knife's edge of the energy landscape, for efficiency reasons.

Chemists are interested in quantum simulation because it would be fully accurate and be an actual substitute for ground-truth experiment. With these approximations, you still wouldn't know if what you're simulating matches reality.

i just skimmed the article, but it does sound like it would be detectable if the case you had is one that the algorithm doesn't handle. In any case, it sounds like it is very rare that you have one of those cases vs existing heuristics, which is a simplification every time.

Typical quantum simulation papers do not target 100% accuracy, they target "chemical accuracy [1]". That said, chemistry simulations do tend to be less tolerant of approximations because you are sampling an unknown distribution and so can't easily tell if a shot had a failure. But the linked article is about a subroutine for Shor's algorithm, where it is very obvious if you succeeded or not because you either recovered the private key or you didn't.

[1]: https://chemistry.stackexchange.com/questions/62001/why-is-c...

Reply on news.ycombinator.com