Abstract: A quantum algorithm for general combinatorial search that uses the underlying structure of the search space to increase the probability of finding a solution is presented. This algorithm shows how coherent quantum systems can be matched to the underlying structure of abstract search spaces, and is analytically simpler than previous structured search methods. The algorithm is evaluated empirically with a variety of search problems, and shown to be particularly effective for searches with many constraints. Furthermore, the algorithm provides a simple framework for utilizing search heuristics. It also exhibits the same phase transition in search difficulty as found for sophisticated classical search methods, indicating it is effectively using the problem structure.
Recommendations
Cites work
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Entropy of theK-Satisfiability Problem
- Exploiting the deep structure of constraint problems
- scientific article; zbMATH DE number 43238 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1149422 (Why is no real title available?)
- scientific article; zbMATH DE number 1163213 (Why is no real title available?)
- Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
- Optimization by simulated annealing
- Quantum complexity theory
- Quantum computation
- Quantum computational networks
- Quantum computers, factoring, and decoherence
- Quantum mechanical Hamiltonian models of Turing machines
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Realizable Universal Quantum Logic Gates
Cited in
(12)- Quantum search on structured problems
- Intricacies of quantum computational paths
- Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
- Information and computation: Classical and quantum aspects
- HIERARCHICAL QUANTUM SEARCH
- scientific article; zbMATH DE number 1149422 (Why is no real title available?)
- scientific article; zbMATH DE number 2020426 (Why is no real title available?)
- TOOLS FOR QUANTUM ALGORITHMS
- APPLYING QUANTUM SEARCH TO AUTOMATED TEST PATTERN GENERATION FOR VLSI CIRCUITS
- scientific article; zbMATH DE number 1406118 (Why is no real title available?)
- Experimental realization of a highly structured search algorithm
- Tree search and quantum computation
This page was built for publication: A framework for structured quantum search.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1586960)
