Quantum community detection via deterministic elimination
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911269226807296 |
|---|---|
| author | Umeano, Chukwudubem Scali, Stefano Kyriienko, Oleksandr |
| author_facet | Umeano, Chukwudubem Scali, Stefano Kyriienko, Oleksandr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_13160 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum community detection via deterministic elimination Umeano, Chukwudubem Scali, Stefano Kyriienko, Oleksandr Quantum Physics Disordered Systems and Neural Networks 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. |
| title | Quantum community detection via deterministic elimination |
| topic | Quantum Physics Disordered Systems and Neural Networks |
| url | https://arxiv.org/abs/2412.13160 |