Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication Related

Topics

Quantum Optimization Quantum Simulation

Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem

arXiv
Authors: Yu. A. Biriukov, R. D. Morozov, I. V. Dyakonov, S. S. Straupe

Year

2026

Paper ID

56508

Status

Preprint

Abstract Read

~2 min

Abstract Words

87

Citations

0

Abstract

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.

Why This Paper Matters

  • This paper contributes to the Quantum Simulation research area in the Quantum Articles archive.
  • It adds a 2026 reference point for readers tracking recent quantum research.
  • This paper addresses the problem of finding the densest k-vertex subgraph in an arbitrary graph.

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in
Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:2604.27782 [2] arXiv https://arxiv.org/abs/2604.27782 [3] Publisher https://arxiv.org/abs/2604.27782

Local Citation Graph (Related-Paper Links)

Current Paper #56508 #78846 Analog quantum simulation of Sh... #78810 Secure Quantum Handshakes: Quan... #78802 Quantum Co-Design of Inhomogene... #78801 Constructing Large and Structur...

External citation index: OpenAlex citation signal • updated 2026-10-20 00:26:20

Community Reactions

Quick sentiment from readers on this paper.

Score: 0
Likes: 0 Dislikes: 0

Sign in to react to this paper.

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.