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?

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


Your Answer

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