Tag Info

10

This is not known, but as domotorp stated, it is believed not to be the case. First, note that $\mathsf{P} = \mathsf{BPP}$ doesn't say that randomness isn't useful in any context, just in the context of poly-time decision problems. For example, just assuming $\mathsf{P} = \mathsf{BPP}$ is already not known to imply that $\mathsf{AM} = \mathsf{NP}$ (and the ...

9

I believe our result shows that if the prover is capable of solving NTIME[poly(T)] problems, and has the ability to manipulate polylog(T) qubits, then they can convince the verifier of YES instances of NTIME[T] problems. In other words, roughly speaking NTIME[2^poly(Q)] = MIP*[Q] where MIP*[Q] denotes the provers being limited to Q qubits of entanglement.

5

An oracle separation is easy to show. I'm not sure which paper showed it first, but for example you can already show that there exists an oracle $X$ such that $\mathsf{NP}^X \not\subset \mathsf{QSZK}^X,$ which implies $\mathsf{AM}^X \not\subset \mathsf{SZK}^X$ because $\mathsf{NP}$ is in $\mathsf{AM}$ and $\mathsf{SZK}$ is in $\mathsf{QSZK}$. See ...

2

No, but I don't know what would count as a proof. People conjecture P=BPP and IP$\ne$NP, if that is good enough.

2

According to this paper: https://arxiv.org/pdf/1509.09180.pdf The client only needs the ability to prepare random single-qubit pure states. You may also look at this paper for more information: https://link.springer.com/article/10.1007/s00224-018-9872-3

Only top voted, non community-wiki answers of a minimum length are eligible