Quantum community detection via deterministic elimination

Abstract

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.

12 pages, 8 figures

References in corpus (42)

• Statistical mechanics of complex networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Quantum computational chemistry
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• The Physics of Financial Networks
• Ranking in evolving complex networks
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Challenges and Opportunities in Quantum Optimization
• Quantum Hypergraph States
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Molecular Docking with Gaussian Boson Sampling
• Computational advantage of quantum random sampling
• Efficient phase-factor evaluation in quantum signal processing
• Using Gaussian Boson Sampling to Find Dense Subgraphs
• Complex Networks from Classical to Quantum
• Quantum query complexity of some graph problems
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Exponential quantum speedup in simulating coupled classical oscillators
• A universal programmable Gaussian Boson Sampler for drug discovery
• Towards quantum advantage via topological data analysis
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• A variational quantum algorithm for the Feynman-Kac formula
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum Quantile Mechanics: Solving Stochastic Differential Equations for Generating Time-Series
• Optimization by Decoded Quantum Interferometry
• Protocols for classically training quantum generative models on probability distributions
• Protocols for Trainable and Differentiable Quantum Generative Modelling
• The topology of data hides in quantum thermal states
• Quantum topological data analysis via the estimation of the density of states
• Multidimensional Quantum Generative Modeling by Quantum Hartley Transform