# Is PP invariant under changing its cut-off from 1/2 to another number?

Suppose I have a fixed family of quantum circuits $$\{C_i\}$$ for which determining whether the maximum output acceptance probabilities are $$p\geq 1/2$$ or $$p< 1/2$$ is PP-hard.

Now suppose I have the same family of circuits $$\{C_i\}$$, but ask for $$p\geq b$$ or $$p< b$$, for $$0, $$b\neq 1/2$$. $$b$$ may be some function that depends on the number of input bits. Then is this second problem still PP-hard?

I'm aware that normally in the definition of PP we are able to change the value of $$b$$, but this is done by amplifying and shifting the circuit a polynomial number of times so that we get a different set of circuits which are not the same as $$\{C_i\}$$ (but are polynomially equivalent).

I suppose the question boils down to: is the statement of PP-hardness that estimating $$p$$ for some particular $$b$$ is PP-hard (e.g. for $$b=1/2$$), or for all $$0 is estimating $$p$$ is PP-hard?

Edit: A summary of the question is: if we let the cut-off be $$b$$, then is it the case that $$PP(1/2)\subseteq PP(b)$$?

• No. For any constant $b<1/2$, it is PP-hard to determine whether $C$ has acceptance probability $\ge1/2$ for circuits $C$ that are guaranteed to have acceptance probability $>b$, and dually for $b>1/2$. Mar 11 '20 at 17:41
• @EmilJeřábek3.0, apologies Emil, I don't quite understand how your comment relates to the question. If b<1/2, knowing whether $p>b$ or $p<b$ doesn't tell you whether $p>1/2$ or $p<1/2$, so it's not a direct reduction (unless I'm misunderstanding you). Mar 11 '20 at 17:58
• I’m saying that for any $b\ne1/2$, there is a family of circuits for which determining if the probability is $\ge1/2$ is PP-complete, while determining if it is $\ge b$ is trivial. Mar 11 '20 at 18:19
• Perfect, thanks! Mar 11 '20 at 18:37
• A succinct answer in terms of your summary is that for any non-negligible function $f(n)$ (negligible means $f(n) = n^{-\omega(1)}$), one has that $\mathsf{PP}(1/2 + f(n)) = \mathsf{BPP}$, which is a vastly weaker class. Note that any constant function is non-negliglble. This condition holds intuitively because standard BPP amplification works for non-negligible $f$ (and therefore for $\mathsf{BPP}$, the precise cut-off doesn't matter much), but fails for negligible (or zero) $f$, so the cutoff matters much more.
– Mark
Mar 17 '20 at 16:49