We initiate the study of quantum agnostic learning of phase states with respect to a function class $C \subseteq {c:{0,1}^n\rightarrow {0,1}}$: given copies of an unknown $n$-qubit state $|\psi⟩$ which has fidelity $\textsf{opt}$ with a phase state $|\phi_c⟩=\frac{1}{\sqrt{2^n}}\sum_{x\in {0,1}^n}(-1)^{c(x)}|x⟩$ for some $c\in C$, output $|\phi⟩$ which has fidelity $|⟨\phi | \psi ⟩|^2 \geq \textsf{opt}-\varepsilon$. To this end, we give agnostic learning protocols for the following classes: 1. Size-$t$ decision trees which runs in time $\textsf{poly}(n,t,1/\varepsilon)$. This also implies $k$-juntas can be agnostically learned in time $\textsf{poly}(n,2^k,1/\varepsilon)$. 2. $s$-term DNF formulas in time $\textsf{poly}(n,(s/\varepsilon)^{\log \log (s/\varepsilon) \cdot \log(1/\varepsilon)})$. Our main technical contribution is a quantum agnostic boosting protocol which converts a “weak” agnostic learner, which outputs a parity state $|\phi⟩$ such that $|⟨\phi|\psi⟩|^2\geq \textsf{opt}/\textsf{poly}(n)$, into a “strong” learner which outputs a superposition of parity states $|\phi’⟩$ such that $|⟨\phi’|\psi⟩|^2\geq \textsf{opt} - \varepsilon$. Using quantum agnostic boosting, we give a $n^{O(\log(n/\varepsilon)\cdot \log \log n)}$-time algorithm for $\varepsilon$-learning $\textsf{poly}(n)$-sized depth-$3$ circuits (consisting of $\textsf{AND}$, $\textsf{OR}$, $\textsf{NOT}$ gates) in the uniform $\textsf{PAC}$ model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the $\textsf{PAC}$ model and our work answers this given quantum examples.

We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we give classical and quantum polynomial-time algorithms that, for $A \subseteq \mathbb{F}_2^n$ with doubling constant $K$, learn an explicit description of a subspace $V \subseteq \mathbb{F}_2^n$ of size $|V| \leq |A|$ such that $A$ can be covered by $K^C$ translates of $V$, for a universal constant $C>1$.

We consider the task of learning a structured stabilizer decomposition of an arbitrary n-qubit quantum state |ψ⟩: for every ε > 0, output a succinctly describable state |φ⟩ with stabilizer-rank poly(1/ε) such that |ψ⟩=|φ⟩+|φ′⟩ where |φ′⟩ has stabilizer fidelity at most ε. We firstly show the existence of such decompositions using the inverse theorem for the Gowers-3 norm of quantum states that was recently established by our prior work [AD, STOC’25].

We consider the problems of testing and learning an unknown $n$-qubit quantum Hamiltonian $H=Σ_x λ_x σ_x$ expressed in its Pauli basis, from queries to its evolution operator $e^{-iHt}$ under the normalized Frobenius norm. To this end, we prove the following results (with and without quantum memory) for Hamiltonians whose Pauli spectrum involves only $k$-local terms or has sparsity at most $s$: (1) Local Hamiltonians: We give a tolerant testing protocol to decide if a Hamiltonian is $ε_1$-close to $k$-local or $ε_2$-far from $k$-local, with $O(1/(ε_2-ε_1)^4)$ queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir [BCO'24]. For learning a $k$-local Hamiltonian up to error $ε$, we give a protocol with query complexity and total time evolution $exp(O(k^2+k\mathrm{log} (1/ε)))$. Our algorithm leverages the non-commutative Bohnenblust-Hille inequality in order to get a complexity independent of $n$. (2) Sparse Hamiltonians: We give a protocol for testing whether a Hamiltonian is $ε_1$-close to being $s$-sparse or $ε_2$-far from being $s$-sparse, with $O(s^6/(ε{_2}^2-ε{_1}^2)^6)$ queries. For learning up to error $ε$, we show that $O(s^4/ε^8)$ queries suffices. (3) Learning without quantum memory: The learning results stated above have no dependence on the system size $n$, but require $n$-qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; increasing the query complexity by a (log$n$)-factor in the local case and an $n$-factor in the sparse case. (4) Testing without quantum memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test $s$-sparse Hamiltonians using $Õ(s^{14}/(ε{_2}^2-ε{_1}^2)^{18})$ query complexity. A key ingredient is showing that $s$-sparse Pauli channels can be tested in a tolerant fashion as being $ε_1$-close to being $s$-sparse or $ε_2$-far under the diamond norm, using $Õ(s^2/(ε_2-ε_1)^6)$ queries via Pauli hashing. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge about the support of the Hamiltonian terms.

We consider the problem of learning low-degree quantum objects up to $\varepsilon$-error in $\ell_2$-distance. We show the following results: $(i)$ unknown $n$-qubit degree-$d$ (in the Pauli basis) quantum channels and unitaries can be learned using $O(1/\varepsilon^d)$ queries (independent of $n$), $(ii)$ polynomials $p:\{-1,1\}^n\rightarrow [-1,1]$ arising from $d$-query quantum algorithms can be classically learned from $O((1/\varepsilon)^d\cdot \log n)$ many random examples $(x,p(x))$ (which implies learnability even for $d=O(\log n)$), and $(iii)$ degree-$d$ polynomials $p:\{-1,1\}^n\to [-1,1]$ can be learned through $O(1/\varepsilon^d)$ queries to a quantum unitary $U_p$ that block-encodes $p$. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded~polynomials.

The usual setting for learning the structure and parameters of a graphical model assumes the availability of independent samples produced from the corresponding multivariate probability distribution. However, for many models the mixing time of the respective Markov chain can be very large and i.i.d. samples may not be obtained. We study the problem of reconstructing binary graphical models from correlated samples produced by a dynamical process, which is natural in many applications. We analyze the sample complexity of two estimators that are based on the interaction screening objective and the conditional likelihood loss. We observe that for samples coming from a dynamical process far from equilibrium, the sample complexity reduces exponentially compared to a dynamical process that mixes quickly.

PySPH is an open-source, Python-based, framework for particle methods in general and Smoothed Particle Hydrodynamics (SPH) in particular. PySPH allows a user to define a complete SPH simulation using pure Python. High-performance code is generated from this high-level Python code and executed on either multiple cores, or on GPUs, seamlessly. It also supports distributed execution using MPI. PySPH supports a wide variety of SPH schemes and formulations. These include, incompressible and compressible fluid flow, elastic dynamics, rigid body dynamics, shallow water equations, and other problems. PySPH supports a variety of boundary conditions including mirror, periodic, solid wall, and inlet/outlet boundary conditions. The package is written to facilitate reuse and reproducibility. This article discusses the overall design of PySPH and demonstrates many of its features. Several example results are shown to demonstrate the range of features that PySPH provides.