2
$\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?

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

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.