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

Focus: Why Language Exceptions Remain the Rule
Interdisciplinary Physics

Focus: Why Language Exceptions Remain the Rule

Interaction among speakers of a language may explain why frequently used verbs tend to remain irregular even as language evolves over generations. Read More »

Synopsis: Critical Markets
Nonlinear Dynamics

Synopsis: Critical Markets

Financial markets can behave like critical systems in which small perturbations have an anomalously high impact on trading prices. Read More »

Focus: Heavily Interconnected Economies Are Vulnerable to Shocks
Interdisciplinary Physics

Focus: Heavily Interconnected Economies Are Vulnerable to Shocks

A network analysis finds that the European economies with the most interconnections, like Germany, are the most vulnerable to economic crises in the absence of government intervention. Read More »

More Articles