Query-Optimal Estimation of Unitary Channels via Pauli Dimensionality

• URL: http://arxiv.org/abs/2510.00168v1
• Date: Tue, 30 Sep 2025 18:40:42 GMT
• Title: Query-Optimal Estimation of Unitary Channels via Pauli Dimensionality
• Authors: Sabee Grewal, Daniel Liang,
• Abstract summary: We study process tomography of unitary channels whose Pauli spectrum is supported on a small subgroup.<n>We present an algorithm that achieves this using $O(2k/epsilon)$ queries.<n>We also give a computationally efficient algorithm for learning compositions of depth-$O(log n)$ circuits with near-Clifford circuits.
• Score: 0.8594140167290097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study process tomography of unitary channels whose Pauli spectrum is supported on a small subgroup. Given query access to an unknown unitary channel whose Pauli spectrum is supported on a subgroup of size $2^k$, our goal is to output a classical description that is $\epsilon$-close to the unknown unitary in diamond distance. We present an algorithm that achieves this using $O(2^k/\epsilon)$ queries, and we prove matching lower bounds, establishing query optimality of our algorithm. When $k = 2n$, so that the support is the full Pauli group, our result recovers the query-optimal $O(4^n/\epsilon)$-query algorithm of Haah, Kothari, O'Donnell, and Tang [FOCS '23]. Our result has two notable consequences. First, we give a query-optimal $O(4^k/\epsilon)$-query algorithm for learning quantum $k$-juntas -- unitary channels that act non-trivially on only $k$ of the $n$ qubits -- to accuracy $\epsilon$ in diamond distance. This represents an exponential improvement in both query and time complexity over prior work. Second, we give a computationally efficient algorithm for learning compositions of depth-$O(\log \log n)$ circuits with near-Clifford circuits, where "near-Clifford" means a Clifford circuit augmented with at most $O(\log n)$ non-Clifford single-qubit gates. This unifies prior work, which could handle only constant-depth circuits or near-Clifford circuits, but not their composition.

Related papers

• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  We design efficient algorithms for learning halfspaces without point synthesis.<n>As a corollary, we obtain an optimal $O(d + log n)$ query deterministic learner for axis-aligned halfspaces.<n>Our algorithm solves the more general problem of learning a Boolean function $f$ over $n$ elements which is monotone under at least one of $D$ provided orderings.
  arXiv  Detail & Related papers  (2025-09-25T07:39:25Z)
• Process Tomography for Clifford Unitaries [0.08594140167290097]
  We present an algorithm for performing quantum process tomography on an unknown $n$-qubit unitary $C$.<n>Our algorithm achieves the same performance without querying $Cdagger$.
  arXiv  Detail & Related papers  (2025-05-12T21:11:04Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Do you know what q-means? [42.96240569413475]
  We present a classical $varepsilon$-$k$-means algorithm that performs an approximate version of one iteration of Lloyd's algorithm with time complexity.<n>We also propose an improved $q$-means quantum algorithm with time complexity.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates [0.43123403062068827]
  We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and $O(log n)$ non-Clifford gates. Specifically, for an $n$-qubit state $|psirangle$ prepared with at most $t$ non-Clifford gates, our algorithms use $mathsfpoly(n,2t,1/varepsilon)$ time and copies of $|psirangle$ to learn $|psirangle$ to trace distance at most gates.
  arXiv  Detail & Related papers  (2023-05-22T18:49:52Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
  arXiv  Detail & Related papers  (2021-06-14T07:36:25Z)
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits [1.933681537640272]
  We use nested meet-in-the-middle technique to develop algorithms for synthesizing provably emphdepth-optimal and emphT-depth-optimal circuits. For synthesizing T-depth-optimal circuits, we get an algorithm with space and time complexity $Oleft(left(4n2right)lceil d/crceilright)$. Our algorithm has space and time complexity $poly(n,25.6n,d)$ (or $poly(nlog n,
  arXiv  Detail & Related papers  (2021-01-08T18:13:36Z)
• Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
  We first obtain optimal exact quantum query algorithms ($Q_algo(f)$) for a direct sum based class of $Omega left( 2fracsqrtn2 right)$ non-symmetric functions. We show that query complexity of $Q_algo$ is $lceil frac3n4 rceil$ whereas $D_oplus(f)$ varies between $n-1$ and $lceil frac3n4 rce
  arXiv  Detail & Related papers  (2020-08-14T12:17:48Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.