Finding cliques by quantum adiabatic evolution

Details Finding cliques by quantum adiabatic evolution Finding cliques by quantum adiabatic evolution

2000-12-19

arxiv.org/abs/quant-ph/0012104v1

Quantum Information and Computation 2, 181 (2002)

Physics

Quantum Physics

11 pages, 4 EPS figures, REVTeX

Scientific paper

Quantum adiabatic evolution provides a general technique for the solution of combinatorial search problems on quantum computers. We present the results of a numerical study of a particular application of quantum adiabatic evolution, the problem of finding the largest clique in a random graph. An n-vertex random graph has each edge included with probability 1/2, and a clique is a completely connected subgraph. There is no known classical algorithm that finds the largest clique in a random graph with high probability and runs in a time polynomial in n. For the small graphs we are able to investigate (n <= 18), the quantum algorithm appears to require only a quadratic run time.

Affiliated with

Also associated with

No associations

Rating

Finding cliques by quantum adiabatic evolution does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding cliques by quantum adiabatic evolution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding cliques by quantum adiabatic evolution will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-256667