A reduction framework from sample complexity yields matching time lower bounds for purity estimation, high-order functionals, productness testing, and related quantum protocols.
hub
Semidefinite Progr ams on Sparse Random Graphs and /T_heir Application to Community Detection
16 Pith papers cite this work, alongside 409 external citations. Polarity classification is still indexing.
16
Pith papers citing it
409
external citations · external index
hub tools
citation-role summary
baseline 1
method 1
citation-polarity summary
representative citing papers
Coherent quantum inference achieves O(1/ε) sample complexity for d-dimensional quantum purity amplification, exponentially better than the Ω(d/ε) required by any incoherent measurement-mediated protocol.
Solves quantum purity amplification for arbitrary n, m, eigenstates, and dimension d, with asymptotic input scaling O(m/(ε D_min²)) independent of d and non-asymptotic bounds from generalized Young diagrams.
Two relational structures are indistinguishable by k-RCR if and only if they receive identical homomorphism counts from every structure of generalised hypertreewidth ≤ k.
Sample complexity for fidelity estimation to a rank-r reference state is O(r²/ε²) with lower bound Ω(r/ε²); O(r²/ε⁴) when unknown state also has rank ≤r.
Random dimension reduction replaces full dimension with max rank in sample complexity for symmetric quantum state properties and connects to but differs from random purification.
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
Generalizes homomorphism indistinguishability equivalences induced by orthogonal easy quantum groups, including a classification of (0,0)-intertwiners for graph-theoretic versions.
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
Adding loop composition to branching quantum walk models produces a variable-time quantum search algorithm whose complexity matches the best known results.
AC³ isomorphism tests for coprime Abelian extensions and central-radical groups with elementary Abelian radical, plus an AC circuit bound for arbitrary central-radical groups.
A classical agent extracts more work from quantum temporal correlations via adaptive strategies bounded by the new Time-Ordered Free Energy, while reinforcement learning achieves polylogarithmic dissipation when learning unknown states.
1D translation-invariant Gibbs states at positive temperature exhibit superexponential decay of Belavkin-Staszewski conditional mutual information, enabling efficient learning from local measurements and tensor network approximations.
Sparse Erdős-Rényi graphs of average degree d have vector chromatic number (1/2)√d + o_d(1).
The paper determines the automorphism groups of Berman codes and associated abelian codes for n ≥ 5 and provides partial results for n = 3.
Presents analogous arguments supporting the Cobham-Edmonds thesis that feasible computation explicates to P.
citing papers explorer
-
Quantum Time Lower Bounds by Permutation Invariance
A reduction framework from sample complexity yields matching time lower bounds for purity estimation, high-order functionals, productness testing, and related quantum protocols.
-
An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
Coherent quantum inference achieves O(1/ε) sample complexity for d-dimensional quantum purity amplification, exponentially better than the Ω(d/ε) required by any incoherent measurement-mediated protocol.
-
Quantum Purity Amplification for Arbitrary Eigenstates and Multiple Outputs
Solves quantum purity amplification for arbitrary n, m, eigenstates, and dimension d, with asymptotic input scaling O(m/(ε D_min²)) independent of d and non-asymptotic bounds from generalized Young diagrams.
-
Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler--Leman and Hypertree Width
Two relational structures are indistinguishable by k-RCR if and only if they receive identical homomorphism counts from every structure of generalised hypertreewidth ≤ k.
-
Estimating Fidelity to a Reference Quantum State
Sample complexity for fidelity estimation to a rank-r reference state is O(r²/ε²) with lower bound Ω(r/ε²); O(r²/ε⁴) when unknown state also has rank ≤r.
-
Random dimension reduction and learning symmetric properties of quantum states
Random dimension reduction replaces full dimension with max rank in sample complexity for symmetric quantum state properties and connects to but differs from random purification.
-
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
-
Homomorphism Indistinguishability Relations induced by Quantum Groups
Generalizes homomorphism indistinguishability equivalences induced by orthogonal easy quantum groups, including a classification of (0,0)-intertwiners for graph-theoretic versions.
-
Hardness and Approximation for Coloring Digraphs
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
-
Loop Composition in Quantum Algorithms
Adding loop composition to branching quantum walk models produces a variable-time quantum search algorithm whose complexity matches the best known results.
-
Parallel Algorithms for Group Isomorphism via Code Equivalence
AC³ isomorphism tests for coprime Abelian extensions and central-radical groups with elementary Abelian radical, plus an AC circuit bound for arbitrary central-radical groups.
-
A Demon that remembers: An agential approach towards quantum thermodynamics of temporal correlations
A classical agent extracts more work from quantum temporal correlations via adaptive strategies bounded by the new Time-Ordered Free Energy, while reinforcement learning achieves polylogarithmic dissipation when learning unknown states.
-
Conditional Independence of 1D Gibbs States with Applications to Efficient Learning
1D translation-invariant Gibbs states at positive temperature exhibit superexponential decay of Belavkin-Staszewski conditional mutual information, enabling efficient learning from local measurements and tensor network approximations.
-
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
Sparse Erdős-Rényi graphs of average degree d have vector chromatic number (1/2)√d + o_d(1).
-
On the Automorphism Groups of Berman Codes and associated Abelian Codes
The paper determines the automorphism groups of Berman codes and associated abelian codes for n ≥ 5 and provides partial results for n = 3.
-
Feasibilism, Explication, and the Cobham-Edmonds Thesis
Presents analogous arguments supporting the Cobham-Edmonds thesis that feasible computation explicates to P.