6
$\begingroup$

Question: Which results in complexity theory use quantum computing to evade the algebrization barrier?

I am aware of the separation $NEXP\not\subset ACC$, which evades all barriers, but it does not involve quantum classes.$^1$ I am also aware of the result $QIP(3)=PSPACE$, but the proof seems to be a natural extension of the original proof, defeating relativization and natural proofs but not algebrization. The same holds for a recent result of Aaronson, that $PP$ does not have quantum circuits of size $O(n^k)$ for any $k$, because the only non-relativizing part is the same as in the proof that $PP$ does not have classical circuits of size $O(n^k)$, namely it uses LKNF's algebrizing theorem that the matrix permanent has an interactive proof.

This question and this question asked about barriers, but no quantum answer was given.

$^1$In fact, quantum computing seems to occupy a special place in William's proof by being one of the only branches of computer science it does not draw from!

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.