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


Features

More Features »

Announcements

More Announcements »

Subject Areas

Interdisciplinary Physics

Previous Synopsis

Next Synopsis

Quantum Information

Quantum Pairs Walking

Read More »

Related Articles

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 »

Synopsis: Pinpointing Ebbs and Flows of Commuter Traffic
Interdisciplinary Physics

Synopsis: Pinpointing Ebbs and Flows of Commuter Traffic

Vulnerabilities in a city’s public transport system are identified through a network analysis that accounts for the number of passengers and vehicles at any given time. Read More »

Focus: Imaging with Your Wi-Fi Hotspot
Interdisciplinary Physics

Focus: Imaging with Your Wi-Fi Hotspot

The Wi-Fi signals that provide internet access can also produce images of the transmitter’s 3D surroundings, even through walls. Read More »

More Articles