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.
Semidefinite Progr ams on Sparse Random Graphs and /T_heir Application to Community Detection
10 Pith papers cite this work. Polarity classification is still indexing.
10
Pith papers citing it
citation-role summary
baseline 1
method 1
citation-polarity summary
representative citing papers
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.
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).
citing papers explorer
-
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.
-
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).