Finding cliques by quantum adiabatic evolution

Abstract

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.

11 pages, 4 EPS figures, REVTeX

Cited by in corpus (8)

• $XY$-mixers: analytical and numerical results for QAOA
• Deterministic Preparation of Dicke States
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Dicke-state preparation through global transverse control of Ising-coupled qubits
• Finding Small and Large k-Clique Instances on a Quantum Computer
• Lower bounds for adiabatic quantum algorithms by quantum speed limits
• Deterministic carving of quantum states with Grover's algorithm
• Generalized Parity Measurements and Efficient Large Multi-component Cat State Preparation with Quantum Signal Processing