Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem

Biriukov, Morozov, Dyakonov, Straupe · arXiv:2604.27782 · 2026-05-01 (new submission, quant-ph) · score 9/10 (HIGH) · ← Back to digest

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.

Executive summary

Direct method-and-scope overlap with Yuan's Y4. The paper develops an explicit Grover circuit for the densest-k-subgraph problem — exactly the cardinality-constrained binary optimisation problem class Y4 targets — using a Dicke-state initialiser to restrict the search to k-subsets and a QFT-based edge-counting oracle. The construction is explicit at the gate level: vertex register (n qubits) + edge counter (L+1 qubits, L=⌈log₂(k(k−1)/2)⌉) + diffusion. The achieved oracle cost is O(k² √C(n,k)) (or O(log k · √C(n,k)) with binary search over thresholds), which is the same √C(n,k) Grover scaling Y4 achieves for cardinality-constrained search. The paper also runs full Quantum-Grover simulation up to ~20-bit search spaces and a black-box-Grover emulator beyond, fitting power-laws to the measured oracle cost as a function of N=C(n,k). The numerical fits confirm √N (Grover) scaling, with classical brute-force giving N (linear).

Main contribution

The Grover-based search restricts the search space to k-subsets via Dicke-state preparation |Dⁿ_k⟩ (Bärtschi–Eidenbenz construction, depth O(k log(n/k))), avoiding the QUBO's penalty-based feasibility. The oracle counts edges via a QFT-based adder (depth O(|E|)), compares the count to a threshold m_i using two's-complement arithmetic, applies a phase flip, and uncomputes. Threshold updates follow a Dürr–Høyer schedule (random t ∈ [0, π/4·√N]); after R consecutive failures the algorithm terminates with statistical confidence ≥1−p. The diffusion is U_diff = Uⁿ_k X^⊗n(2|0⟩⟨0|−I)X^⊗n(Uⁿ_k)^†, the Dicke-state-tailored reflection. Numerical simulations on Erdős–Rényi G(n, 0.5) graphs across k ∈ {3,…,8} fit oracle cost to power laws y = aN^b; fitted exponents are consistent with b ≈ 0.5 (Grover) versus b ≈ 1 (brute-force) and intermediate for simulated annealing.

Key constructions

Dicke-state initialisation (Sec. III): |Dⁿ_k⟩ = C(n,k)^−½ Σ_HW(x)=k |x⟩ prepared via Bärtschi–Eidenbenz O(kn) two-qubit gates and depth O(k log(n/k)).
QFT-based edge oracle (Sec. III, Fig. 2): apply QFT (Hadamards, since the counter starts in |0⟩); for each edge (i,j), apply controlled phase rotations conditioned on both vertex qubits being 1; inverse QFT yields the edge count in the L+1-qubit counter.
Threshold comparator: two's-complement subtraction C = 2^L+1 − m_i; the most-significant bit of (count + C) flags whether count ≥ m_i.
Dicke-state diffusion (Sec. III, Fig. 3): Uⁿ_k X^⊗n(2|0⟩⟨0|−I)X^⊗n(Uⁿ_k)^†, an O(nk)-gate construction that reflects about |Dⁿ_k⟩ rather than the uniform superposition.
Dürr–Høyer adaptive threshold: sample iteration count t ∈ [0, π/4·√N] uniformly; success probability per attempt ≥ 1/4; after R = ⌈log(1−p)/log(1−s)⌉ consecutive failures terminate with confidence p (R ≈ 11 for p=95%).
Total oracle cost: O(K·√C(n,k)) per problem, with K ≤ k(k−1)/2 thresholds linearly or K = O(log k) thresholds via binary search; per-iteration gate cost O(|E|L + kn) and depth O(|E| + k log(n/k)).

Detailed walkthrough

The densest-k-subgraph (DkS) problem asks for the k-vertex subgraph with the most internal edges. The conventional quantum approach is the QUBO formulation: introduce binary x_i for vertex inclusion, maximise −Σ_i<jA_ijx_ix_j subject to Σx_i=k, and enforce the cardinality constraint with a quadratic penalty λ(Σx_i−k)². Section II reviews this and notes the penalty needs λ > k(k−1)/2 — the same dynamic-range inflation that Y2's quasi-binary mixer was designed to avoid.

The paper's Section III builds an explicit Grover-based alternative that restricts the search space to feasible k-subsets from the start. Dicke states are the natural feasible-subspace initialiser: |Dⁿ_k⟩ has equal amplitude on every Hamming-weight-k computational basis state. The Bärtschi–Eidenbenz circuit prepares them with O(k log(n/k)) depth in all-to-all connectivity. The oracle for "this subset has ≥ m_i edges" works by counting edges via QFT-based addition: the QFT moves the counter to the Fourier basis where increments become phase rotations; for each edge (i,j) ∈ E in the original graph, a doubly-controlled phase rotation increments the counter when both x_i = x_j = 1; inverse QFT returns the counter to the computational basis. The comparator subtracts the threshold (two's complement) and flips a phase based on the MSB. Uncomputation restores the counter so only the phase mark survives.

The diffusion operator (Fig. 3) is the standard Grover reflection but specialised to reflect about the Dicke state rather than the uniform superposition: U_diff = Uⁿ_k X^⊗n(2|0⟩⟨0|−I)X^⊗n(Uⁿ_k)^†. Each Grover iteration thus stays inside the k-subset subspace.

The threshold-update schedule follows Dürr–Høyer: pick a random iteration count t and run; if the result has more edges than the current best m_i, update; otherwise count a failure. After R consecutive failures (R ≈ 11 for 95% confidence), terminate. This avoids needing to know in advance how many marked solutions exist at each threshold.

The complexity analysis (Sec. III) gives O(K · √C(n,k)) total oracle calls, where K is the number of distinct threshold levels (at most k(k−1)/2 linearly, or O(log k) with binary search). The √C(n,k) factor is the Grover quadratic speedup over classical √-coverage of the feasible subspace — the same scaling Y4 derives for its cardinality-constrained binary optimisation.

The numerical simulations (Sec. IV) come in two parts. (1) Fixed n=10 graph, k ∈ {4,5,6}: convergence trajectories of best-so-far edge count vs oracle calls for Quantum Grover (Aer simulation), Black-box Grover emulator (success probability fixed at 25% per call), brute-force, and simulated annealing with k-swap neighbourhood and tabu list. The Grover and Black-box-Grover curves are essentially indistinguishable, confirming that the 25% per-call success probability is the dominant determinant of convergence speed. (2) Scaling study on Erdős–Rényi G(n,0.5) graphs across k ∈ {3,…,8}: oracle cost to reach 95% certifiable optimality, fit by power laws y = aN^b. The fitted exponents are b ≈ 0.5 for both QG and BBG (Grover and emulator), consistent with √N scaling; brute-force scales linearly in N; simulated annealing exhibits intermediate behaviour over the tested range.

Section V's discussion is candid about the resource cost: the QFT-based edge oracle has substantial T-count overhead in the fault-tolerant regime, and dense input graphs (large |E|) inflate this further. They suggest future improvements via (i) approximate Dicke-state preparation; (ii) carry-save adders or blockwise edge-counting; (iii) amplitude-estimation-based Grover schedules; (iv) classical–quantum hybrid preprocessing — exactly Y4's ADMM hybrid territory.

Figures

Benchmark graph — Benchmark Erdős–Rényi-style graph with n=10 vertices used in the convergence experiments (Sec. IV).

General Grover scheme — General gate scheme of one iteration of the threshold-search algorithm: Dicke-state preparation, edge-counting oracle, diffusion, measurement.

Edge oracle — QFT-based edge-counting oracle: QFT on the counter, controlled phase rotations per graph edge, inverse QFT, comparator against threshold m_i, phase flip, and uncomputation.

Diffusion operator — Dicke-state-tailored diffusion U_diff = Uⁿ_kX^⊗n(2|0⟩⟨0|−I)X^⊗n(Uⁿ_k)^†; depth dominated by the Dicke-state preparation.

Convergence k=4 — Convergence of best-so-far edge count vs oracle calls on the n=10 benchmark graph at k=4. Solid lines: mean over 1000 runs; shaded bands: empirical 90% CIs.

Convergence k=5 — Same as left, k=5. The Grover and Black-box-Grover curves are essentially identical, confirming the 25%-per-call success-probability model.

Grover scaling — Scaling of Grover oracle cost vs search-space size N=C(n,k) for k ∈ {3,…,8}. QG: full Quantum-Grover simulation; BBG: Black-box Grover emulator. Fitted exponent b in y=aN^b consistent with the expected b ≈ 0.5 across k.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y4 (Grover + ADMM cardinality-constrained binary opt): Direct method-and-scope overlap. Y4 also uses Grover with O(√C(n,k)) rotations on a cardinality-constrained subspace; the ADMM hybrid in Y4 layers a classical decomposition on top to handle ε-approximation. This paper provides the explicit gate-level oracle circuit (QFT-based edge counting) that Y4 abstracts. A natural composition: replace the Y4 oracle abstraction with this paper's explicit gate decomposition and report concrete circuit-depth numbers for portfolio cardinality.
Y2 (quasi-binary, hard mixer): The Dicke-state initialisation is a hard-mixer-equivalent on the cardinality-constrained subspace. The "no penalty term" theme matches Y2's anti-penalty philosophy, applied to a different problem class (DkS instead of portfolio).
Y3 (DGMVP portfolio QAOA, NISQ scaling): Y3's Sec. III on QUBO formulation closely parallels this paper's Sec. II. The contrast is method (Grover here vs QAOA in Y3); the empirical scaling stories are complementary.

Recommended action for Yuan

Cite as the explicit-circuit complement to Y4: in the next iteration of Y4, this paper's Dicke-state + QFT-edge-counter oracle is a natural concrete realisation. Direct citation is warranted.
Implement and benchmark for portfolio cardinality: the densest-k-subgraph oracle generalises directly to portfolio cardinality (mean-variance with exactly-k-asset constraint becomes "k-subset of vertices with maximum −variance"). Yuan's group could plug in Y3's DGMVP instances and produce a head-to-head Grover-vs-QAOA comparison on identical instances.
Email the authors: Dyakonov / Straupe (Russian Quantum Center) work on photonic / Grover-style algorithms; the gate-level explicit construction is a natural collaboration hook for Y4's ADMM layer.