7 ms·
Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve (2018)
- itcrowd 6y ago(2018) but very well written! Even with a limited grasp of complexity theory, it stuck for me.
- theonemind 6y agogood point. it let me update the title. thanks!
- IIAOPSW 6y agoUm, 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.
- thehappypm 6y agoForrelation is discussed in the article prominently. Did you read it?
- tgflynn 6y agoNote 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.
- sandworm101 6y agoTheory 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.
- tgflynn 6y agoMaybe, 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.
- thotsBgone 6y agoYour 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?
- devit 6y agoClassical computers can emulate quantum computers, so the title is obviously false.
- ahelwer 6y ago"will ever" implies a component of time
- SilasX 6y agoThey 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.
- deleted 6y ago[deleted]
- uwu123 6y agoSo, 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.
- eunice-aiden 6y agoThey'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.
- deleted 6y ago[deleted]
- micropoet 6y agoquantum is the way to go for electric cars and other complex stuff