I came across this paper by Scott Aaronson and though I understand nothing of quantum computing, the fact that there was an (even hypothetical and probably unrealizable) model of ALL which he claims, theoretical or otherwise, that solves ALL.

Because ALL is apparently defined as the class (aptly) of all decision problems, this seems to completely transcend all Turing degrees and the arithmetical hierarchy, which blows my mind because this is the first I've heard of any approach, hypercomputation or otherwise, that does that.

So my question is two-fold:

  1. Does solving ALL really do what I what I just laid out above, in particular does it transcend all oracles?
  2. Does the approach laid out in the paper do that?

Yes, your understanding is correct. Note that the "programs" allowed in this paper cannot be described using a finite amount of information, since they include an infinite sequence of "quantum advice states" (one for each possible length of input). Note that if you allow such extra information with no bound on its length, it is trivial that you can compute any language: just let your advice state for inputs of length $n$ encode what all of the outputs should be on inputs of length $n$. In this case the result is more surprising since the size of the advice state is limited to being polynomial in $n$, but it is still not too shocking.

  • 2
    $\begingroup$ And the advice in this case is not just a string of length polynomial in $n$, but an entire quantum state of that many qubits. (If it were not so, there still wouldn't be enough programs to solve everything). $\endgroup$ – Henning Makholm May 20 '18 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.