# Show that if language belongs to $BPP$ then also similar language belgons to $QP$

Prove that for each arbitrary set of natural numbers $A$ we have:
$$\{bin(n) | n\in A\} \in BPP \to \{0^n|n\in A\}\in QP$$ where $bin (n)$ is binary representation of $n$ $$QP = \bigcup_{c\in \mathbb{N}} DTIME\left(2^{(\log n)^c}\right)$$

I have no idea how to move from probablistic machines to non-probablisitic machine. Any ideas ?

Edit
Let us note, that $DTIME(n)\subseteq QP$, because for $c=1$ we have $2^{\log n}=n$. Now we use the fact that $BPP\subset EXP$. Let $X=\{bin(n)|n\in A\}$ will be decided by exponetnial turing machine $M$.

Now, we give machine $N$ which in $DTIME(n)$ (so in particular in $QP$) recognize $Y=\{0^n | n\in A\}$.
The $N$ works in following way:
1. Convert unary ($n$ bits) number to binary number ($\log n$) bits.
2. Launch $M$ on this converted input - it takes $2^{\log n}=n$ steps.
3. $n\in DTIME(n)\subseteq QP$.

• Can you put $BPP$ in $EXP$? Can you think of how does this help you here? – Ariel Aug 15 '17 at 14:59
• @Ariel I edited and added my thoughts. I think that it does work, however I am not sure why $BPP\subset EXP$. Can you check my thoughts and clarify $BPP\subset EXP$ ? – Haskell Fun Aug 15 '17 at 17:24
• $EXP=\bigcup\limits_{c} 2^{n^c}$, so $M$ might run in $2^{n^c}$ time, and thus your solution puts $Y$ in $QP$ rather than in linear time. – Ariel Aug 15 '17 at 19:24
• Ahhh, ok. Sol solution is almost ok. What about $BPP\subset EXP$ ? – Haskell Fun Aug 15 '17 at 20:09
• @JamesHollis, QP has nothing with quantumness, it means quasipolynomial. – rus9384 Aug 15 '17 at 20:35