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<1$, $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<b<1$ 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)$?

  • $\begingroup$ 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$. $\endgroup$ Mar 11 '20 at 17:41
  • $\begingroup$ @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). $\endgroup$
    – user138901
    Mar 11 '20 at 17:58
  • 3
    $\begingroup$ 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. $\endgroup$ Mar 11 '20 at 18:19
  • $\begingroup$ Perfect, thanks! $\endgroup$
    – user138901
    Mar 11 '20 at 18:37
  • $\begingroup$ 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. $\endgroup$
    – Mark
    Mar 17 '20 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.