Skip to main content
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 ...
Joshua Grochow's user avatar
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 ...
Henry Yuen's user avatar
  • 3,798
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\...
Emil Jeřábek's user avatar
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{...
Robin Kothari's user avatar
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 ...
Craig Gidney's user avatar
  • 1,518
4 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 ...
Peter Shor 's user avatar
3 votes

Notation problem

You need to add a space after the d, before the ].
Pierre Jouvelot's user avatar
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.
domotorp's user avatar
  • 14k
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: ...
Bassem Khoury's user avatar
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 ...
Mark S's user avatar
  • 1,125
2 votes

Is the protocol perfect zero knowledge?

Zero-knowledge proofs do not in general compose in parallel. See this paper by Feige and Shamir for a (contrived) counterexample. Beyond this counterexample, there are several constraints to actually ...
lamontap's user avatar
  • 1,010
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$ ...
Or Meir's user avatar
  • 5,615
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)$,...
Geoffrey Irving's user avatar
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 $...
Mark S's user avatar
  • 1,125

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