Hacker News Reader

Comment by sweezyjeezy | Hacker News Reader

> We know an ideal quantum computer provides an exponential speed-up in commercially relevant applications

Do we know that though?

We don't. Here's a survey paper from quantum computing expert Scott Aaronson, posted to arXiv just a couple months ago: https://arxiv.org/pdf/2209.06930.pdf

From the abstract:

> I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022. [...] I make some skeptical remarks about widely-repeated claims of exponential quantum speedups for practical machine learning and optimization problems. Through many examples, I try to convey the "law of conservation of weirdness," according to which every problem admitting an exponential quantum speedup must have some unusual property to allow the amplitude to be concentrated on the unknown right answer(s).

I am very confused at how so many people are absolutely convinced that quantum computing is known to do, or already does, all sorts of things it is not known to do. There's a sister comment here saying exponentially superior quantum computers are available in AWS!

It's like an urban legend that circulates among software engineers.

You're wrong, we do know that, and the paper you cite doesn't refute that in any way.

Integer factorization and quantum simulation would be two examples of commercially highly relevant applications where an exponential speed-up applies.

Integer factorization for codebreaking is a military or criminal application, not a commercial one. Someone will make money doing it, but it won't be contributing to society in the way we normally mean when talking about commerce. It would be like saying nukes have commercial applications.

"Quantum simulation" is too vague to speak to applicability in any domain. There is no proven or empirically demonstrated exponential speedup on any simulation problem with known commercial applications.

This paper claims quantum computer can integrate arbitrary non-linear differential equations with quantum advantage:

https://arxiv.org/pdf/2011.06571.pdf

It does seems too good to be true.

I found a layman's explanation at Quanta Magazine: https://www.quantamagazine.org/new-quantum-algorithms-finall...

The two caveats are

1. Only works for "mildly" nonlinear equations

2. Results are in quantum world and have to be translated back into normal deterministic world results, and this hasn't been figured out yet

Why would integer factorization be commercially relevant? Only practical use of that (as far as I'm aware) is breaking RSA. Hopefully people will just switch to known quantum secure algorithms. It'll be a nothing burger.

Switching a few key libraries like OpenSSL to using quantum-resistant cryptography is WAY WAY easier than constructing a viable quantum computer (in secret) that is able to break 512 bit or 1024 bit key RSA.

Integer factorization is relevant only because integer factorization is currently considered to be computationally difficult and effectively impossible. If this ceases to be the case (effective QC hardware, or perhaps some math breakthrough), the effect is simply that integer factorization stops being a valid security or proof-of-work measure and thus it ceases to be used, not that breaking integer factorization becomes a viable commercial industry.

The only thing I can think of is somehow speeding up drug discovery or materials research by accelerating atomistic simulation. However that's so far from reality it's hard to tell whether it will actually be faster in practice. (Pretty much the first application people like Feynman had in mind too)

Well, those two small niches plus biological research are bottlenecks is pretty much any production process we have with real things.

Breaking RSA and ECC is commercially relevant.

> Breaking RSA and ECC is commercially relevant.

Yes, but we don't actually know that we can build such a device.

If you can break RSA once using say a $34 billion machine that is a one-shot operation, is it really commercially relevant?

With the number of qubits required to break RSA, there's no reason why general purpose computing wouldn't be possible.

Without assuming a spherical cow, that is well into the realm of science fiction-stuff we have no idea how to do. It assumes a degree of control over the variables that is far beyond anything we have access to.

As a parallel, on a purely theoretical level, we know how to construct a warp drive as well[1].

Solving a theoretical equation is one thing, replicating the prerequisite conditions experimentally is another entirely. Theoretically you can balance a perfect sphere upon another perfect sphere. In practice, you can't because setting up such an arrangement is practically impossible.

[1] https://en.wikipedia.org/wiki/Alcubierre_drive

Not in the long term, because as soon as quantum computers can practically break RSA, it would cease to be used and thus breaking RSA would become commercially irrelevant.

Currently the choice of replacements is taking its time e.g. https://www.nist.gov/news-events/news/2022/07/nist-announces... but if tonight we'd find out that people do have sufficiently powerful quantum computers, we'd just start using one of the candidates in a jiffy)

Yes, and you can test it yourself on already consumer available quantum hardware via AWS.

AWS Braket is only, at best, useful for research in quantum algorithms. It gives you access to classical simulations of QCs (which run you linear-time quantum algorithm in exponential real time), or access to some noisy real QCs (the ones whose best achievements so far are proving that 21 = 3 * 7 using a version of Shor's algorithm specialized for certain numerical properties of the number 21).

Reply on news.ycombinator.com