Grover's Search applied to Schöning's Algorithm

Question

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?

Craig Gidney · Answer

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.

Grover's Search applied to Schöning's Algorithm

One Answer

Add your own answers!

Ask a Question