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


More Features »


More Announcements »

Subject Areas

Interdisciplinary Physics

Previous Synopsis

Next Synopsis

Quantum Information

Quantum Pairs Walking

Read More »

Related Articles

Focus: Drops Falling in Clouds Make More Drops
Fluid Dynamics

Focus: Drops Falling in Clouds Make More Drops

Experiments with a simplified version of the atmosphere show that falling drops seed many smaller droplets in their wake. Read More »

Synopsis: Friction Means Life or Death for Ants
Soft Matter

Synopsis: Friction Means Life or Death for Ants

Experiments show that the mass of an object determines whether it slides down a sandy slope, which may explain why insect predators called antlions can trap ants in sand pits. Read More »

Viewpoint: Language Boundaries Driven by Surface Tension
Interdisciplinary Physics

Viewpoint: Language Boundaries Driven by Surface Tension

A new model of language evolution assumes that changes in the spatial boundaries between dialects are controlled by a surface tension effect. Read More »

More Articles