tutorial at IJCAI-2001

Search Algorithms for Quantum Computers

Tad Hogg

Relative amplitudes for a 10 variable instance of 3-SAT with 40 clauses, using a quantum heuristic.

The amplitudes for the three solutions are in black. For the other assignments, colors indicate the number of conflicting clauses, ranging from 1 (red) to 11 (blue). All amplitudes are shown relative to the amplitude for one of the solutions.

The t bar shows the number of completed steps, alternating between phase adjustment (black) and mixing (purple).

The P bar shows the probability to obtain a solution.

Relative amplitudes for a 20 variable instance of 3-SAT with 80 clauses, using a quantum heuristic.

The amplitudes for the 24 solutions are in black. For the other assignments, colors indicate the number of conflicting clauses, ranging from 1 (red) to 11 or more (blue). All amplitudes are shown relative to the amplitude for one of the solutions.

description

Quantum computers, if they can eventually be built, will factor integers in polynomial time, a problem thought to be intractable for conventional machines. More directly relevant to artificial intelligence is the open question of how rapidly they can solve NP-hard combinatorial searches. Although unlikely to efficiently solve all NP problems, quantum computers may offer substantial improvement for many searches that arise in practice. This observation provides an opportunity to develop heuristic search methods for quantum computers. Quantum algorithms, operating on the entire search space at once, can exploit correlations among properties of search states. Furthermore, heuristics can pose less stringent requirements on the hardware than algorithms ignoring problem structure, thereby reducing the formidable challenge of building these machines.

Most current work on quantum computing involves hardware, error correction and general computational complexity results. Relatively little attention has been paid to devising heuristics incorporating the capabilities of quantum computers. This tutorial will help researchers familiar with the design and analysis of search heuristics participate in creating such heuristic algorithms.

This tutorial will describe the capabilities of quantum computers relevant for search, such as their ability to test exponentially many search states in about the same time conventional machines test just one. Attendees will learn how to combine these capabilities in quantum search algorithms through a variety of examples, including random 3-SAT near a phase transition in typical search cost. The tutorial will also cover techniques, both theoretical and empirical, for evaluating such algorithms and a variety of open research questions that the AI community is well-positioned to address.

The tutorial will assume some knowledge of combinatorial searches, such as satisfiability (SAT), and heuristic methods, such as hill-climbing and GSAT. Familiarity with quantum mechanics is not required.

For further background on the focus of this tutorial, see A Quantum Leap for AI in IEEE Intelligent Systems, July/August 1999.

topics