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.


9

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\mathrm P\subseteq\mathrm{AM}$, then the polynomial hierarchy collapses to $\mathrm{PH=AM=coAM}$. (In fact, the whole $\mathrm{Mod_2PH}$ hierarchy collapses to $\...


6

This question seems a little confused. The class of decision problems solvable efficiently on a quantum computer is BQP, while on a classical computer it is either P or BPP depending on exactly how you define things. An interactive proof is something entirely different. It is a protocol which allows a prover to prove, beyond reasonable doubt, the outcome of ...


6

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 to a circuit that only has measurement as the last step. Doing so involves performing three simple transformations again and again: Moving measurements onto a ...


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

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 wonderful result. I'm curious about follow-up questions, such as determining how many half-turn twists $m$ it would take to get the cube fully "mixed" to $\epsilon$...


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


1

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)$, using a single call to Grover's algorithm to check if there is a path falsifying the oracle. Moreover, this is optimal in the black box case. Consider a TBQF ...


1

In his simplified proof of the parallel repetition theorem, Holenstein gives the following explicit bound on the value of the $n$-fold parallel repetition of a game with value $v$: $$ \left(1-\frac{(1-v)^3}{6000}\right)^{n/\log(|\Sigma_1|\cdot |\Sigma_2|)}, $$ where $\Sigma_1, \Sigma_2$ are the alphabets of the two players. It's not clear to me that Raz's ...


1

The prover and the simulator must both be able to generate the proof, but given different inputs. The Prove functionality gets as input the CRS $\sigma$, the statement $y$ and the witness $w$, and outputs $\pi$. The soundness requirement postulates that nobody should be able to create $\pi$ for $y \not\in L$, given $\sigma$ as an input. However, zero-...


1

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 prover $P$, a verifier $V$, and they are talking about some problem with language $L$. They are given a string $x$ that both can see, then $P$ is trying to ...


1

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 $\mathbb{C}^n$, contingent on the Generalized Riemann Hypothesis. Here Merlin finds a prime $p$ with $H(p)=0$ for some random hash $H$, along with a solution $(...


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