Provides characterization of near-extremizers for the fourth noncommutative Gowers uniformity norm, enabling an efficient tester for the third Clifford hierarchy level.
Title resolution pending
8 Pith papers cite this work. Polarity classification is still indexing.
8
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 8roles
background 1polarities
background 1representative citing papers
Polynomial-time algorithms for the Polynomial Freiman-Ruzsa theorem and equivalent formulations over F_2^n, based on an optimized quadratic Goldreich-Levin procedure.
Any n-qubit QC Hamiltonian sparsifies to Õ(n/ε²) terms preserving all state energies within 1±ε using invariant subspace decomposition and the Alon-Kozma operator inequality.
A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
Moonflowers are introduced as set families with per-set unique elements, yielding near-optimal extremal bounds that enable logarithmic code sparsification with a matching lower bound.
A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
Derives Õ(d β² A² / ε⁴) oracle complexity for AIS estimating normalizing constant Z to relative error ε and introduces reverse diffusion sampler for geometric paths with large action.
citing papers explorer
-
Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity
A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.
-
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
-
Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond
Derives Õ(d β² A² / ε⁴) oracle complexity for AIS estimating normalizing constant Z to relative error ε and introduces reverse diffusion sampler for geometric paths with large action.