SINGLE-STEP QUANTUM SEARCH USING PROBLEM STRUCTURE

Tad Hogg ()
Additional contact information
Tad Hogg: Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA 94304, USA

International Journal of Modern Physics C (IJMPC), 2000, vol. 11, issue 04, 739-773

Abstract: The structure of satisfiability problems is used to improve search algorithms for quantum computers and to reduce their required coherence times by using only a single coherent evaluation of problem properties. The structure of randomk-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 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 apply also to other quantum algorithms, supplementing the limited evaluation possible with classical simulations, and showing how quantum computing can use the ensemble properties of NP search problems.

Keywords: Quantum Computing; Quantum Algorithms; Satisfiability; NP-complete Search (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183100000663
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:11:y:2000:i:04:n:s0129183100000663

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183100000663

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().