As a starting point for this question, I came across this question, which AIUI is citing a construction showing how to simulate quantum circuits with a $PP$ algorithm, i.e. implying quantum computation in general is in $PP$.

However, it struck me as counterintuitive to say that the only way to implement a specific example of QC, like Grover's algorithm, would be to do so by emulating a quantum computer and running it in there. I then tried to imagine what implementing it more naturally might look like, e.g. operations in terms of list items directly rather than transforming them into a quantum state vector.

For background, I understand that non-$BPP$ algorithms in $PP$ are allowed to be arbitararily close to random, and so we potentially need to repeat them exponentially many times to arrive at any particular confidence in their answer. I'm specifically interested in what a single iteration (that then needs to be repeated exponentially many times) of a Grover-like algorithm looks like. I presume, from the fact that the translation in the linked thread is 1-1, that this single iteration would be expected to take $O(\sqrt n)$ time, but please let me know if this inference is incorrect.

(I'm also presuming that this Grover-like algorithm is not in $BPP$, because otherwise search theory would be very different. It being outside $BPP$ means we're talking about a search algorithm that in practice takes $O(2^\sqrt n)$ time, which isn't going to revolutionize anything.)

Also, since $PP$ is generally defined in terms of binary decision problems and Grover's algoritm is not one, I had to extrapolate slightly about what the success criteria looks like in a $PP$ rather than $BQP$ context. The criteria I tentatively came up with is that the algorithm should be create and pick from a probability distribution over the $N$ items of a list, with the property that the most likely item to be selected is the (a, if more than one) item marked by the oracle function, i.e. it has the pluarity, but not necessarily majority, of probability mass.

That has the obvious caveats that because the list in general contains more than two items, it is not more likely than not that that item gets selected, only that no single item is more likely. The difference in probability between the most and second-most likely items being chosen is also allowed to be arbitararily small. An algorithm that returns the marked item from a list of $N$ with probability $\frac{1}{N}+2^{-N}$ would be allowed so long as all other items were less likely.

Is there any existing work on algorithms that achieve the corresponding outcome as Grover's (or similar specific quantum algorithms), but in more direct/natural terms?


1 Answer 1


Let $F$ be a function that maps integers from $0 \dots N-1$ to $\{0, 1\}$. We want to find $x$ (which is promised to be unique) such that:

$$F(x) = 1$$

Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output:

  1. $b$, if $F(a) = 0$
  2. $a$, if $F(a) = 1$

For any fixed $x$ and $y$ we have:

$$P_{a=x} = P_{b=x} = P_{a=y} = P_{b=y} = \frac{1}{N}\\ P_{a \ne x} = P_{b \ne x} = P_{a \ne y} = P_{b \ne y} = \frac{N-1}{N}$$

Knowing that $a$ and $b$ are independent random variables, the probability that we output $x$ is

$$P_{a = x \lor a \ne x \land b = x} = P_{a = x} + P_{a \ne x} P_{b = x} = \frac{1}{N} + \frac{N - 1}{N^2}$$

and the probability that we output some other value $y \ne x$ is

$$P_{a \ne x \land b = y} = P_{a \ne x} P_{b = y} = \frac{N - 1}{N^2} < \frac{1}{N}$$

  • $\begingroup$ Thanks, this is an almost perfect answer but would you mind elaborating slightly on how you got the $(N-1)/N^2$ term? I can see that we get a bias towards the correct value (and also that this problem was much simpler than I was expecting before I rewrote the OP) but not obviously why it's that form specifically. $\endgroup$
    – redroid
    Dec 4, 2019 at 1:18
  • $\begingroup$ @redroid this is just counting all the possibilities. I added the derivations. $\endgroup$ Dec 4, 2019 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.