Single-Step Quantum Search Using Problem Structure
arXiv:quant-ph/9812049 · doi:10.1142/S0129183100000663
Abstract
The structure of satisfiability problems is used to improve search algorithms for quantum computers and reduce their required coherence times by using only a single coherent evaluation of problem properties. The structure of random k-SAT allows determining the asymptotic average behavior of these algorithms, showing they improve on quantum algorithms, such as amplitude amplification, that ignore detailed problem structure but remain exponential for hard problem instances. Compared to good classical methods, the algorithm performs better, on average, for weakly and highly constrained problems but worse for hard cases. The analytic techniques introduced here also apply to other quantum algorithms, supplementing the limited evaluation possible with classical simulations and showing how quantum computing can use ensemble properties of NP search problems.
39 pages, 12 figures. Revision describes further improvement with multiple steps (section 7). See also http://www.parc.xerox.com/dynamics/www/quantum.html
References in corpus (13)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Experimental realization of a quantum algorithm
- Quantum computers can search arbitrarily large databases by a single query
- Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
- Nested quantum search and NP-complete problems
- Efficient Quantum Transforms
- Single quantum querying of a database
- Generalized Quantum Search with Parallelism
- A Framework for Structured Quantum Search
- Quantum search on structured problems
- Tools for Quantum Algorithms
- Solving Highly Constrained Search Problems with Quantum Computers