3
$\begingroup$

I am studying worst to average case reductions for different complexity classes.

Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to worst-to-average-case reductions?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ QIP=PSPACE, so "yes". QMA seems very analogous NP, so "probably not". $\endgroup$
    – Peter Shor
    Dec 6, 2021 at 0:44
  • 1
    $\begingroup$ What about QSZK? $\endgroup$
    – AngryLion
    Dec 9, 2021 at 4:53

0

Reset to default

Your Answer

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