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$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.