Quantum methods analyze planted clique detection limitations and potential
Planted Cliques and Quantum Symmetry-Adapted Measurements
Computational Complexity
Summary
The planted clique problem involves finding a special group of connected points inside a larger network, which is hard for classical computers. The authors examine two quantum ways to encode and measure this information to see if quantum methods can detect the group more efficiently. They find that some quantum approaches still need many copies of the network to detect the clique, while others show more promise in preserving information useful for detection. They also show that having one special quantum copy can help distinguish certain cases efficiently, but it remains unknown if this can be done from just one classical network sample.
What this means in practice
- •For quantum algorithm developers: Design quantum algorithms that target planted clique detection by leveraging structural insights from symmetry-adapted measurements.
- •For quantum hardware engineers: Implement efficient quantum measurement schemes inspired by the Schur transform to improve quantum data analysis for graph-based problems.
A theory result. No direct application yet.
Authors
Vojtech Havlicek, Jordan Docter, Subhash Khot
Abstract
The planted clique problem is a promising candidate for quantum advantage with a wide computational-statistical gap and substantial evidence for classical hardness. We study two quantum encodings of classical samples, a natural binary phase state encoding and symmetry-adapted measurements, and determine if they preserve enough information for planted-clique detection, as well as discuss their potential towards algorithmic efficiency. For the binary phase state encoding, we show that constant-advantage detection requires $Ω(n^{1+2\varepsilon}\ln^2 n)$ copies, even under arbitrary joint measurements. Measurements on $\tilde{O}(n^2)$ copies suffice statistically above the logarithmic clique threshold. The symmetry-adapted measurements on the full graph register arise naturally from the Schur transform. We show that the outcome distribution of weak Schur sampling depends on the sampled graph only through its edge count and fails to distinguish the distributions; whereas retaining the representation label and Specht register after discarding multiplicity preserves distance $1-o(1)$. Near-perfect distinguishability survives even if the label is also discarded. We calculate the retained states, providing concrete targets for efficient measurement. Finally, we show that one supplied coherent quantum sample enables an efficient quantum distinguisher, which yields a conditional computational separation from one classical sample under quantum planted-clique hardness. Our results are structural and information-theoretic; efficient detection from one classical graph in the conjectured hard regime remains open.