Skip to content

Planted Cliques and Quantum Symmetry-Adapted Measurements

Sep 2026 · arXiv.org · Vol abs/2609.40310 · 0 citations · 42 references
Computer Science Physics

Abstract

We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires $\Omega(n^{1+2\varepsilon}\ln^2 n)$ copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of $k$-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.

View source

Similar papers

#machine learning Preprint Sep 2026

The Sample Complexity of Quantum Entanglement Allocation

How many past requests are needed to decide which qubits should share entanglement? We show that the answer depends on the allocation choices created by the queries: a larger memory can require no more data. The memory stores a classical bit and answers requests through a fixed detector that preserves coherence within...

N. Roll · 0 citations
Preprint Oct 2026

Quantum Query Complexity of Maximum Degree and its Generalizations

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $\Theta(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a...

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro et al. · 2 citations · ⚡1
Preprint Sep 2026

Quantum Sampling of Random Spanning Trees via Amortized Data Structures

A quantum algorithm that generates a uniform superposition over the spanning trees of a graph -- also known as a q-sample -- using only a sub-linear number of queries to the graph using only a sub-linear number of queries to the graph is presented.

Yassine Hamoudi, A. Tanasa, S. Sridhara · 0 citations
Preprint Oct 2026

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This...

Ze-Kun Ye · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.