Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40310

Planted Cliques and Quantum Symmetry-Adapted Measurements

Vojtech Havlicek, Jordan Docter, Subhash Khot

quant-phcs.CCSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations• Revised Oct 5, 2026 (v3)
v1 · Sep 30, 2026v2 · Oct 1, 2026v3 · Oct 5, 2026
arXivHTMLPDF

Abstract

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 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.

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

Related papers

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Amin Shiraz Gilani, Xingyu Zhou

Subgraph detection asks whether an $n$-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph $H$. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of $H$ is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed $r\ge 4$, detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$, the exponents $λ_r$ increase strictly with $r$, and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$. More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$. These bounds approach quadratic as $c$ grows: for sufficiently large $c$, detection requires $n^{2-O(\sqrt{\log\log c/c})-o(1)}$ queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{r})$. Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.

quant-pharXiv:2609.40263•Oct 1, 2026•0 citations

Adaptive Local Measurements For Quantum Learning Can Exponentially Outperform Nonadaptive Global Measurements

Alireza Goldar, Zhen Qin, Zhihui Zhu +2 more

Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance? In many quantum settings, adaptivity helps at most polynomially; known exponential advantages require coherent measurements across copies or restricted measurements. We show an exponential advantage measuring one copy at a time, with no quantum memory kept between state copies, even when the nonadaptive learner may perform arbitrary global measurements on each copy. We construct explicit families of multi-qubit states in which a scalar parameter is encoded in one of exponentially many candidate observables, with an auxiliary marker indicating which one. An adaptive protocol identifies the relevant observable and then measures it using only single-qubit measurements and one round of adaptation. At fixed accuracy, it needs logarithmically many copies as the qubit count grows, whereas every nonadaptive protocol needs exponentially many. The same mechanism yields an exponential gap in local asymptotic minimax mean squared error constants, tight up to the exponential base. The states are separable and classical in label-dependent product bases; no entanglement or other nonclassical correlations are required. The gap comes from measurement incompatibility: the candidate observables cannot be measured jointly, so a fixed measurement must divide its information budget among them, while adaptivity selects the informative one. Accordingly, the separation disappears when the candidate observables commute, and cannot occur with fully observed classical samples. Measurement incompatibility thus emerges as a resource for quantum learning, distinct from entanglement and quantum memory, that classical feedback alone can exploit.

quant-pharXiv:2610.38922•Oct 30, 2026•0 citations

Efficient quantum detection of maximum clique via hybrid heuristic and global information encoding

Wenmin Han, Shiqi Zheng, Peian Chen +1 more

Abstract The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an enhanced quantum solution method that introduces a pre-detection phase based on a hybrid heuristic algorithm and a vertex pruning strategy, encoding the prior constraints on clique size into quantum registers as global information. It encodes the prior constraints on clique size into quantum registers as global information. In contrast, state-of-the-art Grover-based methods for n-vertex graphs require O ( n 2 n ) iterations and O ( n ) measurements. By leveraging a global information encoding mechanism, the proposed method compresses the number of iterations to O ( 2 n ) and only needs a constant number of measurements to identify all maximum cliques. We validate algorithmic correctness through simulations on IBM’s Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.

Journal of Physics A Mathematical and Theoretical•May 13, 2026•0 citations

Symmetry Discovery in Quantum Learning: Observable-Level and Task-Level Inference from Finite Measurements

Zeyu Chen

Symmetry reduces the capacity of a quantum learning model, but the imposed group must match both the measured information and the label transformation. We establish a finite-measurement theory for inferring this group from candidate transformations. The central structural result identifies observable-invisible transformations with the stabilizer of a projected state whenever the probe span is invariant. It turns recovered generators into a valid subgroup and identifies the continuous invisible space with its Lie algebra. For finite dictionaries, an unbiased shadow statistic distinguishes zero from positive squared expectation discrepancies with an inverse-gap measurement rate, improving the inverse-square-gap rate of uniform discrepancy estimation. A commuting qubit lower bound proves the gap dependence optimal at fixed snapshot scale, and simultaneous intervals support data-dependent tolerances. Task validation then tests either the joint distribution through a characteristic kernel or its encoded mean through a classical--quantum discrepancy. An exact group-average identity relates the latter to joint-state asymmetry and specifies its conversion to binary task breaking mass. Projection bias quantifies the cost of excessive symmetry, while an $\ell_1$ readout bound quantifies the capacity gained by relaxing it. At an invariant pure-state backbone, retained and nontrivial breaking sectors are Fisher-orthogonal. Ising-chain calculations connect finite-shot recovery, label-dependent symmetry, and physical sector drift. These results determine which symmetry the measurements support and provide the statistical and geometric basis for a subsequent release decision.

quant-pharXiv:2610.00157•Sep 14, 2026•0 citations

Weak Schur sampling with logarithmic quantum memory

Enrique Cervero-Martí­n, Laura Mančinska

The quantum Schur transform maps the computational basis of a system of $n$ qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces of the representations of the unitary and the symmetric groups acting on the state space of $n$ $d$-level systems. We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group. There are two major advantages of our algorithm for weak Schur sampling when compared to existing approaches which proceed via quantum Schur transform algorithm or Generalized Phase Estimation algorithm. First, our algorihtm is suitable for streaming applications and second it is exponentially more efficient in its memory usage. We show that an instance of our weak Schur sampling algorithm on $n$ qubits to accuracy $ε$ requires only $O(\log_2n)$ qubits of memory and $O(n^3\log_2(\frac{n}ε))$ gates from the Clifford+T set. Further, we show that our weak Schur sampling algorithm on $n$ qudits decomposes into $O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}ε\big)\big)$ gates from an arbitrary fault-tolerant qudit universal set, for $p\approx 4$, and requires a memory of $O(\log_dn)$ qudits to implement.

arXiv:2309.11947•Sep 21, 2023•0 citations

Classical Sufficiency in Quantum Statistical Experiments

Samriddha Lahiry

A quantum measurement transforms a quantum statistical experiment into a classical one, but different measurements generally yield experiments with different statistical information. We introduce quantum-to-classical sufficiency: relative to a prescribed measurement class, a measurement is sufficient if its induced classical experiment Blackwell-dominates those from every other measurement in the class. This separates two components of quantum inference: reducing the measurement class through symmetry or decision-theoretic arguments, and identifying a canonical measurement in the reduced class by an experiment-level sufficiency condition. We establish a factorization criterion where the parameter enters the group-averaged experiment only through weights of an orthogonal block decomposition. The block-label measurement is then sufficient relative to all invariant measurements. For tensor-product models under unitary conjugation, this identifies weak Schur sampling as the sufficient measurement for spectral inference. Combined with risk-preserving symmetrization, it reduces invariant Bayes and minimax problems over all measurements exactly to classical decision problems based on Young diagrams. We derive sharp first-order asymptotic Bayes and minimax risks for smooth spectral functionals. We establish an analogous reduction for a noncompact group action in a continuous-variable setting. We consider displaced thermal states and functionals of the thermal parameter with an unknown displacement. Within displacement-invariant measurements, total residual photon number measurement emerges as the sufficient measurement. Combined with Hunt-Stein reduction, this yields exact finite-sample reductions of Bayes-minimax and minimax problems over all measurements to classical decision problems based on the total residual photon count, which follows a negative binomial distribution.

math.STCross-listedarXiv:2609.29348•Sep 25, 2026•0 citations
We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For k=⌊n1/2−ε⌋k=\lfloor n^{1/2-\varepsilon}\rfloork=⌊n1/2−ε⌋, with fixed 0<ε<1/20<\varepsilon<1/20<ε<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 Ω(n1+2εln⁡2n)Ω(n^{1+2\varepsilon}\ln^2 n)Ω(n1+2εln2n) 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 kkk-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.
Subgraph detection asks whether an nnn-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph HHH. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of HHH is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed r≥4r\ge 4r≥4, detecting the clique KrK_rKr​ requires nλr−o(1)n^{λ_r-o(1)}nλr​−o(1) queries, where λ4=19/18λ_4=19/18λ4​=19/18, the exponents λrλ_rλr​ increase strictly with rrr, and λr≥2−42/r+O(1/r)λ_r\ge 2-4\sqrt{2/r}+O(1/r)λr​≥2−42/r​+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph HHH with chromatic number c≥4c\ge 4c≥4. These bounds approach quadratic as ccc grows: for sufficiently large ccc, detection requires n2−O(log⁡log⁡c/c)−o(1)n^{2-O(\sqrt{\log\log c/c})-o(1)}n2−O(loglogc/c​)−o(1) queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph Kr,rK_{r,r}Kr,r​ requires nβr−o(1)n^{β_r-o(1)}nβr​−o(1) queries, where β10=181/180β_{10}=181/180β10​=181/180 and βr≥2−O(1/r)β_r\ge 2-O(1/\sqrt{r})βr​≥2−O(1/r​). Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.
Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance? In many quantum settings, adaptivity helps at most polynomially; known exponential advantages require coherent measurements across copies or restricted measurements. We show an exponential advantage measuring one copy at a time, with no quantum memory kept between state copies, even when the nonadaptive learner may perform arbitrary global measurements on each copy. We construct explicit families of multi-qubit states in which a scalar parameter is encoded in one of exponentially many candidate observables, with an auxiliary marker indicating which one. An adaptive protocol identifies the relevant observable and then measures it using only single-qubit measurements and one round of adaptation. At fixed accuracy, it needs logarithmically many copies as the qubit count grows, whereas every nonadaptive protocol needs exponentially many. The same mechanism yields an exponential gap in local asymptotic minimax mean squared error constants, tight up to the exponential base. The states are separable and classical in label-dependent product bases; no entanglement or other nonclassical correlations are required. The gap comes from measurement incompatibility: the candidate observables cannot be measured jointly, so a fixed measurement must divide its information budget among them, while adaptivity selects the informative one. Accordingly, the separation disappears when the candidate observables commute, and cannot occur with fully observed classical samples. Measurement incompatibility thus emerges as a resource for quantum learning, distinct from entanglement and quantum memory, that classical feedback alone can exploit.
Abstract The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an enhanced quantum solution method that introduces a pre-detection phase based on a hybrid heuristic algorithm and a vertex pruning strategy, encoding the prior constraints on clique size into quantum registers as global information. It encodes the prior constraints on clique size into quantum registers as global information. In contrast, state-of-the-art Grover-based methods for n-vertex graphs require O ( n 2 n ) iterations and O ( n ) measurements. By leveraging a global information encoding mechanism, the proposed method compresses the number of iterations to O ( 2 n ) and only needs a constant number of measurements to identify all maximum cliques. We validate algorithmic correctness through simulations on IBM’s Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
Symmetry reduces the capacity of a quantum learning model, but the imposed group must match both the measured information and the label transformation. We establish a finite-measurement theory for inferring this group from candidate transformations. The central structural result identifies observable-invisible transformations with the stabilizer of a projected state whenever the probe span is invariant. It turns recovered generators into a valid subgroup and identifies the continuous invisible space with its Lie algebra. For finite dictionaries, an unbiased shadow statistic distinguishes zero from positive squared expectation discrepancies with an inverse-gap measurement rate, improving the inverse-square-gap rate of uniform discrepancy estimation. A commuting qubit lower bound proves the gap dependence optimal at fixed snapshot scale, and simultaneous intervals support data-dependent tolerances. Task validation then tests either the joint distribution through a characteristic kernel or its encoded mean through a classical--quantum discrepancy. An exact group-average identity relates the latter to joint-state asymmetry and specifies its conversion to binary task breaking mass. Projection bias quantifies the cost of excessive symmetry, while an ℓ1\ell_1ℓ1​ readout bound quantifies the capacity gained by relaxing it. At an invariant pure-state backbone, retained and nontrivial breaking sectors are Fisher-orthogonal. Ising-chain calculations connect finite-shot recovery, label-dependent symmetry, and physical sector drift. These results determine which symmetry the measurements support and provide the statistical and geometric basis for a subsequent release decision.
The quantum Schur transform maps the computational basis of a system of nnn qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces of the representations of the unitary and the symmetric groups acting on the state space of nnn ddd-level systems. We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group. There are two major advantages of our algorithm for weak Schur sampling when compared to existing approaches which proceed via quantum Schur transform algorithm or Generalized Phase Estimation algorithm. First, our algorihtm is suitable for streaming applications and second it is exponentially more efficient in its memory usage. We show that an instance of our weak Schur sampling algorithm on nnn qubits to accuracy εεε requires only O(log⁡2n)O(\log_2n)O(log2​n) qubits of memory and O(n3log⁡2(nε))O(n^3\log_2(\frac{n}ε))O(n3log2​(εn​)) gates from the Clifford+T set. Further, we show that our weak Schur sampling algorithm on nnn qudits decomposes into O(dn2dlog⁡2p(n2dε))O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}ε\big)\big)O(dn2dlog2p​(εn2d​)) gates from an arbitrary fault-tolerant qudit universal set, for p≈4p\approx 4p≈4, and requires a memory of O(log⁡dn)O(\log_dn)O(logd​n) qudits to implement.
A quantum measurement transforms a quantum statistical experiment into a classical one, but different measurements generally yield experiments with different statistical information. We introduce quantum-to-classical sufficiency: relative to a prescribed measurement class, a measurement is sufficient if its induced classical experiment Blackwell-dominates those from every other measurement in the class. This separates two components of quantum inference: reducing the measurement class through symmetry or decision-theoretic arguments, and identifying a canonical measurement in the reduced class by an experiment-level sufficiency condition. We establish a factorization criterion where the parameter enters the group-averaged experiment only through weights of an orthogonal block decomposition. The block-label measurement is then sufficient relative to all invariant measurements. For tensor-product models under unitary conjugation, this identifies weak Schur sampling as the sufficient measurement for spectral inference. Combined with risk-preserving symmetrization, it reduces invariant Bayes and minimax problems over all measurements exactly to classical decision problems based on Young diagrams. We derive sharp first-order asymptotic Bayes and minimax risks for smooth spectral functionals. We establish an analogous reduction for a noncompact group action in a continuous-variable setting. We consider displaced thermal states and functionals of the thermal parameter with an unknown displacement. Within displacement-invariant measurements, total residual photon number measurement emerges as the sufficient measurement. Combined with Hunt-Stein reduction, this yields exact finite-sample reductions of Bayes-minimax and minimax problems over all measurements to classical decision problems based on the total residual photon count, which follows a negative binomial distribution.