{"id":"arxiv/2609.40310","url":"https://arxiv.org/abs/2609.40310","tags":["quant-ph","cs.CC"],"score":0,"title":"Planted Cliques and Quantum Symmetry-Adapted Measurements","domain":"quant-ph","source":"arxiv","authors":["Vojtech Havlicek","Jordan Docter","Subhash Khot"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}