Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve (2018) | Hacker News Reader

Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve (2018)

quantamagazine.org

46 pointstheonemind14 comments

Note that this is an oracle result, which has about zero relevance to anything in our universe (because oracles don't exist in our universe). It is of purely theoretical interest to complexity theorists.

In our universe it remains unknown if there are problems that can be solved efficiently by a quantum computer but not by any classical algorithm. It is known that BQP is contained in P^#P, so proving such a result would require separating P from P^#P, which is probably nearly as difficult as separating P from NP.

Theory follows the tools available to the theorists. It is possible that ready access to quantum computation will open doors to problems that we never realized we needed to solve. Perhaps some things that today we consider just to random and chaotic to be solvable will become non-random once our thinking adapts to quantum computation. There may be many such problems hiding in plain sight.

Maybe, but none of that has much to do with this article.

Right now "ready access to quantum computation" is more dependent on experimental physics than complexity theory and the kind of work that complexity theorists do that might be relevant to practical quantum computations (like improved error correction schemes) doesn't appear to have much to do with oracle results.

One place oracle results have proven useful theoretically is in excluding many approaches to proving P != NP. It's possible that a result like this one might one day contribute to a proof separating BQP from P but we still seem to be very far away from that and I doubt this result will advance the arrival of practical quantum computers in any meaningful way.

Your definition of "relevance" seems to be that which advances the arrival of practical quantum computers. Why can't something be interesting in its own right?

(2018) but very well written! Even with a limited grasp of complexity theory, it stuck for me.

good point. it let me update the title. thanks!

So, all the buzzwords aside, I thought that you can simulate quantum computers on a Turing machine. Consequently, computers and quantum computers should be able to solve exactly the same class of problems.

They're equivalent from a computability perspective, not a complexity perspective. We don't really know whether Turing machines are capable of simulating quantum Turing machines efficiently. In fact, it's conjectured not to be the case.

quantum is the way to go for electric cars and other complex stuff

Classical computers can emulate quantum computers, so the title is obviously false.

"will ever" implies a component of time

They mean solve with a certain asymptotic time bound.

Edit: with that said, the title is written like they have a proof that classical computers can't match that time bound, but it's just strong evidence, which is definitely an advance, but not what the title implies.

Um, The Deutsch Jozsa problem. Forrelation. BosonSampling. etc.

We've had problems that only a quantum computer can do since the early days. The challenge has been finding problems which are both easy for a QC and useful to solve.

Forrelation is discussed in the article prominently. Did you read it?

Reply on news.ycombinator.com