Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance

Zahra Honjani, Mohsen Heidari · 2026

Read Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance by Zahra Honjani, Mohsen Heidari (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00203.txt.

Introduction

Honjani and Heidari study learning unitaries whose Pauli spectrum concentrates on at most s components with small residual, covering sparse unitaries, k-juntas, and near-Clifford compositions. Given query access to a unitary, their algorithm builds a close channel with query counts growing polynomially in sparsity and inverse accuracy. A key part estimates large Pauli coefficients up to a shared phase, extending sparse recovery to general unitaries. For bounded Pauli norm unitaries, they prove an exponential query lower bound, then show learnability under a relaxed metric for input states.

Catalog record

CREATORZahra Honjani, Mohsen Heidari
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94983
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.00203

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance Zahra Honjani, Mohsen Heidari Abstract We study the problem of learning nearly ( s , ϵ ) (s,\epsilon) -sparse unitaries, meaning that the Pauli spectrum is concentrated on at most s s components with at most ϵ \epsilon residual mass in Pauli ℓ 1 \ell_{1} -norm. This class generalizes well-studied families, including sparse unitaries, quantum k k -juntas, 2 k 2^{k} -Pauli dimensional channels, and compositions of depth O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) circuits with near-Clifford circuits. Given query access to an unknown nearly sparse unitary U U , our goal is to efficiently (both in time and query complexity) construct a quantum channel that is close in diamond distance to U U . We design a learning algorithm achieving this guarantee using O ~ ​ ( s 6 / ϵ 4 ) \tilde{O}(s^{6}/\epsilon^{4}) forward queries to U 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 U , estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold θ \theta , extending existing sparse recovery techniques to general unitaries. We also study the broader class of unitaries with bounded Pauli ℓ 1 \ell_{1} -norm. For that class, we prove an exponential query lower bound Ω ⁡ ( 2 n / 2 ) \Omega(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 ℓ 1 \ell_{1} -norm uniformly bounded by L 1 L_{1} are learnable with O ~ ​ ( L 1 8 / ϵ 16 ) \tilde{O}(L_{1}^{8}/\epsilon^{16}) . \coltauthor Department of Computer Science, Indiana University Bloomington and Department of Computer Science, Indiana University Bloomington 1 Introduction Understanding the foundations of learning unknown quantum processes is a central problem with direct implications for the characterization and verification of quantum systems. This problem underlies a broad range of tasks, including quantum process tomography, Hamiltonian learning, and the verification and benchmarking of quantum devices. Without structural assumptions, however, learning quantum processes is intractable. In particular, learning an unknown n -qubit unitary with additive error \epsilon in diamond distance requires \Omega(4^{n}/\epsilon) queries ( Haah et al. 2023a ) . This raises a fundamental question: what natural structural assumptions and accuracy metrics enable efficient learning of quantum processes, and what are the resulting sample complexity bounds ? A growing body of work has addressed this question by studying unitaries with locality or sparsity structures in a known basis; most prominently the Pauli basis. Pauli sparsity leads to a simple description in a physically meaningful operator basis, and parallels classical sparse Boolean functions ( Kushilevitz and Mansour 1993 ) . Formally, an n -qubit operator U can be expressed in the Pauli basis as U=\sum_{\mathbf{s}}\alpha_{\mathbf{s}}\sigma^{\mathbf{s}} , where \sigma^{\mathbf{s}} are n -qubit Pauli operators indexed by \mathbf{s}\in\{0,1,2,3\}^{n} and \alpha_{\mathbf{s}} are the corresponding Pauli coefficients. An operator is s -sparse if it has at most s non-zero Pauli coefficients. In this work, we study the more general class of nearly (s,\epsilon) -sparse unitaries, whose Pauli spectrum is concentrated on a set \mathcal{S} of size at most s dominant components, while allowing for a \epsilon small residual mass, i.e., \sum_{\mathbf{s}\notin\mathcal{S}}|\alpha_{\mathbf{s}}|\leq\epsilon . Nearly sparse unitaries generalize several families including exactly s -sparse, quantum k -juntas, and compositions of depth O(\log\log n) circuits with near-Clifford circuits that have been studied extensively. Particularly, quantum k -juntas, as a special case of 4^{k} -sparse unitaries, are learnable with O(4^{k}/\epsilon) queries ( Chen et al. 2022 ; Bao and Yao 2023 ; Montanaro and Osborne 2010 ; Grewal and Liang 2025 ; Heidari and Szpankowski 2023 ) . More generally, unitaries whose Pauli support lies within a Pauli subgroup of size 2^{k} , and are therefore 2^{k} -sparse, can be learned with optimal query complexity \Theta(2^{k}/\epsilon) ( Grewal and Liang 2025 ) . Learning general sparse (and more broadly nearly sparse) unitaries remains an open question. This work aims to fill this gap by studying the learnability of nearly sparse unitaries. We make three main contributions, summarized bellow. 1.1 Summary of the main results First, we propose an efficient algorithm for identifying and estimating large Pauli coefficients of an unknown unitary U using only forward query access to U . This leads to the following result, abbreviated from Theorem 13 in Section 4 : Result 1 . There is an algorithm that, given \theta and query access to an unknown unitary U , estimates all Pauli coefficients of U with magnitude at least \theta , up to a global phase factor, with additive error O(\tfrac{\epsilon}{\theta}) using \tilde{O}(\frac{\log(1/\theta)}{\epsilon^{4}}) queries. The algorithm applies to arbitrary unitaries, without any sparsity assumptions, and treats U purely as a black box accessed via forward queries. This improves upon existing approaches ( Arunachalam et al. 2025 ; Abbas et al. 2025 ; Montanaro and Osborne 2010 ; Grewal and Liang 2025 ; Hu et al. 2025 ) , which require additional structure such as subgroup support, Boolean-valued spectra, or access to time-evolution at small evolution times. Note that the resulted estimates \hat{\alpha}_{\mathbf{s}} are close to e^{i\phi}\alpha_{\mathbf{s}} , for some unknown \phi\in[0,\pi] . This global phase ambiguity is unavoidable without access to controlled- U . Our approach builds upon the estimation algorithm of ( Arunachalam et al. 2025 ) originally developed for Hamiltonian learning via access to short-time evolution operators of the form U=e^{-iHt} . We employ Bell sampling on the Choi state of U to efficiently locate the dominant Pauli components. However, the coefficient estimation techniques used in prior Hamiltonian learning works ( Arunachalam et al. 2025 ; Abbas et al. 2025 ) do not directly extend to arbitrary unitaries, as they rely on linear approximations of the form U\approx I-itH , which require small evolution times. In contrast, a general unitary or the time evolution of a Hamiltonian at large times—need not be close to the identity. Moreover, existing shadow tomography methods for estimating Pauli observables, such as ( Chen et al. 2024 ; King et al. ) , are not directly applicable, since the Pauli coefficients of a unitary operator are generally complex-valued rather than real. We overcome these challenges by first estimating the magnitude of the largest Pauli coefficient, and then using this estimate to combine Bell sampling with classical shadow tomography based on random Clifford measurements. This enables accurate estimation of both the magnitude and relative phase of the dominant Pauli coefficients of U . Second, we analyze the query complexity of learning nearly sparse unitaries. Moreover, we use our estimation algorithm for efficiently learning nearly-sparse unitaries. We have the following main results, abbreviated from Theorem 14 in Section 5 : Result 2 . There exists an algorithm that learns nearly (s,\epsilon) -sparse unitaries in diamond distance using \tilde{O}(\frac{s^{6}}{\epsilon^{4}}) queries. Moreover, there exists a polynomial time quantum algorithm that learns nearly sparse unitaries using the same number of queries, and with additive error O(\sqrt{s\epsilon}) in diamond distance. Learning unitaries under the diamond norm poses several challenges. The diamond distance depends on the \ell_{1} -norm of

Read the complete text