Synopsis: Quantum Search for Elusive Numbers

An adiabatic quantum algorithm can calculate properties about graphs that cannot be efficiently computed on a classical computer.

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 »

Announcements

More Announcements »

Subject Areas

Interdisciplinary Physics

Previous Synopsis

Particles and Fields

Next Synopsis

Quantum Information

Related Articles

Biological Physics

Synopsis: Flocks Without Memory

Moving particles with no memory can group together in complex flock configurations using only instantaneous cues.   Read More »

Mechanics

Synopsis: Ribbon Creases and Twists

Experiments with paper ribbons show how one can predict the final shape of a loop when the ribbon’s ends are pulled tight. Read More »

Interdisciplinary Physics

Focus: Keeping a Secret for a Whole Day

Researchers have securely contained a single bit for a record 24 hours, during which it was inaccessible to both sender and recipient, a technology that could be useful for voting or bidding. Read More »