Planted Cliques and Quantum Symmetry-Adapted Measurements

arXiv:2609.40310 · quant-ph, cs.CC · Submitted 2026-09-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Planted Cliques and Quantum Symmetry-Adapted Measurements".

Mira: Planted clique detection is studied through quantum encodings and symmetry-adapted measurements to probe whether quantum computation can overcome classical hardness conjectures in statistical inference.

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So, shifting gears slightly to the title and the people behind this work on "Planted Cliques and Quantum Symmetry-Adapted Measurements." The title itself tells us we're dealing with two main concepts: planted cliques and symmetry-adapted measurements.

Mira: Indeed, Kai. The focus is on using these specific measurement techniques to tackle the planted clique problem, which is a central challenge in statistical inference where classical algorithms are known to struggle.

Lev: I'm curious about the authors; what kind of expertise do we have here? Are they coming from a background that would give them insight into the quantum error correction challenges we mentioned earlier?

Kai: The authors, Vojtech Havlicek, Jordan Docter, and Subhash Khot are researchers who bring expertise from various areas of quantum computation and theoretical physics. They're tackling this by looking at both the structural encoding of the data and how we can measure it efficiently.

Mira: That mix of algebraic structure and measurement theory is exactly what makes this paper interesting, as it suggests that the underlying symmetry of a quantum state might hold the key to unlocking detection capabilities where raw counting fails.

Lev: I wonder if their background helps them handle the complexity of these proofs when we try to translate them into protocols for actual hardware, since those proofs can get pretty dense.

Kai: They are definitely coming from a place where they understand both the mathematical rigor and the experimental constraints, which is crucial when bridging the gap between theory and what we can actually cool down and measure.

Mira: I think their work sets a high bar by showing that even with known classical hardness, quantum techniques based on symmetry can extract meaningful information from these samples.

Lev: That's encouraging because it means the theoretical framework is robust enough to handle the realities of noise and limited resources that real hardware imposes.

Kai: So, looking ahead, they are laying a foundation for how we can design quantum experiments that aren't just brute-force tests but are instead tailored to exploit specific symmetries.

Mira: They aren't suggesting a single magic trick; rather they are pointing toward a systematic way to use the group structure of the state space for better inference.

Lev: That systematic approach is what we need when designing error correction codes that need to be sensitive to specific noise models, and this paper gives us tools for that.

Kai: So, the main point here is setting up a roadmap for how quantum hardware should look when we're trying to solve these kinds of structured problems.

Mira: I think they’re showing that the choice of measurement matters fundamentally in determining whether quantum computation can even make an impact in these statistical inference settings.

Lev: And if we can nail those measurement choices, then we start having concrete, testable hypotheses for what kind of hardware is needed to achieve that advantage.

Kai: That sounds like the next logical step for us in connecting this paper to our experimental reality.

Mira: Absolutely, because they’re showing that the theoretical possibility isn't just a statement about abstract states but has implications for how we design measurement circuits.

Lev: And that's exactly where my interest lies—how to build something concrete out of those theoretical ideas.

The paper's summary: Kai: So, to recap the core findings of "Planted Cliques and Quantum Symmetry-Adapted Measurements," the paper is essentially showing that they study two encodings—binary phase states and symmetry-adapted measurements—to see if they preserve enough information for planted-clique detection.

Mira: They investigate the binary phase state encoding, demonstrating that while constant-advantage detection demands (n one plustwo epsilon/ two n) copies, O(n two) copies are enough for success probability one - o(one) with separate measurements.

Lev: So, the takeaway here is that we have a clear resource requirement: we need either many copies or a specific measurement strategy to make progress against the planted-clique conjecture.

Kai: Then they move on to symmetry-adapted measurements, showing that weak Schur sampling doesn't work well for small clique sizes because its outcome only depends on the edge count.

Mira: However, the key finding is retaining the representation label and Specht register after dropping multiplicity, which preserves distance one - o(one), which means near-perfect distinguishability.

Lev: That's a significant result because it points to a specific piece of information that is robust against some types of noise or sampling limitations.

Kai: This means that the structural features encoded in the state space are more resilient than we initially thought, provided we measure them correctly.

Mira: The paper is essentially showing that the choice of measurement dictates what information survives; if you keep those specific registers, you get good results.

Lev: And for hardware implementation, this suggests we need to design circuits that specifically extract these representation labels to get the benefit they describe.

Kai: So the paper boils down to: specific encodings and measurements can indeed preserve enough information for quantum detection under planted-clique hardness.

Mira: That's the central thesis: the structure of the quantum state space itself is a powerful tool when harnessed by symmetry-adapted measurements.

Lev: It frames the resource requirements not just as a number, but as a question about which computational resources—copies versus specific information types—are most valuable for our error correction goals.

Kai: So we've got a good summary of the paper's main points, and now we can look at what these findings actually mean for future AI applications.

The paper's improvements: Mira: Moving into the suggested improvements, the paper suggests that AI systems should focus on leveraging the identified information bottlenecks to design better feature extractors.

Kai: They suggest that AI systems can use a single coherent quantum sample as a computational resource for hypothesis testing against planted-clique hardness, which is what Corollary one shows.

Lev: That single sample idea is appealing because it implies that we might not need to run huge ensembles of data or samples if we have the right quantum resource to probe it effectively.

Kai: They also suggest using collective rotation averaging on multiple copies to project the state onto a subspace that preserves both the measured label and Specht state, which can be used for detection.

Mira: That's a practical suggestion for an AI feature extractor; it means instead of just looking at raw data, we should be projecting the state onto these structurally relevant subspaces.

Lev: If we can design a protocol that performs that projection efficiently, then the quantum advantage becomes tangible in terms of how much better it is than classical methods for this task.

Kai: Regarding encoding, they highlight the trade-off: if you want constant advantage at logarithmic clique sizes, you need O(n two) copies, but parity compression can help compress the graph encoding into a parity vector.

Mira: That means for AI systems dealing with very sparse graphs or high-dimensional inputs, we can use the parity compression technique to keep the required copy complexity down while still retaining relevant structural information.

Lev: I see a clear path here: optimizing the encoding method to manage resource costs based on the specific problem instance we're facing.

Kai: And they also point to targeting specific subgroups of the clique-count-preserving group G whose isotypic measurement yields a constant distinguishing gap when k is in the hard regime, i.e., k = o(sqrt n).

Mira: That subgroup targeting gives us a specific algorithmic target for an AI system; it means we don't have to search the whole group, just this one part that is guaranteed to work effectively in those hard scenarios.

Lev: Focusing on that subgroup makes the required measurement design much more constrained and potentially easier to implement on physical devices.

Kai: So, if we combine all these points, the suggested improvements point toward designing AI systems that are not just generic detectors but are specialized tools designed around quantum symmetry and specific measurement strategies.

Mira: Exactly; it moves us away from general quantum computation towards highly tailored inference tools where structural information is explicitly preserved through the measurement process.

Lev: That’s the goal—building specialized inference modules for real-world problems, not just chasing theoretical bounds in a vacuum.

Conclusion: Kai: So, to wrap up this discussion on "Planted Cliques and Quantum Symmetry-Adapted Measurements," the paper gives us concrete targets for how quantum hardware should be set up and what information we should prioritize measuring.

Mira: We’ve established that retaining the representation label and Specht register is a key mechanism for achieving near-perfect classification when clique sizes exceed a certain logarithmic threshold, k (two + epsilon) two n.

Lev: From an error correction viewpoint, this gives us a concrete metric to aim for: we need measurement circuits that can reliably extract these specific structural features to achieve that desired distance separation.

Kai: The overall implication is that using one coherent quantum sample with these specific measurements offers a conditional computational separation under planted-clique hardness, which is a very tangible result for testing the limits of classical inference.

Mira: This means that the study provides a clear blueprint for designing AI systems that can leverage these structural properties to detect hidden structures in complex data distributions.

Lev: We need to keep pushing on the resource estimation, figuring out if those O(n two) copies are too much, because that's the final hurdle for moving this from theory to a practical quantum algorithm.

Kai: And we’re eager to see how the next round of experiments builds on these exact measurement strategies proposed in this paper.

Mira: It’s a promising direction because it moves the discussion from just "can we do it" to "how exactly should we measure it".

Lev: I think this paper provides the necessary tools for us to start designing real quantum error correction protocols that are aware of these structural symmetries.

Kai: We've got a lot to digest, but I think this is a really solid piece of work on how quantum information theory connects directly to practical problem-solving in inference.

IBM Research · Stanford University

quant-ph, cs.CC

Submitted: 2026-09-30

Updated: 2026-10-05

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

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: Planted clique detection is studied through quantum encodings and symmetry-adapted measurements to probe whether quantum computation can overcome classical hardness conjectures in statistical

Key concepts

Binary Phase State Encoding
This method represents a graph using only 'O(log n) qubits per copy,' where the edges are encoded as signs in the state's amplitudes. The analysis determines how many copies are needed for constant-advantage detection, revealing that O(n^2) copies suffice for high success probability.
Symmetry-Adapted Measurements
These measurements use tools like the Schur transform to organize quantum states into 'representation registers.' Retaining both the representation label and the Specht register preserves near-perfect distinguishability, even when multiplicity is discarded, demonstrating which information is crucial for detection.
Conditional Computational Separation
This means that given one coherent quantum sample, a quantum algorithm can efficiently distinguish between two statistical problems (P0 and P1) related to planted-clique hardness. This separation is conditional on the assumption that the planted-clique conjecture holds true.

Terminology

Summary

Planted clique detection is studied through quantum encodings and symmetry-adapted measurements to probe whether quantum computation can overcome classical hardness conjectures in statistical inference. The gist: one supplied coherent quantum sample enables an efficient quantum distinguisher, yielding a conditional computational separation from one classical sample under planted-clique hardness.

Binary Phase State Encoding

The binary phase state encoding represents a graph using only O(log n) qubits per copy, where edges are encoded as signs in the amplitudes of the state. The analysis focuses on determining the required number of copies needed for detection. For constant-advantage detection at fixed clique sizes, the paper shows that constant-advantage detection requires omega(n(1+2ε/ln2 n) copies, even under arbitrary joint measurements. Conversely, O(n 2) copies suffice for success probability 1 − o(1) using separate measurements followed by, possibly inefficient, classical postprocessing. The analysis of the large-copy limit reveals that the encoding reveals the graph up to complementation, leading to explicit Helstrom and pretty good decision rules.

Symmetry-Adapted Measurements

The study investigates measurements arising from representation-theoretic transforms, such as the Schur transform, which organize quantum states into representation registers. Weak Schur sampling, which measures only the isotypic label, shows that its outcome distribution depends only on the graph through its edge count and fails to distinguish the distributions when restricted. However, retaining the representation label and Specht register after discarding multiplicity preserves distance 1 − o(1), and Nearperfect distinguishability survives even if the label is also discarded.

Detection from One Quantum Sample

A single coherent quantum sample provides a powerful access model, enabling an efficient test. Proposition 1 demonstrates that a measurement using M Hadamard gates followed by computational-basis measurements has zero error under P0 and error at most µk under P1, where µk is related to the clique size. Corollary 1 establishes a Conditional computational separation at one sample, showing that given one coherent qsample, a quantum algorithm distinguishes P0 from P1 in O(n 2) time with success probability 1 − o(1), conditional on the planted-clique conjecture.

Level-Set Symmetries and Rank Analysis

The analysis of level-set symmetries provides a geometric picture by examining how the planted mixture relates to the null state. The planted mixture σ1 has rank o(N), while the null state σ0 has full rank. The full level-set group exposes this separation through its representation labels, giving near-perfect detection. Specifically, Proposition 8 shows that an isotypic projector annihilates the planted state and has a probability under the null of 1 − o(1), leading to a conditional label distance DG = 1 − o(1) when k = o(√n).

Comparison of Measurement Readouts

The paper compares different measurement readouts to identify which information is retained. The weak Schur label has a Distance O(k 4/n 2), while the readout retaining the label and multiplicity recovers the edge count exactly, with a distance of TV(W1, W0) = O(k 2/n). Finally, measuring the Specht register alone yields near-perfect discrimination when k ⩾ (2 + ε)log2 n for fixed ε > 0. The analysis shows that The full group label exposes the support separation that the edge-permutation label misses.

Conclusion and Open Directions

The study concludes by identifying concrete targets for efficient measurement, such as an efficient two-outcome measurement on the retained label and Specht register. It also identifies a second target: an explicitly specified subgroup of the clique-count-preserving group G whose isotypic measurement has a constant distinguishing gap. The paper notes that closing the gap between the lower bound and upper bound for phase copies requires resolving a statistical problem, and whether an efficient distinguisher can dispense with the label remains open. The results are structural and information-theoretic, focusing on how quantum encodings and symmetry-adapted measurements preserve or lose the information needed for detection.

Summary of Key Findings

  1. Binary phase states require omega(n(1+2ε/ln2 n)) copies for constant-advantage detection, though O(n 2) copies suffice for success probability 1 − o(1).

  2. Weak Schur sampling has vanishing distinguishing power when k = o(√n), with a bound of DL = O(k 4/n 2).

  3. Retaining the label and Specht register after discarding multiplicity preserves near-perfect distinguishability.

  4. One coherent qsample enables an efficient detection measurement, yielding a conditional computational separation under planted-clique hardness.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed this paper on planted-clique detection in quantum computing, focusing on its structural information-theoretic results regarding quantum encodings (binary phase states and symmetry-adapted measurements).

The paper suggests specific architectural and algorithmic improvements for AI systems—specifically quantum machine learning or inference tasks—by leveraging the identified information bottlenecks.

Here are the specific improvements and capabilities derived from this research:

)Specific Improvements to AI Systems

  1. Improvement in Quantum Hypothesis Testing via Coherent Samples:

The paper proves that a single coherent quantum sample allows for an efficient quantum distinguisher against planted-clique hardness (Corollary 1).

  • [A.3 & Corollary 1]: AI systems can be designed to utilize a single, high-quality coherent quantum sample as a computational resource. This enables detection of planted structures (like cliques) with success probability approaching 1, even when the classical input is hard for polynomial-time algorithms.

  • [A.4 & Lemma 10]: The system can approximate the full limiting experiment (which yields near-perfect discrimination) using only a moderate number of copies, specifically requiring only a budget of order O(M log M) copies to reduce error by any fixed margin (i.e., achieving detection with success probability at least 1/2 + η/2).

  1. Improvement in Feature Extraction via Symmetry-Adapted Measurements:

The paper identifies that while weak Schur sampling (measuring only the isotypic label) provides vanishing distinguishing power for planted cliques when the clique size is small, retaining the Specht register alone preserves near-perfect distinguishability above a logarithmic threshold (Corollary 2).

  • [Section 4.2.2 & Corollary 2]: AI feature extractors can be optimized to specifically measure and retain the Specht register (the irreducible representation label) of a quantum state, while discarding the multiplicity register. This retained information is sufficient to distinguish between planted cliques and null graphs when the clique size is large enough (k = (2 + ε)log2 n).

  • [Proposition 7]: The system can employ collective rotation averaging on multiple copies to project the state onto a subspace that preserves both the measured label and Specht state, which is then used for detection.

  1. Improvement in Computational Complexity via Encoding:

The paper establishes a clear trade-off between encoding methods for planted structure detection.

  • [Section 3]: For binary phase states, the system can use a compact O(log n) qubit encoding per copy to retain information useful for planted-clique detection. However, it must be aware of the required copy complexity: if constant advantage is needed at logarithmic clique sizes, the system requires O(n 2) copies.

  • [Section 3.1]: The parity compression technique allows the system to effectively compress a graph encoding into a parity vector, which is then used in the analysis to derive information-theoretic bounds on required resources.

  1. Improvement in Algorithmic Design via Structural Group Actions:

The paper suggests targeting specific subgroups of the full symmetry group that preserve clique counts (Lemma 9).

  • [Section 4.3.1 & Lemma 9]: An AI system can be designed to utilize a specific, efficiently implementable subgroup action (e.g., vertex relabelings or clique-count preserving permutations) whose associated isotypic measurement yields a constant distinguishing gap when the clique size is in the hard regime (k = o(√n)).

)What the Improved AI System Can Do

Based on these improvements, the resulting AI system can perform:

  1. [Quantum-Enhanced Anomaly Detection]: The system can detect hidden, structured anomalies (like planted cliques) in complex data distributions where classical detection is intractable, by utilizing a single coherent quantum sample and performing a specific measurement sequence tailored to the structure of the underlying distribution (e.g., using the Specht register readout).

  2. [Efficient Quantum Inference with Resource Estimation]: The system can estimate the exact quantum resources (copy complexity) required for robust detection against specific structural hypotheses, allowing researchers to determine if a problem is fundamentally hard or merely requires more resources than currently available.

  3. [Structure-Preserving Feature Mapping]: By employing symmetry-adapted measurements (like those involving the Schur transform), the system can extract arrangement-dependent correlations in quantum states—information that is lost when only edge counts are measured—allowing for a more sensitive detection of planted structures, provided the clique size is above a certain threshold.

  4. [Near-Perfect Classification under Hard Constraints]: For sufficiently large clique sizes (k = (2 + ε)log2 n), the system can achieve near-perfect classification by retaining the Specht register, effectively bypassing the limitations imposed by discarding multiplicity information in quantum measurements.

Abstract

We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For k= n 1/2-epsilon, with fixed 0< epsilon<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 epsilon squared 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.

Sources

Related papers