3

Quantum Machine Learning Algorithms: Read the Fine Print says:

By using a quantum computer, one could dramatically accelerate the simulation of quantum physics and chemistry (the original application advocated by Richard Feynman in the 1980s); break almost all of the public-key cryptography currently used on the Internet (for example, by quickly factoring large numbers, with the famous Shor’s algorithm); and maybe achieve a modest speedup for solving optimization problems in the infamous “NP-hard” class (but no one is sure about the last one).

Why is no one sure about the last point? Don't quantum computers achieve polynomial speed-ups for Circuit-SAT, an NP-hard problem that some optimization problems can be translated to?

Victory Omole
  • 2,332
  • 1
  • 10
  • 24

2 Answers2

3

I reached out to the author. Here's how I would rephrase this sentence based on our correspondence:

By using a quantum computer, one could break almost all of the public-key cryptography currently used on the Internet (for example, by quickly factoring large numbers, with the famous Shor’s algorithm); maybe dramatically accelerate the simulation of quantum physics and chemistry (the original application advocated by Richard Feynman in the 1980s); and maybe achieve a modest speedup for solving optimization problems in the infamous “NP-hard” class (but no one is sure about the last two).

With the rephrasing, the sentence makes it clear that's it's not claiming that there is a quantum speedup for factoring. It also doesn't deny that it might turn out that simulating quantum physics and solving optimizations problems can be done classically. Quantum simulation and Grover based algorithms have to be evaluated on a case-by-case basis against the best classical algorithms.

Victory Omole
  • 2,332
  • 1
  • 10
  • 24
2

Why is no one sure about the last point? Don't quantum computers achieve polynomial speed-ups for [Circuit-SAT], an NP-hard problem that some optimization problems can be translated to?

Theoretically, Grover's algorithm solves CIRCUIT-SAT problem quadratically faster than the best-known classical algorithm.

Practically, the overhead introduced by error correction introduces large constant factor that would cancel out this speedup. See for example this paper.

Of course, this could change by enhancing the hardware to be less error-prone and developing error-correction methods with less overhead.

Egretta.Thula
  • 11,986
  • 1
  • 13
  • 34