Synopsis: Quantum Search for Elusive Numbers

An adiabatic quantum algorithm can calculate properties about graphs that cannot be efficiently computed on a classical computer.
Synopsis figure
William G. Macready, D-Wave Systems, Inc.

The mathematician F. P. Ramsey proved in 1930 the existence of a set of numbers that reveal hidden patterns within a large structure, such as a complex graph of vertices connected by edges. Imagine that the graph edges can be given different colors: a Ramsey number is the minimum number of vertices a complete graph (i.e., one in which each pair of vertices is connected by a unique edge) must have so that every possible coloring of the edges will contain at least one monochromatic complete subgraph of specified order. These numbers are extremely difficult to compute because adding additional vertices to a graph causes an explosion in the number of graph colorings that must be checked for the desired set of (complete) monochromatic subgraphs, rapidly expanding the search time on a computer. This classically intractable behavior explains why so few Ramsey numbers are known exactly.

Frank Gaitan at the Laboratory for Physical Sciences, Maryland, and Lane Clark at Southern Illinois University, Carbondale, present, in Physical Review Letters, a quantum algorithm that computes two-color Ramsey numbers. The procedure introduces a problem Hamiltonian that covers the space of all possible graph configurations, and whose ground-state energy is zero when the number of graph vertices N is less than the (two-color) Ramsey number, and becomes nonzero when N equals the Ramsey number. A time-varying Hamiltonian is adiabatically transformed into the problem Hamiltonian, and a measurement at the end of the evolution gives its ground-state energy. The algorithm starts with N-vertex graphs, for N less than the Ramsey number, and iterates N until the ground-state energy first becomes nonzero. The corresponding N value is the desired Ramsey number.

The authors simulate their adiabatic scheme on a classical computer—which they can do for small, known Ramsey numbers—to verify the quantum algorithm, and also show that calculation of Ramsey numbers belongs to a class of hard problems that is fundamental to the theory of quantum computation. The algorithm raises the prospect of one day determining unknown Ramsey numbers using an adiabatic quantum computer. – Sonja Grondalski


Announcements

More Announcements »

Subject Areas

Interdisciplinary Physics

Previous Synopsis

Next Synopsis

Quantum Information

Quantum Pairs Walking

Read More »

Related Articles

Synopsis: Trees Crumbling in the Wind
Materials Science

Synopsis: Trees Crumbling in the Wind

Lab experiments with wooden rods help explain why all trees—irrespective of size or species—break when battered by wind blowing at the same critical speed. Read More »

Focus: Sensing Delays Control Robot Swarming
Interdisciplinary Physics

Focus: Sensing Delays Control Robot Swarming

A robot group clusters together or disperses based on each robot’s reaction time for sensing light, a finding useful for search-and-rescue missions.   Read More »

Focus: Wikipedia Articles Separate into Four Categories
Interdisciplinary Physics

Focus: Wikipedia Articles Separate into Four Categories

A study of the entire editing history of English Wikipedia shows that the articles cluster into four categories based on how frequently and how aggressively they are edited. Read More »

More Articles