# Tag Info

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 ...
• 37.4k
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,798
Accepted

• 13.7k
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,518
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 ...
• 24.8k

### Notation problem

You need to add a space after the d, before the ].

### 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.
• 14k

### 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: ...

### 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 ...
• 1,125

### 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 ...
• 1,010
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,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)$,...
• 3,263
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 \$...
• 1,125

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