arXiv:2609.40310
Planted Cliques and Quantum Symmetry-Adapted Measurements
Vojtech Havlicek, Jordan Docter, Subhash Khot
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 $Ω(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.
AI Summary
The paper asks what information quantum encodings and symmetry-adapted measurements retain for planted-clique detection from one classical graph, particularly at $k=\lfloor n^{1/2-\varepsilon}\rfloor$, where efficient classical detection is conjectured hard. It separates statistical distinguishability from efficient measurement implementation. For a binary phase encoding on $O(\log n)$ qubits, constant-advantage detection requires $\Omega(n^{1+2\varepsilon}\ln^2 n)$ copies encoding the same graph, even with arbitrary joint measurements. The proof uses a Poissonized product-state comparison, a weighted trace-norm inequality, and bounds on overlaps of random clique locations. Separate measurements suffice with $O(n^2)$ copies, but their classical post-processing may be expensive. The bounds match at $\Theta(n^2)$ for $k=\lceil c\log_2 n\rceil$, with fixed $c>2$. Infinitely many copies identify the graph up to complementation; optimal detection then thresholds the combined clique count of both graphs. For computational-basis graph encodings, weak Schur sampling depends only on edge count and has distinguishing distance $O(k^4/n^2)$ below the square-root scale. Nevertheless, the Specht register retains trace distance $1-o(1)$ for $k\geq(2+\delta)\log_2 n$, even after discarding label and multiplicity. This follows from the planted state's small relative rank and a general bound for discarding a small register. One supplied coherent qsample also enables an $O(n^2)$-time detector above this logarithmic threshold, excluding preparation costs. No efficient detector from one classical graph is obtained: informative subgroup-isotypic measurements are proposed as an open direction, and the qsample separation assumes quantum planted-clique hardness.
We then made extensive use of ChatGPT-6 Astra at Max or Ultra settings during the writeup, with author guidance throughout.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 21 pages, no figures. Revised it to improve clarity and readability. VH takes responsibility for the previous submission prepared under a tight deadline that was far from a finished product