Does Raz and Tal 2018 (linked) falsify the Extended Church-Turing Hypothesis?

98 Views Asked by At

In the paper Oracle Separation of BQP and PH, Raz and Tal exhibit an algorithm that is in complexity class BQP but not in PH.

Question: Does their proof invalidate the Extended Church-Turing Hypothesis? (Note: the Extended Church-Turing Hypothesis is not the same as the Church-Turing Hypothesis)

1

There are 1 best solutions below

0
On

In the paper Oracle Separation of BQP and PH, Raz and Tal exhibit an algorithm that is in complexity class BQP but not in PH.

This is not what the paper is showing. The paper is showing a problem that can be solved in a $BQP^O$ but not in $PH^O$. This doesn't imply that BQP is different than PH. (For example, IP=PSPACE but there is an oracle such that $IP^O \neq PSPACE^O$.)

Before this paper, there was already a known oracle separation between BQP and BPP (e.g. https://cs.stackexchange.com/questions/13528/). The paper improved it to BQP and PH. While this is a breakthrough, I don't think this difference matters much for the extended Church-Turing thesis. We already knew that if we allow oracles, BQP is strictly more powerful than BPP.

The extended Church-Turing thesis is about computation without oracles. To invalidate the extended Church-Turing thesis this way, we would have to show BQP $\neq$ BPP in the normal, unrelativized world.