This paper addresses the problem of finding the densest $k$-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.
This paper addresses the problem of finding the densest k-vertex subgraph in an arbitrary graph. This problem is NP-hard and has important applications in social network analysis, fraud detection, recommendation systems, and bioinformatics. We propose two quantum approaches to solve this problem: reduction to Quadratic Unconstrained Binary Optimization (QUBO) and using Grover's quantum search algorithm. For the latter approach, we present an explicit gate-based oracle circuit utilizing Dicke states and Quantum Fourier Transform for edge counting. Numerical simulations demonstrate a quadratic speedup over classical Brute-force search.
We introduce a novel quantum algorithm for similar subgraph identification in form of an NP-hard cardinality-constrained binary quadratic optimization problem. Given a weighted reference graph with Laplacian B, our algorithm determines the subgraph featuring Laplacian B′ on the same vertex set, but x out of N inactive edges, minimizing the Frobenius distance ∣∣B−B′∣∣F2. We represent the (xN) graph topologies by an equal-weight superposition in form of a Dicke state, enabling controlled transformations applied to the quantum state associated with the vectorized Laplacian of the reference graph. Combined with amplitude estimation and a minimum finding approach, our algorithm provides a polynomial speed up O(Nx/x!NloglogN) compared to O(Nx+1/x!) of classical brute-force search algorithms. We demonstrate the application of our method on standard test cases, which represent electric power grids, by reconstructing ∣∣B−B′∣∣F2 from measurements and show how our approach can be additionally used to calculate energy functional like quadratic forms of the Laplacians with respect to a given vector.
The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph G with n vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, O(2n) and O(n2). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph G with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.
The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations.This work introduces two quantum algorithms for solving the 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs.We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets.Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2 5 to 2 20 .
Abstract The maximum clique problem(MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an improved algorithm that dynamically tracks the maximum clique size by encoding prior constraints on the vertex count—derived from Turán's theorem and complete graph properties—into global variables through quantum circuit pre-detection. The algorithm further synergizes with Grover's search to optimize the solution space. Our auxiliary-qubit encoding scheme dynamically tracks clique sizes during quantum search, eliminating iterative measurements, achieving MCP solution with $O\left ( \sqrt{2^{n } } \right ) $ Grover iterations and $O\left ( 1 \right ) $ measurements. This represents an n-fold improvement over state-of-the-art Grover-based methods, which require O(n2n) iterations and O(n) measurements for n-vertex graphs. We validate algorithmic correctness through simulations on IBM's Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O(N) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.
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.