2024/12/17 by Umeano, Chukwudubem, Scali, Stefano, Kyriienko, Oleksandr · 1 citation
#Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2412.13160
We propose a quantum algorithm for calculating the structural properties of complex networks and graphs. The corresponding protocol -- deteQt -- is designed to perform large-scale community and botnet detection, where a specific subgraph of a larger graph is identified based on its properties. We construct a workflow relying on ground state preparation of the network modularity matrix or graph Laplacian. The corresponding maximum modularity vector is encoded into a log(N)-qubit register that contains community information. We develop a strategy for ``signing'' this vector via quantum signal processing, such that it closely resembles a hypergraph state, and project it onto a suitable linear combination of such states to detect botnets. As part of the workflow, and of potential independent interest, we present a readout technique that allows filtering out the incorrect solutions deterministically. This can reduce the scaling for the number of samples from exponential to polynomial. The approach serves as a building block for graph analysis with quantum speed up and enables the cybersecurity of large-scale networks.