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
9 Pith papers cite this work, alongside 1 external citations. Polarity classification is still indexing.
9
Pith papers citing it
1
external citations · external index
citation-role summary
background 1
citation-polarity summary
roles
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 yield near-optimal extremal bounds and improve code sparsification support from polylog(n) to O(k log n / eps^2 * poly(log(k/eps), log log n)).
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.
Every abelian Cayley graph admits an optimal O(ε^{-2} log |G|)-generator weighted Cayley spectral sparsifier, proved via a character-symmetry volume bound on a sparsification polytope.
citing papers explorer
-
On Clifford hierarchy testing and near-extremizers of noncommutative uniformity norms
Provides characterization of near-extremizers for the fourth noncommutative Gowers uniformity norm, enabling an efficient tester for the third Clifford hierarchy level.
-
An algorithmic Polynomial Freiman-Ruzsa theorem
Polynomial-time algorithms for the Polynomial Freiman-Ruzsa theorem and equivalent formulations over F_2^n, based on an optimized quadratic Goldreich-Levin procedure.
-
Quantum Cut Sparsifiers
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.
-
Tomography of quantum states with bounded extent
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 and efficient code sparsification
Moonflowers yield near-optimal extremal bounds and improve code sparsification support from polylog(n) to O(k log n / eps^2 * poly(log(k/eps), log log n)).
-
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.
-
Optimal Sparsifiers for Abelian Cayley Graphs
Every abelian Cayley graph admits an optimal O(ε^{-2} log |G|)-generator weighted Cayley spectral sparsifier, proved via a character-symmetry volume bound on a sparsification polytope.