Quantum search heuristics
- 14 April 2000
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 61 (5) , 052311
- https://doi.org/10.1103/physreva.61.052311
Abstract
An alternative quantum algorithm for combinatorial search, adjusting amplitudes based on number of conflicts in search states, performs well, on average, for hard random satisfiability problems near a phase transition in search difficulty. The algorithm exploits correlations among problem properties more effectively than some current heuristics, and improves on prior quantum algorithms that ignore these correlations.Keywords
This publication has 22 references indexed in Scilit:
- TOOLS FOR QUANTUM ALGORITHMSInternational Journal of Modern Physics C, 1999
- Highly Structured Searches with Quantum ComputersPhysical Review Letters, 1998
- Quantum computingReports on Progress in Physics, 1998
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Quantum Mechanics Helps in Searching for a Needle in a HaystackPhysical Review Letters, 1997
- Quantum Computers, Factoring, and DecoherenceScience, 1995
- Quantum ComputationScience, 1995
- Critical Behavior in the Satisfiability of Random Boolean ExpressionsScience, 1994
- An assumption-based TMSArtificial Intelligence, 1986
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 1985