<p>Suppose I have a fixed family of quantum circuits <span class="math-container">$\{C_i\}$</span> for which determining whether the maximum output acceptance probabilities are <span class="math-container">$p\geq 1/2$</span> or <span class="math-container">$p&lt; 1/2$</span> is PP-hard.</p>

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

<p>I'm aware that normally in the definition of PP we are able to change the value of <span class="math-container">$b$</span>, 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 <span class="math-container">$\{C_i\}$</span> (but are polynomially equivalent).</p>

<p>I suppose the question boils down to: is the statement of PP-hardness that estimating <span class="math-container">$p$</span> for some particular <span class="math-container">$b$</span> is PP-hard (e.g. for <span class="math-container">$b=1/2$</span>), or for all <span class="math-container">$0&lt;b&lt;1$</span> is estimating <span class="math-container">$p$</span> is PP-hard? </p>

<p>Edit: A summary of the question is: if we let the cut-off be <span class="math-container">$b$</span>, then is it the case that <span class="math-container">$PP(1/2)\subseteq PP(b)$</span>?</p>

CC BY-SA 4.0
2020-03-11T17:41:26.813Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2020-03-11T17:58:32.830Z
@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).
Hans Schmuber
CC BY-SA 4.0
2020-03-11T18:19:46.190Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-03-11T18:37:18.047Z
Perfect, thanks!
Hans Schmuber
CC BY-SA 4.0
2020-03-17T16:49:19.063Z
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 Schultz-Wu
<cc.complexity-theory><complexity-classes><time-complexity>
Is PP invariant under changing its cut-off from 1/2 to another number?
Hans Schmuber
# Is PP invariant under changing its cut-off from 1/2 to another number?

(Asked by: username_0 on 2020-03-11)

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)$?

**Tags:** cc.complexity-theory, complexity-classes, time-complexity
> **Comments:**
> **username_1**: 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$.  
> **username_0**: @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).  
> **username_1**: 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.  
> **username_0**: Perfect, thanks!  
> **username_2**: 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.  

---

## 0 answers

