⚛️ quantum physics

Planted Cliques and Quantum Symmetry-Adapted Measurements

This paper investigates the information-theoretic limits of detecting planted cliques using quantum encodings, demonstrating that while binary phase state encoding requires many copies for detection, symmetry-adapted measurements can preserve distinguishing information and a single coherent quantum sample enables an efficient distinguisher that offers a conditional computational separation from classical methods.

Original authors: Vojtech Havlicek, Jordan Docter, Subhash Khot

Published 2026-10-01

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Vojtech Havlicek, Jordan Docter, Subhash Khot

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, there is a persistent question about where the true power of a machine lies. Scientists have long known that quantum computers, which use the strange rules of the subatomic world, can solve certain problems much faster than the best classical machines we have today. However, proving this advantage is difficult. It requires finding a specific task where a quantum machine can succeed, while a classical one is mathematically proven to fail or is so slow that it is effectively useless. One such task is the planted clique problem. Imagine a large social network where everyone has a random chance of being friends with anyone else. Now, imagine that a secret group of people has been added, and every single person in this group is friends with every other person in the group. The challenge is to find this secret group just by looking at the entire network map. For very small groups, this is easy. For very large groups, it is also easy. But for groups of a specific, medium size, it becomes a puzzle that seems impossible for any known fast algorithm to solve, even though the answer is statistically hidden in the data. This gap between what is theoretically possible to find and what is computationally possible to find is the battleground where researchers are testing the limits of quantum speed.

A team of researchers recently investigated whether quantum computers could crack this specific puzzle. They did not start by building a new algorithm to solve the problem immediately. Instead, they asked a more fundamental question: if you take a picture of the network and turn it into a quantum state, does that quantum version actually contain enough information to find the secret group? They explored two different ways of translating the network map into quantum language. The first method was a straightforward translation, turning the connections into a specific pattern of quantum waves. The second method was more sophisticated, using the natural symmetries of the network—how the map looks the same even if you swap the names of the people—to organize the quantum information.

When they tested the first, simpler method, they found a significant hurdle. To have a good chance of finding the secret group, the quantum computer would need to look at the network not just once, but many, many times. Specifically, they calculated that for a network of a certain size, the computer would need to examine roughly the square of the number of people in the network, multiplied by some extra factors, just to get a reliable signal. This is a massive amount of data. Even with the most powerful quantum measurements allowed by physics, the simple translation method requires so many copies of the network that it does not seem to offer a practical shortcut. The information is there, but it is buried so deep that extracting it efficiently seems unlikely.

The second approach, however, revealed a much more promising picture. By using a special quantum transformation that respects the symmetries of the network, the researchers found that the information about the secret group was preserved in a very specific part of the quantum state. They discovered that even if they threw away most of the quantum data, keeping only a specific component related to the arrangement of the connections, the signal remained incredibly strong. In fact, the remaining quantum state was almost perfectly distinguishable from a random network. This means that the information needed to solve the puzzle is not lost; it is just hidden in a different part of the quantum system than the simple method looked at.

The researchers also showed that if a quantum computer were given a single, perfectly prepared quantum version of the network, it could solve the problem almost instantly. This highlights a crucial difference: the difficulty is not that the information is missing, but that it is hard to access from a standard, classical description of the network. The study concludes that while the simple way of encoding the data fails to provide a shortcut, the more complex, symmetry-based method keeps the solution intact. The final challenge remains: can we build a fast, practical quantum machine that can actually read this specific part of the quantum state? The researchers have identified exactly what needs to be measured, but the engineering to do so efficiently is still an open question. Their work maps out the terrain, showing that the treasure is there, but the path to it requires a more careful and clever key than previously thought.

Technical Summary: Planted Cliques and Quantum Symmetry-Adapted Measurements

Problem Statement
The paper investigates the planted clique detection problem within the context of quantum computing, specifically addressing the conjectured computational-statistical gap. The problem involves distinguishing between two hypotheses:

Null Hypothesis ( $P_0$ ): A graph $G(n, 1/2)$ drawn from an Erdős–Rényi distribution.
Alternative Hypothesis ( $P_1$ ): A graph where a clique of size $k$ is planted in a uniformly random set of $k$ vertices.

The focus is on the regime where $k = \lfloor n^{1/2-\epsilon} \rfloor$ for a fixed $0 < \epsilon < 1/2$ . In this regime, detection is statistically possible (as the null graph rarely contains such a clique), but no polynomial-time classical algorithm is known to achieve constant-advantage detection. The central question is whether quantum resources can bridge this gap when the input is restricted to one classical graph sample, rather than a coherent quantum sample (qsample).

Methodology
The authors analyze two distinct quantum encoding strategies and the information preserved by symmetry-adapted measurements:

Binary Phase State Encoding:
- The graph is encoded into a quantum state on $O(\log n)$ qubits per copy, where edge signs determine the phases of the amplitudes.
- The study examines the copy complexity required for detection under arbitrary joint measurements.
- The analysis utilizes Fourier analysis on the hypercube and characterizes the limiting experiment as observing the graph up to complementation.
Symmetry-Adapted Measurements on the Full Graph Register:
- The graph is represented in the computational basis on $M = \binom{n}{2}$ qubits.
- The authors apply the Schur transform, which decomposes the Hilbert space under edge permutations into irreducible representations (Specht modules) and multiplicity spaces.
- They analyze three specific readout strategies:
  - Weak Schur Sampling: Measuring only the isotypic label (block index).
  - Label + Multiplicity: Measuring the label and retaining the multiplicity register.
  - Specht-Only: Discarding both the label and multiplicity registers, retaining only the Specht (representation) register.
- Additionally, the paper explores level-set symmetries, considering the group of permutations that preserve the number of $k$ -cliques (the clique-count levels) rather than just edge permutations.

Key Contributions and Results

Copy Complexity of Phase States:
- Lower Bound: For constant-advantage detection at $k = \lfloor n^{1/2-\epsilon} \rfloor$ , the authors prove that $\Omega(n^{1+2\epsilon} \ln^2 n)$ copies of the binary phase state are necessary, even with unrestricted joint measurements.
- Upper Bound: $\tilde{O}(n^2)$ copies suffice for success probability $1-o(1)$ .
- Limiting Behavior: In the limit of many copies, the encoding reveals the graph up to complementation. The optimal decision rules (Helstrom and Pretty Good Measurements) depend on the count of $k$ -cliques and independent sets, but the circular nature of these measurements does not suggest an efficient algorithmic path.
Information Retention in Schur Measurements:
- Weak Schur Sampling: The outcome distribution depends only on the edge count of the graph. For $k = o(\sqrt{n})$ , the statistical distance between the null and planted distributions is $O(k^4/n^2)$ , which vanishes. Thus, weak Schur sampling fails to distinguish the planted clique.
- Retaining Multiplicity: Measuring the label and retaining the multiplicity register recovers the edge count exactly, offering no advantage over simple edge counting.
- Specht-Only Register: Crucially, the authors show that the Specht register alone (after discarding both the isotypic label and multiplicity) retains near-perfect distinguishability ( $D = 1-o(1)$ ) for $k \ge (2+\epsilon)\log_2 n$ . This is proven via a rank bound argument: the planted state occupies a superpolynomially small fraction of the space, while the null state is maximally mixed.
- Explicit Reduced States: The paper provides explicit formulas for the reduced Specht states and identifies the operator components preserved when multiplicity is discarded (specifically, even-degree Fourier components).
Level-Set Symmetries:
- The authors construct a "full common outcome-permutation group" that preserves the number of $k$ -cliques.
- They identify a single isotypic projector $\Pi$ for this group that annihilates the planted state ( $\Pi \sigma_1 = 0$ ) but has almost full rank under the null ( $\text{rank}(\Pi) \approx N$ ).
- Measuring this label yields a distinguishing distance of $1-o(1)$ . However, implementing this measurement efficiently is shown to be as hard as solving the clique existence problem (implying $NP \subseteq BQP$ if done efficiently for all graphs).
Quantum Samples vs. Classical Samples:
- The paper demonstrates that if a coherent quantum sample (qsample) of the distribution is provided, detection can be performed in $O(n^2)$ time with success $1-o(1)$ above the logarithmic threshold.
- Under the assumption of quantum planted-clique hardness, this establishes a conditional computational separation: one coherent qsample is computationally more powerful than one classical graph sample, even when both are processed by a quantum computer.

Significance and Claims
The paper's primary contribution is structural and information-theoretic. It does not provide a polynomial-time quantum algorithm for planted clique detection in the hard regime. Instead, it:

Quantifies Information Loss: It rigorously demonstrates that certain natural quantum encodings (phase states) and symmetry-adapted measurements (weak Schur sampling) lose the necessary information for detection, while others (Specht-only states) retain it.
Defines Concrete Targets: It formulates the remaining algorithmic challenge explicitly: finding an efficient measurement on the reduced Specht states (or the level-set isotypic components) that achieves constant advantage.
Clarifies the Gap: The results suggest that the barrier to quantum advantage in planted clique is not a lack of statistical information in the quantum encoding, but rather the difficulty of efficiently accessing the information retained in specific symmetry-adapted subspaces.

The authors conclude that while the statistical gap can be bridged by specific measurements, the computational complexity of implementing these measurements remains an open problem. The work sets a foundation for future algorithmic developments by isolating the specific quantum states and operators that must be targeted to achieve a quantum advantage.

Technical Summary: Planted Cliques and Quantum Symmetry-Adapted Measurements

More like this