Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.09912

Learning Clifford-structured quantum unitaries and Hamiltonians

Arkopal Dutt, Dale Jacobs, John Jeang, Saeed Mehraban, Vladimir Podolskii

quant-phcs.CCSubmitted Aug 10, 2026• Announced Aug 11, 2026• 0 citations
arXivHTMLPDF

Abstract

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.

Related papers

Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance

Zahra Honjani, Mohsen Heidari

We study the problem of learning nearly $(s,ε)$-sparse unitaries, meaning that the Pauli spectrum is concentrated on at most $s$ components with at most $ε$ residual mass in Pauli $\ell_1$-norm. This class generalizes well-studied families, including sparse unitaries, quantum $k$-juntas, $2^k$-Pauli dimensional channels, and compositions of depth $O(\log\log n)$ circuits with near-Clifford circuits. Given query access to an unknown nearly sparse unitary $U$, our goal is to efficiently (both in time and query complexity) construct a quantum channel that is close in diamond distance to $U$. We design a learning algorithm achieving this guarantee using $\tilde{O}(s^6/ε^4)$ forward queries to $U$, and running time polynomial in relevant parameters. A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary $U$, estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold $θ$, extending existing sparse recovery techniques to general unitaries. We also study the broader class of unitaries with bounded Pauli $\ell_1$-norm. For that class, we prove an exponential query lower bound $Ω(2^{n/2})$. We introduce a more relaxed accuracy metric which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli $\ell_1$-norm uniformly bounded by $L_1$ are learnable with $\tilde{O}(L_1^8/ε^{16})$.

quant-pharXiv:2604.00203•Apr 2, 2026•0 citations

Testing and learning structured quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

We consider the problems of testing and learning an unknown $n$-qubit Hamiltonian $H$ from queries to its evolution operator $e^{-iHt}$ under the normalized Frobenius norm. We prove: 1. Local Hamiltonians: We give a tolerant testing protocol to decide if $H$ is $ε_1$-close to $k$-local or $ε_2$-far from $k$-local, with $O(1/(ε_2-ε_1)^{4})$ queries, solving open questions posed in a recent work by Bluhm et al. For learning a $k$-local $H$ up to error $ε$, we give a protocol with query complexity $\exp(O(k^2+k\log(1/ε)))$ independent of $n$, by leveraging the non-commutative Bohnenblust-Hille inequality. 2. Sparse Hamiltonians: We give a protocol to test if $H$ is $ε_1$-close to being $s$-sparse (in the Pauli basis) 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 suffice. 3. Learning without memory: The learning results stated above have no dependence on $n$, but require $n$-qubit quantum memory. We give subroutines that allow us to learn without 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 memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test $s$-sparse Hamiltonians with $O(s^{14}/(ε_2^2-ε_1^2)^{18})$ queries. A key ingredient is showing that $s$-sparse Pauli channels can be tolerantly tested under the diamond norm with $O(s^2/(ε_2-ε_1)^6)$ queries. Along the way, we prove new structural theorems for local and sparse Hamiltonians. We complement our learning results with polynomially weaker lower bounds. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms in the support of the Pauli spectrum.

arXiv:2411.00082•Oct 31, 2024•0 citations

Testing and Learning Structured Quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

We consider the problems of testing and learning an n -qubit Hamiltonian \(H=\sum _x \lambda _x \sigma _x\) expressed in its Pauli basis, from queries to its evolution operator \(U=e^{-iHt}\) . To this end, we prove the following results. Testing : We give a tolerant testing protocol to decide if a Hamiltonian is \(\varepsilon _1\) -close to k -local or \(\varepsilon _2\) -far from k -local in the \(\ell _2\) norm of the coefficients, with \(O(1/(\varepsilon _2-\varepsilon _1)^{4})\) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir (Bluhm, A., Caro, M.C., Oufkir, A.). We give a protocol for testing whether a Hamiltonian is \(\varepsilon _1\) -close to being s -sparse or \(\varepsilon _2\) -far from being s -sparse in the \(\ell _2\) norm of the coefficients, with \(O(s^{6}/(\varepsilon _2^2-\varepsilon _1^2)^{6})\) queries. Learning : We give a protocol to \(\varepsilon \) -learn unstructured Hamiltonian in the \(\ell _\infty \) norm of the coefficients with \(O(1/\varepsilon ^4)\) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k -local Hamiltonians in \(\ell _2\) norm of the coefficients that only uses \(O(\exp (k^2+k\log (1/\varepsilon )))\) queries. For Hamiltonians that are s -sparse in the Pauli basis, we can learn them in the \(\ell _2\) norm with \(O(s^2/\varepsilon ^4)\) queries. 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; squaring the query complexity and paying a \((\log n)\) -factor in the local case and an n -factor in the sparse case. Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians in the \(\ell _2\) norm using \(\tilde{O}(s^{14}/(\varepsilon _2^2-\varepsilon _1^2)^{18})\) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being \(\varepsilon _1\) -close to being s -sparse or \(\varepsilon _2\) -far under the diamond norm, using \(\tilde{O}(s^2/(\varepsilon _2-\varepsilon _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 of the support of the Hamiltonian.

Communications in Mathematical Physics•Dec 8, 2025•0 citations

An efficient Pauli decomposition algorithm for structured matrices

Daniel J. Spencer, Kishor Bharti, Alexey V. Gorshkov

Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only $k = \mathsf{poly}(n)$ Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in $n$. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least $1 - δ$, for any $δ$. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in $n$, $k$, and $\log(1/δ)$. These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.

quant-pharXiv:2606.31952•Jul 1, 2026•0 citations

Process tomography for Clifford unitaries

Timothy Skaras, Paul Ginsparg

We present an algorithm for performing quantum process tomography on an unknown $n$-qubit unitary $C$ from the Clifford group. Our algorithm uses Bell basis measurements to deterministically learn $C$ with $4n + 3$ queries, which is the asymptotically optimal query complexity. In contrast to previous algorithms that required access to $C^\dagger$ to achieve optimal query complexity, our algorithm achieves the same performance without querying $C^\dagger$. Additionally, we show the algorithm is robust to perturbations and can efficiently learn the closest Clifford to an unknown non-Clifford unitary $U$ using query overhead that is logarithmic in the number of qubits.

arXiv:2505.08069•Physical Review A•Dec 2, 2025•0 citations

Testing and Learning Structured Quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

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 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.

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•3 citations
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning nnn-qubit quantum unitaries UUU and Hamiltonians HHH, given query access to UUU or the unitary evolution of HHH, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form U=∑iαiCiU = \sum_i α_i C_iU=∑i​αi​Ci​ over Cliffords CiC_iCi​ with bounded Clifford extent ∑i∣αi∣\sum_i |α_i|∑i​∣αi​∣. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary UUU with optimal Clifford fidelity opt\textsf{opt}opt, outputs a Clifford unitary witnessing fidelity ≥opt−ε\geq \textsf{opt} - \varepsilon≥opt−ε for some error ε>0\varepsilon > 0ε>0, in time poly(n,(1/ε)log⁡(1/ε))\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})poly(n,(1/ε)log(1/ε)). We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity Ω(2n)Ω(2^n)Ω(2n)) in the Pauli basis but are Clifford structured.
We study the problem of learning nearly (s,ε)(s,ε)(s,ε)-sparse unitaries, meaning that the Pauli spectrum is concentrated on at most sss components with at most εεε residual mass in Pauli ℓ1\ell_1ℓ1​-norm. This class generalizes well-studied families, including sparse unitaries, quantum kkk-juntas, 2k2^k2k-Pauli dimensional channels, and compositions of depth O(log⁡log⁡n)O(\log\log n)O(loglogn) circuits with near-Clifford circuits. Given query access to an unknown nearly sparse unitary UUU, our goal is to efficiently (both in time and query complexity) construct a quantum channel that is close in diamond distance to UUU. We design a learning algorithm achieving this guarantee using O~(s6/ε4)\tilde{O}(s^6/ε^4)O~(s6/ε4) forward queries to UUU, and running time polynomial in relevant parameters. A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary UUU, estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold θθθ, extending existing sparse recovery techniques to general unitaries. We also study the broader class of unitaries with bounded Pauli ℓ1\ell_1ℓ1​-norm. For that class, we prove an exponential query lower bound Ω(2n/2)Ω(2^{n/2})Ω(2n/2). We introduce a more relaxed accuracy metric which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli ℓ1\ell_1ℓ1​-norm uniformly bounded by L1L_1L1​ are learnable with O~(L18/ε16)\tilde{O}(L_1^8/ε^{16})O~(L18​/ε16).
We consider the problems of testing and learning an unknown nnn-qubit Hamiltonian HHH from queries to its evolution operator e−iHte^{-iHt}e−iHt under the normalized Frobenius norm. We prove: 1. Local Hamiltonians: We give a tolerant testing protocol to decide if HHH is ε1ε_1ε1​-close to kkk-local or ε2ε_2ε2​-far from kkk-local, with O(1/(ε2−ε1)4)O(1/(ε_2-ε_1)^{4})O(1/(ε2​−ε1​)4) queries, solving open questions posed in a recent work by Bluhm et al. For learning a kkk-local HHH up to error εεε, we give a protocol with query complexity exp⁡(O(k2+klog⁡(1/ε)))\exp(O(k^2+k\log(1/ε)))exp(O(k2+klog(1/ε))) independent of nnn, by leveraging the non-commutative Bohnenblust-Hille inequality. 2. Sparse Hamiltonians: We give a protocol to test if HHH is ε1ε_1ε1​-close to being sss-sparse (in the Pauli basis) or ε2ε_2ε2​-far from being sss-sparse, with O(s6/(ε22−ε12)6)O(s^{6}/(ε_2^2-ε_1^2)^{6})O(s6/(ε22​−ε12​)6) queries. For learning up to error εεε, we show that O(s4/ε8)O(s^{4}/ε^{8})O(s4/ε8) queries suffice. 3. Learning without memory: The learning results stated above have no dependence on nnn, but require nnn-qubit quantum memory. We give subroutines that allow us to learn without memory; increasing the query complexity by a (log⁡n)(\log n)(logn)-factor in the local case and an nnn-factor in the sparse case. 4. Testing without memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test sss-sparse Hamiltonians with O(s14/(ε22−ε12)18)O(s^{14}/(ε_2^2-ε_1^2)^{18})O(s14/(ε22​−ε12​)18) queries. A key ingredient is showing that sss-sparse Pauli channels can be tolerantly tested under the diamond norm with O(s2/(ε2−ε1)6)O(s^2/(ε_2-ε_1)^6)O(s2/(ε2​−ε1​)6) queries. Along the way, we prove new structural theorems for local and sparse Hamiltonians. We complement our learning results with polynomially weaker lower bounds. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms in the support of the Pauli spectrum.
We consider the problems of testing and learning an n -qubit Hamiltonian H=∑xλxσxH=\sum _x \lambda _x \sigma _xH=∑x​λx​σx​ expressed in its Pauli basis, from queries to its evolution operator U=e−iHtU=e^{-iHt}U=e−iHt . To this end, we prove the following results. Testing : We give a tolerant testing protocol to decide if a Hamiltonian is ε1\varepsilon _1ε1​ -close to k -local or ε2\varepsilon _2ε2​ -far from k -local in the ℓ2\ell _2ℓ2​ norm of the coefficients, with O(1/(ε2−ε1)4)O(1/(\varepsilon _2-\varepsilon _1)^{4})O(1/(ε2​−ε1​)4) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir (Bluhm, A., Caro, M.C., Oufkir, A.). We give a protocol for testing whether a Hamiltonian is ε1\varepsilon _1ε1​ -close to being s -sparse or ε2\varepsilon _2ε2​ -far from being s -sparse in the ℓ2\ell _2ℓ2​ norm of the coefficients, with O(s6/(ε22−ε12)6)O(s^{6}/(\varepsilon _2^2-\varepsilon _1^2)^{6})O(s6/(ε22​−ε12​)6) queries. Learning : We give a protocol to ε\varepsilon ε -learn unstructured Hamiltonian in the ℓ∞\ell _\infty ℓ∞​ norm of the coefficients with O(1/ε4)O(1/\varepsilon ^4)O(1/ε4) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k -local Hamiltonians in ℓ2\ell _2ℓ2​ norm of the coefficients that only uses O(exp⁡(k2+klog⁡(1/ε)))O(\exp (k^2+k\log (1/\varepsilon )))O(exp(k2+klog(1/ε))) queries. For Hamiltonians that are s -sparse in the Pauli basis, we can learn them in the ℓ2\ell _2ℓ2​ norm with O(s2/ε4)O(s^2/\varepsilon ^4)O(s2/ε4) queries. 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; squaring the query complexity and paying a (log⁡n)(\log n)(logn) -factor in the local case and an n -factor in the sparse case. Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians in the ℓ2\ell _2ℓ2​ norm using O~(s14/(ε22−ε12)18)\tilde{O}(s^{14}/(\varepsilon _2^2-\varepsilon _1^2)^{18})O~(s14/(ε22​−ε12​)18) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being ε1\varepsilon _1ε1​ -close to being s -sparse or ε2\varepsilon _2ε2​ -far under the diamond norm, using O~(s2/(ε2−ε1)6)\tilde{O}(s^2/(\varepsilon _2-\varepsilon _1)^6)O~(s2/(ε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 of the support of the Hamiltonian.
Decomposing classical matrices into linear combinations of Pauli strings is a major bottleneck for end-to-end implementations of near-term quantum algorithms. In this work, we consider a promise version of this Pauli decomposition problem in which the matrix is guaranteed to have support on only k=poly(n)k = \mathsf{poly}(n)k=poly(n) Pauli strings and is given through classical sparse query access. Existing Pauli decomposition algorithms are designed for the generic, dense problem and do not inherently take advantage of this promised sparsity, so these approaches take time that is exponential in nnn. We present a randomized classical algorithm that does take advantage of this sparsity and recovers the exact Pauli decomposition with success probability at least 1−δ1 - δ1−δ, for any δδδ. Under the stated access model, the algorithm executes with query and runtime complexity that is polynomial in nnn, kkk, and log⁡(1/δ)\log(1/δ)log(1/δ). These results show that, even though finding the Pauli decomposition is exponentially hard for general matrices, it becomes efficiently solvable for matrices that are known to be sparse in the Pauli basis, a regime that is relevant to near-term quantum algorithms operating on structured classical input.
We present an algorithm for performing quantum process tomography on an unknown nnn-qubit unitary CCC from the Clifford group. Our algorithm uses Bell basis measurements to deterministically learn CCC with 4n+34n + 34n+3 queries, which is the asymptotically optimal query complexity. In contrast to previous algorithms that required access to C†C^\daggerC† to achieve optimal query complexity, our algorithm achieves the same performance without querying C†C^\daggerC†. Additionally, we show the algorithm is robust to perturbations and can efficiently learn the closest Clifford to an unknown non-Clifford unitary UUU using query overhead that is logarithmic in the number of qubits.
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 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.