patternMinor
Grover's algorithm on probabilistic classical machines
Viewed 0 times
classicalprobabilisticalgorithmmachinesgrover
Problem
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
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
Solution
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:
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}$$
$$F(x) = 1$$
Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output:
- $b$, if $F(a) = 0$
- $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}$$
Context
StackExchange Computer Science Q#117871, answer score: 2
Revisions (0)
No revisions yet.