Single-step quantum search using problem structure

The structure of satisfiability problems is used to improve search algorith ms for quantum computers and to reduce their required coherence times by us ing only a single coherent evaluation of problem properties. The structure of random k-SAT allows the determination of the asymptotic average behavior of these algorithms, showing they improve on the quantum algorithms, such as amplitude amplification, that ignore detailed problem structure but rema in exponential for hard problem instances. Compared to good classical metho ds, the algorithm performs better, on average, for weakly and highly constr ained problems, but worse for hard cases. The analytic techniques introduce d here apply also to other quantum algorithms, supplementing the limited ev aluation possible with classical simulations, and showing how quantum compu ting can use the ensemble properties of NP search problems.