10
votes
Accepted
If $P=BPP$, then Is it correct that $IP=NP$?
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 ...
- 36.4k
9
votes
Accepted
Does the MIP* = RE proof work for limited provers?
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 ...
- 3,718
9
votes
Accepted
Parity P and AM
By request, I’ll turn the comment into an answer.
Toda’s theorem says that $\mathrm{PH\subseteq BP\cdot\oplus P}$. Since $\mathrm{BP\cdot AM=AM}$, this shows the following implication: if $\oplus\...
- 15.6k
6
votes
Accepted
Simulating quantum measurements by unitaries
The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae.
Any circuit with an intermediate measurement can be converted ...
- 1,488
6
votes
Accepted
Separation of AM and SZK
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{...
- 13.4k
3
votes
Accepted
From CHSH inequality to CHSH game
I think your history is entirely right. Computer scientists are used to thinking about protocols as games, while physicists are not, and this is probably why these results weren't formulated as games ...
- 23.9k
2
votes
QPIP minimal client quantum capabilities
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:
...
2
votes
An Interactive Proof of God's Number?
Determining that $20$ is the diameter (God's number) of the Rubik's Cube Group $G$ under the half-turn metric with Singmaster generating set $s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$ was a ...
- 957
2
votes
If $P=BPP$, then Is it correct that $IP=NP$?
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.
- 13.9k
2
votes
Accepted
Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)
The $NP$-problem here is not the problem of finding y,z,n, but rather the following problem:
"Given a mathematical statement $A$ that can be encoded in $n$ bits, does there exist a proof of $A$ ...
- 5,290
1
vote
Accepted
Quantum complexity of TQBF with an untrusted oracle
This question is more complicated to state than its predecessor Quantum complexity of TBQF, but in hindsight it is also way easier to answer.
Theorem: The complexity is $\tilde{O}\left(2^{n/4}\right)$,...
- 3,223
1
vote
On definition of IP class
The answers above addressed your concerns, but I wanted to add a complete description of the definition of the class IP and AM and MA here as well.
Interactive Algorithms
Terminology
We have a ...
- 1,082
1
vote
Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?
Koiran's paper Hilbert's Nullstellensatz is in the Polynomial Hierarchy provides a public-coin Arthur-Merlin protocol for establishing that a system of $m$ equations on $n$ unknowns has a solution in $...
- 957
Only top scored, non community-wiki answers of a minimum length are eligible