= Permutation-preimage quantum search
{title2=$O(\sqrt{N/K})$}
To find an input of a <permutation> whose output lies in a known $K$-element subset, compute the output, apply its <marked-state phase oracle>, and use <uncomputation>. A <modular-addition quantum oracle> costs two forward queries per marked reflection, because <modular-oracle inversion by negation> supplies its inverse. <Amplitude amplification> then uses $O(\sqrt{N/K})$ queries for fixed success probability. Positive-square outputs have $K=\lfloor\sqrt{N-1}\rfloor$ and hence query cost $O(N^{1/4})$.
Back to article page
