3
$\begingroup$

In this paper by Ambainis, he talks about the applicability of Grover's Search to Schöning's algorithm for solving the 3SAT problem to obtain a runtime of $O(\sqrt{1.329...^n}$.

In the original algorithm by Schöning, the algorithm is repeated for $1.329^n$ time to obtain a constant success probability. Ambainis states the following: "To obtain a quantum algorithm, we just use quantum amplitude amplification instead of classical repetition."

I don't understand here at what stage we apply Grover's Search. For instance, what is the search space on which we are applying Grover's Search?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The Grover search is applied to the randomness that's fed into Schoning's algorithm. The randomness could be a big list of random bits, or for simplicity just a seed for a PRNG. You're searching over the seeds for one that causes Schoning's algorithm to succeed.

Given an oracle (Schoning's algorithm) which accepts $(3/4)^n$ of its possible inputs, you only need $O(\sqrt{(4/3)^n)})$ Grover steps to find one of those satisfying inputs.

This general strategy of searching over the randomness will accelerate any algorithm whose runtime is bottlenecked by the need to repeat many times until you get a lucky hit.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the answer. But what about the size of the list of random bits? At each one of the 3N iterations, we may negate one of the n literals which makes n^3n possible assignments for random bits. $\endgroup$
    – usercs
    Oct 22, 2020 at 16:15
  • $\begingroup$ I guess I see. Among n^3n elements, (3/4)^n fraction of them are marked, resulting in square root of 4/3. $\endgroup$
    – usercs
    Oct 22, 2020 at 16:20

Your Answer

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

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