<p>I am studying worst to average case reductions for different complexity classes.</p>
<p>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?</p>

CC BY-SA 4.0
2021-12-06T00:44:27.860Z
QIP=PSPACE, so "yes". QMA seems very analogous NP, so "probably not".
Peter Shor 
CC BY-SA 4.0
2021-12-09T04:53:17.493Z
What about QSZK?
AngryLion
<quantum-computing><reductions><quantum-information><average-case-complexity><worst-case>
Worst to average case reductions for quantum complexity classes
AngryLion
# Worst to average case reductions for quantum complexity classes

(Asked by: username_0 on 2021-11-29)

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?

**Tags:** quantum-computing, reductions, quantum-information, average-case-complexity, worst-case
> **Comments:**
> **username_1**: QIP=PSPACE, so "yes". QMA seems very analogous NP, so "probably not".  
> **username_0**: What about QSZK?  

---

## 0 answers

