  Identifying a biclique with the maximum number of edges bears considerable
implications for numerous fields of application, such as detecting anomalies in
E-commerce transactions, discerning protein-protein interactions in biology,
and refining the efficacy of social network recommendation algorithms. However,
the inherent NP-hardness of this problem significantly complicates the matter.
The prohibitive time complexity of existing algorithms is the primary
bottleneck constraining the application scenarios. Aiming to address this
challenge, we present an unprecedented exploration of a quantum computing
approach. Efficient quantum algorithms, as a crucial future direction for
handling NP-hard problems, are presently under intensive investigation, of
which the potential has already been proven in practical arenas such as
cybersecurity. However, in the field of quantum algorithms for graph databases,
little work has been done due to the challenges presented by the quantum
representation of complex graph topologies. In this study, we delve into the
intricacies of encoding a bipartite graph on a quantum computer. Given a
bipartite graph with n vertices, we propose a ground-breaking algorithm qMBS
with time complexity O^*(2^(n/2)), illustrating a quadratic speed-up in terms
of complexity compared to the state-of-the-art. Furthermore, we detail two
variants tailored for the maximum vertex biclique problem and the maximum
balanced biclique problem. To corroborate the practical performance and
efficacy of our proposed algorithms, we have conducted proof-of-principle
experiments utilizing IBM quantum simulators, of which the results provide a
substantial validation of our approach to the extent possible to date.
