4 ms·

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 t

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.

sandworm101 6y ago
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.
- tgflynn 6y ago
  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.
  - thotsBgone 6y ago
    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?

sandworm101 6y ago

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.

tgflynn 6y ago
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.
- thotsBgone 6y ago
  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?