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.

AI Summary

The paper asks what information quantum encodings and symmetry-adapted measurements retain for planted-clique detection from one classical graph, particularly at $k=\lfloor n^{1/2-\varepsilon}\rfloor$, where efficient classical detection is conjectured hard. It separates statistical distinguishability from efficient measurement implementation. For a binary phase encoding on $O(\log n)$ qubits, constant-advantage detection requires $\Omega(n^{1+2\varepsilon}\ln^2 n)$ copies encoding the same graph, even with arbitrary joint measurements. The proof uses a Poissonized product-state comparison, a weighted trace-norm inequality, and bounds on overlaps of random clique locations. Separate measurements suffice with $O(n^2)$ copies, but their classical post-processing may be expensive. The bounds match at $\Theta(n^2)$ for $k=\lceil c\log_2 n\rceil$, with fixed $c>2$. Infinitely many copies identify the graph up to complementation; optimal detection then thresholds the combined clique count of both graphs. For computational-basis graph encodings, weak Schur sampling depends only on edge count and has distinguishing distance $O(k^4/n^2)$ below the square-root scale. Nevertheless, the Specht register retains trace distance $1-o(1)$ for $k\geq(2+\delta)\log_2 n$, even after discarding label and multiplicity. This follows from the planted state's small relative rank and a general bound for discarding a small register. One supplied coherent qsample also enables an $O(n^2)$-time detector above this logarithmic threshold, excluding preparation costs. No efficient detector from one classical graph is obtained: informative subgroup-isotypic measurements are proposed as an open direction, and the qsample separation assumes quantum planted-clique hardness.

Likely largely AI-generatedAI use disclosedIncremental
We then made extensive use of ChatGPT-6 Astra at Max or Ultra settings during the writeup, with author guidance throughout.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

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

arXiv:2509.01261•Journal of Physics A Mathematical and Theoretical•May 13, 2026•1 citation

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

Performance of Gaussian Boson Sampling on Planted Bipartite Clique Detection

Yu-Zhen Janice Chen, Laurent Massoulié, Don Towsley

We investigate whether Gaussian Boson Sampling (GBS) can provide a computational advantage for solving the planted biclique problem, which is a graph problem widely believed to be classically hard when the planted structure is small. Although GBS has been heuristically and experimentally observed to favor sampling dense subgraphs, its theoretical performance on this classically hard problem remains largely unexplored. We focus on a natural statistic derived from GBS output: the frequency with which a node appears in GBS samples, referred to as the node weight. We rigorously analyze whether this signal is strong enough to distinguish planted biclique nodes from background nodes. Our analysis characterizes the distribution of node weights under GBS and quantifies the bias introduced by the planted structure. The results reveal a sharp limitation: when the planted biclique size falls within the conjectured hard regime, the natural fluctuations in node weights dominate the bias signal, making detection unreliable using simple ranking strategies. These findings provide the first rigorous evidence that planted biclique detection may remain computationally hard even under GBS-based quantum computing, and they motivate further investigation into more advanced GBS-based algorithms or other quantum approaches for this problem.

arXiv:2510.12774•Oct 14, 2025•1 citation

Testing quantum Gaussianity with constant sample complexity

Mahtab Yaghubi Rad, Ricard Puig, Saksham Hassanandani +4 more

Efficiently testing whether a quantum state possesses a given structure is both a fundamental and a practical task in quantum information. Among the most important structured families are Gaussian states, which underpin quantum optics and many-body physics while defining paradigmatic regimes of efficient classical simulation. Despite the central role of Gaussian states, optimal tests of Gaussianity have remained unknown. Here we give optimal and robust algorithms for testing fermionic and bosonic Gaussian states, with sample complexity independent of system size, particle number, and energy. Remarkably, the protocols implement experimentally feasible measurements associated with known exact symmetry characterizations of Gaussianity, using Bell sampling on two copies for fermions and passive interferometry with photon counting on three copies for bosons. We further obtain tolerant testers requiring joint measurements on a larger, but still constant, number of copies. At the heart of our analysis is a unified approach---which we call the gradient-flow method---that applies across all structured families considered here and underlies our optimal testers: representation theory turns approximate satisfaction of the defining symmetry into quantitative control of the gradient of the rejection probability, allowing a continuous descent from the input state to the target family whose length bounds their distance.

quant-pharXiv:2609.40270•Oct 1, 2026•3 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.
The paper asks what information quantum encodings and symmetry-adapted measurements retain for planted-clique detection from one classical graph, particularly at k=⌊n1/2−ε⌋k=\lfloor n^{1/2-\varepsilon}\rfloork=⌊n1/2−ε⌋, where efficient classical detection is conjectured hard. It separates statistical distinguishability from efficient measurement implementation.
For a binary phase encoding on O(log⁡n)O(\log n)O(logn) qubits, constant-advantage detection requires Ω(n1+2εln⁡2n)\Omega(n^{1+2\varepsilon}\ln^2 n)Ω(n1+2εln2n) copies encoding the same graph, even with arbitrary joint measurements. The proof uses a Poissonized product-state comparison, a weighted trace-norm inequality, and bounds on overlaps of random clique locations. Separate measurements suffice with O(n2)O(n^2)O(n2) copies, but their classical post-processing may be expensive. The bounds match at Θ(n2)\Theta(n^2)Θ(n2) for k=⌈clog⁡2n⌉k=\lceil c\log_2 n\rceilk=⌈clog2​n⌉, with fixed c>2c>2c>2. Infinitely many copies identify the graph up to complementation; optimal detection then thresholds the combined clique count of both graphs.
For computational-basis graph encodings, weak Schur sampling depends only on edge count and has distinguishing distance O(k4/n2)O(k^4/n^2)O(k4/n2) below the square-root scale. Nevertheless, the Specht register retains trace distance 1−o(1)1-o(1)1−o(1) for k≥(2+δ)log⁡2nk\geq(2+\delta)\log_2 nk≥(2+δ)log2​n, even after discarding label and multiplicity. This follows from the planted state's small relative rank and a general bound for discarding a small register.
One supplied coherent qsample also enables an O(n2)O(n^2)O(n2)-time detector above this logarithmic threshold, excluding preparation costs. No efficient detector from one classical graph is obtained: informative subgroup-isotypic measurements are proposed as an open direction, and the qsample separation assumes 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.
We investigate whether Gaussian Boson Sampling (GBS) can provide a computational advantage for solving the planted biclique problem, which is a graph problem widely believed to be classically hard when the planted structure is small. Although GBS has been heuristically and experimentally observed to favor sampling dense subgraphs, its theoretical performance on this classically hard problem remains largely unexplored. We focus on a natural statistic derived from GBS output: the frequency with which a node appears in GBS samples, referred to as the node weight. We rigorously analyze whether this signal is strong enough to distinguish planted biclique nodes from background nodes. Our analysis characterizes the distribution of node weights under GBS and quantifies the bias introduced by the planted structure. The results reveal a sharp limitation: when the planted biclique size falls within the conjectured hard regime, the natural fluctuations in node weights dominate the bias signal, making detection unreliable using simple ranking strategies. These findings provide the first rigorous evidence that planted biclique detection may remain computationally hard even under GBS-based quantum computing, and they motivate further investigation into more advanced GBS-based algorithms or other quantum approaches for this problem.
Efficiently testing whether a quantum state possesses a given structure is both a fundamental and a practical task in quantum information. Among the most important structured families are Gaussian states, which underpin quantum optics and many-body physics while defining paradigmatic regimes of efficient classical simulation. Despite the central role of Gaussian states, optimal tests of Gaussianity have remained unknown. Here we give optimal and robust algorithms for testing fermionic and bosonic Gaussian states, with sample complexity independent of system size, particle number, and energy. Remarkably, the protocols implement experimentally feasible measurements associated with known exact symmetry characterizations of Gaussianity, using Bell sampling on two copies for fermions and passive interferometry with photon counting on three copies for bosons. We further obtain tolerant testers requiring joint measurements on a larger, but still constant, number of copies. At the heart of our analysis is a unified approach---which we call the gradient-flow method---that applies across all structured families considered here and underlies our optimal testers: representation theory turns approximate satisfaction of the defining symmetry into quantitative control of the gradient of the rejection probability, allowing a continuous descent from the input state to the target family whose length bounds their distance.