RT Journal Article
T1 Quantum algorithm for testing graph completeness
A1 Giordano, Sara
A1 Martín-Delgado Alcántara, Miguel Ángel
AB Testing graph completeness is a critical problem in computer science and network theory. Leveraging quantum computation, we present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE). Our algorithm, which takes the number of nodes and the adjacency matrix as input, constructs a quantum walk operator and applies QPE to estimate its eigenvalues. These eigenvalues reveal the graph’s structural properties, enablingus to determine its completeness. We establish a relationship between the number of nodes in a complete graph and the number of marked nodes, optimizing the success probability and running time. The time complexity of our algorithm is (log2 𝑛), where 𝑛 is the number of nodes of the graph. offering a clear quantum advantage over classical methods. This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessingsystems based on pairwise comparisons.
PB Elsevier
SN 0003-4916
YR 2026
FD 2026-01
LK https://hdl.handle.net/20.500.14352/129045
UL https://hdl.handle.net/20.500.14352/129045
LA eng
NO S. Giordano, M.A. Martin-Delgado, Quantum algorithm for testing graph completeness, Annals of Physics 484 (2026) 170305. https://doi.org/10.1016/j.aop.2025.170305.
NO © 2025 The Authors.
NO European Commission
NO Ministerio de Ciencia e Innovación (España)
NO Agencia Estatal de Investigación (España)
NO Comunidad de Madrid
DS Docta Complutense
RD 20 mar 2026