  The maximal clique problem, to find the maximally sized clique in a given
graph, is classically an NP-complete computational problem, which has potential
applications ranging from electrical engineering, computational chemistry,
bioinformatics to social networks. Here we develop a quantum algorithm to solve
the maximal clique problem for any graph $G$ with $n$ vertices with quadratic
speed-up over its classical counterparts, where the time and spatial
complexities are reduced to, respectively, $O(\sqrt{2^{n}})$ and $O(n^{2})$.
With respect to oracle-related quantum algorithms for the NP-complete problems,
we identify our algorithm to be optimal. To justify the feasibility of the
proposed quantum algorithm, we have successfully solved an exemplified clique
problem for a graph $G$ with two vertices and one edge by carrying out a
nuclear magnetic resonance experiment involving four qubits.
