Two Quasi-Non-Trivial Questions in Quantum Complexity

\(
\newcommand\cc{\textsf}
\newcommand\UP{\cc{UP}}
\newcommand\coUP{\cc{coUP}}
\newcommand\NP{\cc{NP}}
\newcommand\coNP{\cc{coNP}}
\newcommand\IP{\cc{IP}}
\newcommand\QIP{\cc{QIP}}
\newcommand\PP{\cc{PP}}
\newcommand\PSPACE{\cc{PSPACE}}
\newcommand\QSZK{\cc{QSZK}}
\newcommand\SZK{\cc{SZK}}
\newcommand\CZK{\cc{CZK}}
\newcommand\PZK{\cc{PZK}}
\newcommand\BPP{\cc{BPP}}
\newcommand\BQP{\cc{BQP}}
\newcommand\QMA{\cc{QMA}}
\newcommand\PH{\cc{PH}}
\newcommand\AM{\cc{AM}}
\newcommand\BQNC{\cc{BQNC}}
\newcommand\P{\cc{P}}
\)

Question 1

Can you always parallelize the quantum part of a quantum computation; more precisely, is there even a relativised world where \( \BPP^{\BQNC} \neq \BQP \)?

Question 2

Is there a relativised world where \( \QIP(2) \not\subseteq \AM \)?

Some notes

The first problem was apparently first stated by Richard Jozsa and is also mentioned in Scott Aaronson’s Projects aplenty post but it deserves more press. When I say relativisation, I mean classical relativisation. Also, I am only interested in the decision problem versions of these classes.

Leave a Reply

Your email address will not be published. Required fields are marked *