PaperlayerView exact revision on arXiv

Source-linked AI summary

Planted Cliques and Quantum Symmetry-Adapted Measurements

Vojtech Havlicek, Jordan Docter, Subhash Khot

arXiv:2609.40310v1quant-phcs.CC

TL;DR

Planted-clique detection poses a quantum-advantage question in a conjectured computational–statistical gap. The paper studies binary phase-state encodings and symmetry-adapted measurements on the graph register. It finds substantial copy requirements for the phase encoding and near-perfect distinguishability in retained Schur registers, while efficient measurement from one classical graph remains unresolved.

  • Problem

    The paper asks whether quantum computation can make inference efficient in a computational–statistical gap, using planted-clique detection as its setting.

    Source: §1 · p. 3

  • Method

    The paper analyzes binary phase-state encodings and Schur-transform-based symmetry-adapted measurements of the full graph register.

    Source: §1 · p. 4, §4.2 · p. 18, §5 · p. 31

  • Results

    Binary phase states require Ω(n1+2ε ln2 n) copies for constant-advantage detection at k = ⌊n1/2−ε⌋, while retained Specht states preserve near-perfect distinguishability.

    Source: §1 · p. 4, §5 · p. 31

  • Takeaways & Limitations

    Explicit reduced-state formulas make distinguishing the retained Specht states a concrete algorithmic question, although its computational complexity remains open.

    Source: §5 · p. 31

    The clique-count-preserving group supplies a statistical benchmark, but its definition does not provide an efficient implementation.

    Source: §4.4.1 · p. 28

Abstract

from arXiv · show

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 $\Omega(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.

1 Introduction

The introduction frames planted-clique detection as a test of whether quantum resources can help within a computational–statistical gap. It studies binary phase-state encodings and symmetry-adapted measurements, finding distinct information limits and measurement targets.

1 Introduction

  • One supplied coherent qsample permits an O(n^2)-time test with success 1 −o(1) above the logarithmic threshold, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.Source: §1 · p. 4
  • At k = ⌊n1/2−ε⌋, constant-advantage detection from binary phase states requires Ω(n1+2ε ln2 n) copies even under unrestricted joint measurements; ˜O(n2) copies suffice statistically above the logarithmic threshold.The sufficient-copy guarantee allows measurements followed by possibly inefficient classical postprocessing.Source: §1 · p. 4
  • For k = o(√n), weak Schur sampling has distinguishing distance DL = O(k4/n2), while retaining the Specht register preserves near-perfect distinguishability even after discarding the label and multiplicity.In the stated range (2 + δ) log2 n ⩽ k = o(√n), the retained Specht states have trace distance 1 −o(1).Source: §1 · p. 4
  • The reduced Specht states are calculated explicitly, making their discrimination a concrete measurement problem whose computational complexity remains open.An efficient constant-advantage measurement on these states would give an efficient planted-clique distinguisher.Source: §1 · p. 5
  • After discarding multiplicity while retaining label and Specht information, collective averaging preserves every nonzero even-degree Fourier component, whereas edge averaging removes arrangement-dependent components.The analysis identifies available operator components without asserting that each survives erasing the label.Source: §1 · p. 5
  • The clique-count-preserving group’s isotypic measurement retains almost all distinguishing power, but its implementation on arbitrary graph inputs would already permit clique-existence tests.The group gives a statistical benchmark; its description alone supplies no efficient circuit.Source: §1 · p. 5

2 Preliminaries

The preliminaries define planted-clique detection and show how symmetries relate worst-case planted locations to a uniform mixture. They distinguish processing a classical graph from receiving a coherent quantum sample, which enables efficient detection under stated conditions.

2.1 Detection from one classical graph

  • Planted-clique detection asks whether one graph drawn under equal priors came from the null or planted hypothesis.The null is G(n, 1/2); under the planted law, a uniformly chosen k-vertex set is made into a clique.Source: §2.1 · p. 6

2.2 Worst-case planted locations and the uniform mixture

  • Random vertex relabeling symmetrizes a test so its advantage is the same for every clique location as for the uniform planted mixture.The argument applies to the classical test setting described here.Source: §2.2 · pp. 6–7

2.3 Quantum samples versus quantum processing of a sample

  • For k ≥ (2 + δ) log2 n, one coherent qsample supports a measurement with zero error under P0 and error at most µk under P1, giving equal-prior success 1−o(1).The measurement uses M Hadamard gates followed by computational-basis measurements.Source: §2.3 · p. 7
  • Under the quantum planted-clique conjecture, one coherent qsample yields O(n^2)-time detection with success 1−o(1), while one classical graph admits no uniform polynomial-time quantum distinguisher with fixed positive advantage.The conditional separation applies at k = ⌊n^1/2−ε⌋ for fixed 0 < ε < 1/2.Source: §2.3 · p. 8
  • The computational separation concerns the input resource, not a lack of statistical information in the classical input.Measuring a qsample in the graph basis produces an ordinary sample, whereas retaining coherence permits a different test.Source: §2.3 · p. 8

3 Binary Phase States

This section introduces a compact binary phase-state encoding of a graph and analyzes its tensor powers through parity coordinates. The encoding is lossy, retaining at most the graph up to complementation.

3 Binary Phase States

  • The binary phase-state encoding represents a graph using O(log n) qubits per copy, and repeated copies encode the same sampled graph rather than independent graph samples.The restriction to the Hamming weight-one coordinates makes distinct graph encodings generally non-orthogonal.Source: §3 · p. 9, §3.1 · p. 9

3.1 Phase-state encoding

  • Complementing a graph changes its phase state only by a global sign, so the encoding retains at most the graph up to complementation.The encoding is therefore inherently lossy.Source: §3.1 · p. 9

3.1.1 Parity compression

  • In tensor powers, repeated edge signs cancel in pairs, and the states can be compressed to parity coordinates with weights from a coordinate-flip walk.The graph-independent map Vt is an isometry for analysis; no efficient implementation is assumed.Source: §3.1.1 · pp. 9–10

3.2 Copy complexity

The section bounds the copy complexity of binary phase-state detection and characterizes the limiting experiment. It derives optimal limiting decision rules, a near-perfect distinguishability regime, and a finite-copy budget that approaches that limit.

3.2.1 Lower bound

  • For fixed 0 < ε < 1/2, when k = ⌊n^(1/2−ε)⌋, the stated scale is t = Ω(n^(1+2ε) ln^2 n), with its constant allowed to depend on ε.Source: §3.2.1 · p. 10
  • The lower-bound proof tracks planted-case sign correlations, bounds trace distance through weighted squared entries, and estimates them using overlap between candidate clique locations.The parity label alone reveals no signal; the ensemble difference lies in coherences.Source: §3.2.1 · pp. 10–11

3.2.2 The limiting states and their character basis

  • In the limiting experiment, different graph-complement classes give orthogonal character states, and the experiment is statistically equivalent to observing the graph up to complementation.The compressed ensembles converge in trace norm at fixed n and k.Source: §3.2.2 · pp. 13–14, The limiting laws satisfy · p. 14

3.2.3 Helstrom and PGMs

  • The limiting Helstrom rule accepts when Z(y) > µ, while the PGM accepts with probability Z(y)/(Z(y) + µ).When µ < 1, their accepting eigenvalues differ by at most µ/(1 + µ).Source: §3.2.3 · p. 14

3.2.4 Detection in the limiting experiment

  • The limiting trace distance is 1−o(1) whenever µ=o(1), including k ≥ (2 + ε) log2 n for fixed ε > 0.The precise sufficient condition is µ=o(1); the analysis does not sharpen the clique-number critical window.Source: §3.2.4 · p. 15

3.2.5 Approaching the limiting experiment

  • O(M log M) copies yield trace distance 1−o(1) whenever µ=o(1), approaching the limiting experiment uniformly in k.Here M is the number of graph edges.Source: §3.2.5 · pp. 15–16

3.3 Computational scope

The computational scope discussion separates the phase encoding’s statistical information from the efficiency of extracting it. It leaves efficient detection from a classical graph in the conjectured hard regime unresolved.

3.3 Computational scope

  • At k = ⌊n^1/2−ε⌋, necessary and sufficient phase-state copy counts lie between Ω(n^1+2ε ln^2 n) and ˜O(n^2).The remaining copy-complexity gap is statistical, while efficient extraction of the signal is a separate algorithmic question.Source: §3.3 · p. 16
  • A few more copies, t=˜O(M), permit recovery of [G]={G, Ḡ}, while a classical graph representation permits efficient preparation of polynomially many phase copies.The limiting Helstrom and PGM rules depend on monochromatic cliques, but this does not establish computational hardness; efficient detection from one classical graph remains open.Source: §3.3 · p. 16

4 Symmetry-Adapted Measurements

The section compares symmetry-adapted Schur readouts, separating edge-count information from edge-arrangement information. Weak Schur sampling is limited, while retaining Specht information or changing the permutation action gives statistically powerful measurement targets whose efficient accessibility remains open.

4 Symmetry-Adapted Measurements

  • Weak Schur sampling depends only on edge count and has vanishing distinguishing power when k = o(√n).The Specht register alone permits near-perfect discrimination above the fixed-margin logarithmic threshold, even without a label to select its measurement.Source: §4 · p. 17
  • After measuring the label, retaining it with multiplicity is statistically equivalent to observing the edge count.The Specht register alone still permits near-perfect discrimination when the label is erased.Source: §4 · p. 17
  • Changing the permutation action yields an isotypic measurement that preserves almost all distinguishing distance in the stated regime.The results identify concrete measurement targets, but whether their statistical power can be accessed efficiently remains open.Source: §4 · p. 17

4.1 Planted-clique distribution symmetries

The two graph distributions share vertex-relabeling symmetry, while only the null is invariant under arbitrary edge permutations. Averaging over edge permutations preserves edge-count information and isolates the planted signal in edge arrangements.

4.1 Planted-clique distribution symmetries

  • Both distributions are invariant under vertex relabeling, but only the null is invariant under every edge permutation.Arbitrary edge permutations can alter which edge positions share a vertex, unlike vertex relabeling.Source: §4.1 · p. 17
  • Functions invariant under every edge permutation depend only on edge count, since graphs with equal edge counts lie in the same orbit.Averaging preserves the edge-count law and makes the graph uniform conditional on that count.Source: §4.1 · p. 17
  • The probability difference separates into an edge-count component and a vertex-invariant component orthogonal to every function of edge count.The latter records edge arrangements within each count class and is identified as the structural part of the planted signal.Source: §4.1 · p. 17
  • The graph-state density operators commute with the corresponding group actions, but this does not imply support only on invariant vectors.For edge permutations, the null coherent qsample lies in the trivial sector, whereas the maximally mixed null has support in every sector.Source: §4.1 · p. 18

4.2 Schur Sampling

This section examines Schur-transform-based measurements on the edge-qubit register, comparing readouts that retain or discard the measured label and their implications for measurements on the Specht register. It characterizes the information preserved by weak Schur sampling and by the Specht register, including their behavior above the fixed-margin logarithmic clique threshold.

4.2 Schur Sampling

  • The Schur transform decomposes the M edge qubits into irreducible-representation blocks and admits a poly(M, log(1/ϵ))-size implementation to accuracy ϵ.Each block has a Specht factor and a multiplicity factor; the transform's encoded coordinates can be implemented efficiently for qubits.Source: §4.2 · p. 18

4.2.1 Weak Schur sampling see only edge count

  • Weak Schur sampling depends on a graph only through its edge count, so it loses edge-arrangement information and has vanishing advantage below the square-root scale.For the computational-basis encoding, its distinguishing distance is bounded by the total-variation distance between the edge-count distributions; the refined rate vanishes when k=o(√n).Source: §4.2.1 · pp. 19–20

4.2.2 Comparing Schur readouts

  • For fixed ε>0 and (2+ε)log2 n ≤ k=o(√n), weak-label distance is O(k^4/n^2), label-plus-multiplicity distance is TV(W1, W0)=O(k^2/n), and Specht-only distance is 1−o(1).The Specht-only conclusion gives detection success probability 1−o(1) for every fixed ε>0 and k ≥ (2+ε)log2 n.Source: §4.2.2 · pp. 20–22
  • Measuring the label and retaining multiplicity recovers exactly the edge-count signal, while a measurement on the Specht register alone achieves near-perfect detection above the fixed-margin logarithmic threshold.The paper establishes the Specht-only distinguishing result but gives no efficient circuit for the support-projector measurement; the retained register occupies M−O(log M) qubits with compact storage.Source: §4.2.2 · pp. 21–22

4.2.3 Explicit reduced states

  • Collective averaging yields explicit reduced states: it preserves the label probabilities and corresponding Specht states while replacing multiplicity by a maximally mixed state within each block.The averaged planted state is described using a positive contraction formed from clique-edge symmetrizers, and collective averaging preserves the Specht marginals.Source: §4.2.3 · pp. 22–24
  • The factor r_i arises from tracing the identity on the multiplicity space.Source: §4.2.3 · p. 24
  • With the label retained, a measurement may depend on i; on the Specht register alone, one effect must act on the summed state.When the label is discarded, contributions are added on the common physical Specht register.Source: §4.2.3 · p. 24
  • Zero-padding is essential because the summed operators come from Specht spaces of different dimensions.Source: §4.2.3 · p. 24

4.3 Operator symmetries

Operator averaging distinguishes edge-count information from arrangement-dependent signal: weak labels retain only the former, whereas collective rotation averaging preserves structural correlations. The retained correlations and their limits clarify what Schur readouts can detect.

4.3 Operator symmetries

  • The weak label detects only the edge-count component; detecting the structural component requires an effect not invariant under all edge permutations.Edge averaging after collective rotation averaging reduces the Specht information to label probabilities.Source: §4.3 · p. 25, §4.3.1 · p. 25

4.3.1 Correlations retained after discarding multiplicity

  • Collective rotation averaging annihilates odd-degree diagonal Fourier components and preserves every nonzero even-degree component injectively, scaling squared Hilbert–Schmidt norms by (j + 1)^-1.Edge averaging then keeps only the mean coefficient at each degree, removing differences between edge arrangements.Source: §4.3 · p. 24, §4.3.1 · pp. 25, 27
  • For n ≥ 4 and 3 ≤ k < n, collective averaging preserves the different planted coefficients of adjacent and disjoint edge pairs, while edge averaging removes that variation.Thus the measured label and Specht state retain arrangement information that the weak label cannot detect.Source: §4.3.1 · p. 26
  • The diagonal signal has only two-row conjugation types, and vertex invariance further restricts which types can contribute.For the two-edge example, removing the trivial component leaves only type (M − 2, 2).Source: §4.3.1 · p. 26
  • A Specht-only effect can use only correlations surviving collective averaging, and the analysis does not provide an efficient implementation of that effect.Above the fixed-margin logarithmic threshold, a Specht-only effect achieves near-perfect discrimination.Source: §4.3.1 · p. 27

4.4 Level-set symmetries

The section uses clique-count level sets to construct a statistically powerful symmetry action, then examines what its labels reveal and whether smaller actions could be efficient. The full-group result is a statistical benchmark, not an efficient algorithm.

4.4 Level-set symmetries

  • The full clique-count-preserving group places almost the entire planted kernel in one isotypic component, motivating a search for smaller actions with accessible signals.The section establishes the full-group relation before considering which smaller actions could make the signal accessible.Source: §4.4 · p. 27

4.4.1 Clique-count levels and the planted rank ratio

  • Clique count is a sufficient statistic, and its level sets define a full permutation group that can exchange graphs with the same clique count.This group gives a statistical benchmark, but its definition does not provide an efficient implementation.Source: §4.4.1 · p. 28

4.4.2 An isotypic component of almost full rank

  • Whenever μ_k = o(1), this projector has rank (1 − o(1))N and occurs with probability 1 − o(1) under the null, but never under planting.If μ_k < 1, all other label outcomes favor planting.Source: §4.4.2 · p. 29

4.4.3 From the projector to an efficient distinguisher

  • A readout implemented on every graph would solve clique existence; the stated obstacles do not rule out an efficient distinguisher that succeeds on average.A uniform polynomial-size circuit family for the all-graph readout would imply NP ⊆ BQP.Source: §4.4.3 · p. 29

4.4.4 Which smaller actions retain an informative label?

  • For a subgroup H, isotypic-label probabilities are determined by graph stabilizers, but repeated irreducible types across levels can obscure the planted support.Vertex relabelings give the same label law for all asymmetric graphs, regardless of clique count; an efficient proposal also needs an efficient label measurement and decision rule.Source: §4.4.4 · p. 30

5 Conclusion

The conclusion reviews how quantum encodings and symmetry-adapted measurements preserve or lose planted-clique information, and identifies efficient readout as unresolved. The results are structural and information-theoretic rather than a resolution of the computational–statistical gap.

5 Conclusion

  • Weak Schur sampling has vanishing distinguishing advantage, while retaining the label and Specht register after discarding multiplicity preserves near-perfect distinguishability, even if the label is also discarded.Explicit retained-state formulas make their discrimination a concrete algorithmic question.Source: §5 · p. 31

5.1 Open directions

  • An efficient two-outcome measurement on the retained label and Specht register is an open target; it need only achieve a constant gap, not implement the optimal effect exactly.The retained-state formulas and even-degree components provide starting points for constructing such an effect.Source: §5.1 · p. 31
  • A useful subgroup action must have a constant distinguishing gap, an efficient label measurement, and an efficient decision rule; efficient generators alone are insufficient.The distinguisher need only succeed on the planted ensembles, not reproduce the full-group measurement on every graph.Source: §5.1 · p. 31
  • For t phase copies, any fixed measurement has acceptance probability of degree at most 2t in the edge signs, but connecting effect restrictions to circuit complexity remains a challenge.Polynomial circuit size alone does not imply low degree.Source: §5.1 · p. 32
  • The results do not settle whether the computational–statistical gap survives quantum computation; efficient detection from one classical graph in the conjectured hard regime remains open.A polynomial-time quantum algorithm with constant advantage at k = ⌊n^1/2−ε⌋ would establish a conditional quantum advantage under the classical planted-clique conjecture.Source: §5.1 · p. 32

5.2 Statement on AI usage.

  • The authors report using Claude 5.1 Fable and ChatGPT 5.6 Sol for exposition, proofs, argument checking, and editing, with author responsibility for verification.They also describe GPT-5.6 and ChatGPT-6 Astra assistance during development and writeup.Source: §5.2 · p. 32

A Supporting Calculations for Schur Measurements

The supporting calculations set out exact weak Schur outcome probabilities for fixed graphs and for the null and planted ensembles.

A Supporting Calculations for Schur Measurements

  • The section calculates exact weak Schur outcome probabilities, first for a fixed graph and then for the null and planted ensembles.The passages introduce the scope of the supporting calculations without giving the resulting formulas.Source: A Supporting Calculations for Schur… · p. 33
  • The fixed-graph calculation precedes the ensemble-level calculations.The text distinguishes a fixed graph from the null and planted ensemble cases.Source: A Supporting Calculations for Schur… · p. 33
  • The calculations concern weak Schur outcomes rather than a separate measurement procedure.The supplied passages identify the quantities calculated but do not state their values.Source: A Supporting Calculations for Schur… · p. 33

A.1 Exact block probabilities

This appendix gives exact block-probability calculations for weak Schur sampling, covering fixed graphs and the planted ensemble.

A.1 Exact block probabilities

  • For a graph with w edges, the weak Schur label has a conditional outcome law determined by its edge count.The appendix introduces the fixed-graph law; the supplied passages do not expose its formula values.Source: §A.1 · p. 33
  • Transitivity of edge permutations makes projector diagonal entries equal on each weight space, so the restricted projector rank determines the label probability.The probability is obtained by dividing that rank by the dimension of the weight space.Source: §A.1 · p. 33
  • For the planted ensemble, the appendix gives a closed form using Specht-block ranks obtained from successive Hamming-weight traces.The trace-generating polynomial is (1 + z + ··· + z^m)(1 + z)^s; subtracting traces at weights i and i−1 isolates the rank.Source: §A.1 · p. 33
Loading 2609.40310v1…