Quantum computer search algorithms can exploit the structure of hard combinatorial search problems. As with conventional (i.e., classical) heuristics, using problem structure greatly reduces search cost in many cases, compared to unstructured search. The focus of these algorithms is on average or typical behavior, not worst case performance.
A nontechnical review is Quantum Search Heuristics in A Quantum Leap for AI in the July/August 1999 issue of Intelligent Systems.
Contents of this page:
Quantum algorithms can use the structure of combinatorial search problems to improve average behavior for some classes of problems. The amount of improvement compared to classical heuristics for large problem sizes is an open question. This scaling of average behavior is distinct from the scaling of worst case performance relevant to the relationship between P and NP search problems for quantum computers.
Quantum algorithms with no classical analog are useful for some problems:
Conventional search heuristics give analogous quantum algorithms:
Tools for Quantum Algorithms, 1999, can provide the basis for more complex algorithms.
Demonstrations comparing several quantum search algorithms: a Java demonstration illustrating how amplitudes change during the search for problems up to 16 variables, and a Mathematica demonstration showing evolution of probability and the associated eigenvalue changes during the search with 5 variables.
A IJCAI-2001 tutorial on quantum computing includes animations of amplitudes for a quantum heuristic.
|
|
| A quantum algorithm shifting probability toward low conflict states of a satisfiability problem instance with 20 variables, 80 clauses. |
Quantum information processing with only a few qubits could be useful alternatives for some economic mechanisms.
Economic mechanisms using quantum information:
Human-subject laboratory experiments compare how people actually perform in quantum economic mechanisms with predictions from theory. These experiments use simulated quantum information processing, so the experimental setting provides a trusted context duplicating the information exchange properties that would be provided by quantum information processing in actual applications of these mechanisms.