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

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?

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.