5 ms·

> We know an ideal quantum computer provides an exponential speed-up in commercially relevant applications Do we know that though?

civilized 4y ago
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 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.
- sdgdfgsfdfgsdfg 4y ago
  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.
  - civilized 4y ago
    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.
    - effie 4y ago
      This paper claims quantum computer can integrate arbitrary non-linear differential equations with quantum advantage: https://arxiv.org/pdf/2011.06571.pdf https://arxiv.org/pdf/2011.06571.pdf It does seems too good to be true.
      - civilized 4y ago
        I found a layman's explanation at Quanta Magazine: https://www.quantamagazine.org/new-quantum-algorithms-finally-crack-nonlinear-equations-20210105/ 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
  - geysersam 4y ago
    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.
  - typon 4y ago
    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.
  - PeterisP 4y ago
    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.
typon 4y ago
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)
- marcosdumay 4y ago
  Well, those two small niches plus biological research are bottlenecks is pretty much any production process we have with real things.
reedf1 4y ago
Yes, and you can test it yourself on already consumer available quantum hardware via AWS.
- tsimionescu 4y ago
  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).
jnwatson 4y ago
Breaking RSA and ECC is commercially relevant.
- naasking 4y ago
  > Breaking RSA and ECC is commercially relevant. Yes, but we don't actually know that we can build such a device.
- marginalia_nu 4y ago
  If you can break RSA once using say a $34 billion machine that is a one-shot operation, is it really commercially relevant?
  - Jweb_Guru 4y ago
    With the number of qubits required to break RSA, there's no reason why general purpose computing wouldn't be possible.
    - marginalia_nu 4y ago
      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 https://en.wikipedia.org/wiki/Alcubierre_drive
- PeterisP 4y ago
  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-first-four-quantum-resistant-cryptographic-algorithms 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)

civilized 4y ago

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

sdgdfgsfdfgsdfg 4y ago
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.
- civilized 4y ago
  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.
  - effie 4y ago
    This paper claims quantum computer can integrate arbitrary non-linear differential equations with quantum advantage: https://arxiv.org/pdf/2011.06571.pdf https://arxiv.org/pdf/2011.06571.pdf It does seems too good to be true.
    - civilized 4y ago
      I found a layman's explanation at Quanta Magazine: https://www.quantamagazine.org/new-quantum-algorithms-finally-crack-nonlinear-equations-20210105/ 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
- geysersam 4y ago
  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.
- typon 4y ago
  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.
- PeterisP 4y ago
  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.

typon 4y ago

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)

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

reedf1 4y ago

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

tsimionescu 4y ago
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).

jnwatson 4y ago

Breaking RSA and ECC is commercially relevant.

naasking 4y ago
> Breaking RSA and ECC is commercially relevant. Yes, but we don't actually know that we can build such a device.
marginalia_nu 4y ago
If you can break RSA once using say a $34 billion machine that is a one-shot operation, is it really commercially relevant?
- Jweb_Guru 4y ago
  With the number of qubits required to break RSA, there's no reason why general purpose computing wouldn't be possible.
  - marginalia_nu 4y ago
    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 https://en.wikipedia.org/wiki/Alcubierre_drive
PeterisP 4y ago
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-first-four-quantum-resistant-cryptographic-algorithms 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)