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:2410.11957 · PRX Quantum

Agnostic Process Tomography

Chirag Wadhwa, Laura Lewis, Elham Kashefi, Mina Doosti

Published Oct 27, 2025• 3 citations
arXivHTMLPDF

Abstract

Characterizing a quantum system by learning its state or evolution is a fundamental problem in quantum physics and learning theory with a myriad of applications. Recently, as a new approach to this problem, the task of agnostic state tomography was defined, in which one aims to approximate an arbitrary quantum state by a simpler one in a given class. Generalizing this notion to quantum processes, we initiate the study of agnostic process tomography: given query access to an unknown quantum channel Φ and a known concept class C of channels, output a quantum channel that approximates Φ as well as any channel in the concept class C , up to some error. In this work, we propose several natural applications for this new task in quantum machine learning, quantum metrology, classical simulation, and error mitigation. In addition, we give efficient agnostic process tomography algorithms for a wide variety of concept classes, including Pauli strings, Pauli channels, quantum junta channels, low-degree channels, and a class of channels produced by Q A C 0 circuits. The main technical tool we use is Pauli spectrum analysis of operators and superoperators. We also prove that, using ancilla qubits, any agnostic state tomography algorithm can be extended to one solving agnostic process tomography for a compatible concept class of unitaries, immediately giving us efficient agnostic learning algorithms for Clifford circuits, Clifford circuits with few T gates, and circuits consisting of a tensor product of single-qubit gates. Together, our results provide insight into the conditions and new algorithms necessary to extend the learnability of a concept class from the standard tomographic setting to the agnostic one.

DOI
10.1103/q2nb-zg9m

Related papers

Efficient Noisy Quantum State and Process Tomography

Chenyang Li, Shengxin Zhuang, Yukun Zhang +4 more

Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy $n$-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit ($γ= 0$) and the strong-decoherence regime ($γ= Θ(1)$). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.

quant-pharXiv:2603.01521•Quantum Science and Technology•Mar 3, 2026•0 citations

Efficient learning of quantum states and circuits

Sabee Grewal

Preparing complex quantum states is of limited value without efficient methods for extracting useful classical information from them. This thesis studies when such information can be extracted efficiently, given copies of an unknown quantum state or query access to an unknown unitary transformation. We begin with pure state tomography. We present an algorithm that uses only nonadaptive single-qubit Pauli measurements yet achieves optimal copy and time complexities up to logarithmic factors. This is the first full state tomography algorithm with near-optimal running time. We then show how additional structure can make tomography time-efficient, giving algorithms for two structured classes of quantum states: non-interacting fermions and near-stabilizer states. We also introduce a new learning task, agnostic tomography, where the goal is to find the best approximation to an arbitrary quantum state from a structured class of states, and give efficient algorithms in this model. Turning to property testing, we give an efficient tester for stabilizer dimension, which implies that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare n-qubit computationally pseudorandom states. We also prove copy-complexity lower bounds for testing low-degree phase states, showing that testing is nearly as hard as learning these states. More strongly, for every fixed degree d, ensembles of n-qubit degree-d phase states form exponentially accurate approximate state t-designs for t=Ω(n^{⌊(d-1)/2⌋}). Finally, we extend these questions from states to unitary transformations. We develop a general framework for learning unitary transformations by exploiting low-complexity Pauli spectra. This framework unifies and extends prior learning algorithms for Clifford and near-Clifford circuits, shallow circuits, quantum juntas, and fermionic matchgate circuits.

•Aug 1, 2026•0 citations

Learning Clifford-structured quantum unitaries and Hamiltonians

Arkopal Dutt, Dale Jacobs, John Jeang +2 more

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.

quant-pharXiv:2608.09912•Aug 11, 2026•0 citations

Agnostic Product Mixed State Tomography via Robust Statistics

Alvan Caleb Arulandu, Ilias Diakonikolas, Daniel M. Kane +1 more

We study the complexity of two closely related learning problems, one quantum and one classical. In the quantum setting, we consider agnostic tomography for the natural class of product mixed states. Given $N$ copies of an $n$-qubit state $ρ$, the goal is to output a nearly optimal product mixed state approximation in trace distance. While recent work has focused on pure-state ansatz (e.g., product or stabilizer states), no polynomial-time guarantees were previously known for mixed-state ansatz. In the classical setting, we study robust learning of binary product distributions: given samples from an unknown distribution on ${0,1}^n$, the goal is to output a nearly optimal product approximation. Our main contributions are as follows. (1) We give a semi-agnostic tomography algorithm for product mixed states with polynomial sample and computational complexity achieving error $O(\mathrm{opt}\log(1/\mathrm{opt}))$, where $\mathrm{opt}$ is the trace distance to the best product approximation. This is the first efficient algorithm with any nontrivial agnostic guarantee for mixed-state ansatz, using only single-qubit, single-copy measurements. We also prove a Quantum Statistical Query lower bound showing near-optimality, and an unconditional lower bound demonstrating that adaptivity is necessary under single-qubit measurements. (2) We give a semi-agnostic algorithm for robustly learning binary product distributions with matching guarantees and establish a Statistical Query lower bound, essentially resolving the efficient robust learnability of this class and improving on prior work since Diakonikolas et al. (2016).

arXiv:2510.08472•Oct 9, 2025•0 citations

Agnostic Tomography of Stabilizer Product States

Sabee Grewal, Vishnu Iyer, William Kretschmer +1 more

We define a quantum learning task called agnostic tomography , where given copies of an arbitrary state ρ and a class of quantum states C , the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε ). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ .We give an efficient agnostic tomography algorithm for the class C of n -qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time n O ( log ⁡ ( 2 / τ ) ) / ε 2 , which is p o l y ( n / ε ) for any constant τ .

arXiv:2404.03813•Quantum•Mar 13, 2026•1 citation

Optimal learning of quantum channels in diamond distance

Antonio Anna Mele, Lennart Bittel

Quantum process tomography, the task of estimating an unknown quantum channel, is a central problem in quantum information theory. A long-standing open question is how many uses of an unknown channel are required to learn it in diamond distance, the standard metric for distinguishing quantum processes. While quantum state tomography is well understood, for general channels the problem remained open beyond the unitary case. Here we establish the query complexity of channel tomography with optimal dependence on the dimension parameters, at any fixed constant accuracy. We design an algorithm showing that any channel with input/output dimensions $d_{\mathrm{in}},d_{\mathrm{out}}$ and Kraus rank at most $k$ can be learned to accuracy $\varepsilon$ using $O(d_{\mathrm{in}}d_{\mathrm{out}}k/\varepsilon^{2})$ channel uses. Conversely, we prove that $Ω(d_{\mathrm{in}}d_{\mathrm{out}}k)$ uses are necessary at constant accuracy and that, for non-minimal Kraus rank, a separate $Ω(1/\varepsilon^{2})$ contribution is unavoidable. Since channels subsume states, unitaries, isometries, and measurements as special cases, our protocol provides a unified framework for these tomography tasks, yielding new guarantees for isometry and measurement tomography while recovering known optimal scalings for state and unitary tomography. Our algorithm follows the natural strategy of performing optimal tomography on the Choi state. The main technical contribution is to show that this suffices to control the induced diamond-distance error, avoiding the dimension loss incurred by a naive conversion from Choi-state trace distance to channel diamond distance. The protocol uses the channel non-adaptively to prepare Choi-state copies, purifies them in parallel, and performs optimal pure-state tomography on the resulting purifications. Hence, we reduce channel tomography to pure-state tomography.

quant-pharXiv:2512.10214•Dec 12, 2025•0 citations
Characterizing a quantum system by learning its state or evolution is a fundamental problem in quantum physics and learning theory with a myriad of applications. Recently, as a new approach to this problem, the task of agnostic state tomography was defined, in which one aims to approximate an arbitrary quantum state by a simpler one in a given class. Generalizing this notion to quantum processes, we initiate the study of agnostic process tomography: given query access to an unknown quantum channel Φ and a known concept class C of channels, output a quantum channel that approximates Φ as well as any channel in the concept class C , up to some error. In this work, we propose several natural applications for this new task in quantum machine learning, quantum metrology, classical simulation, and error mitigation. In addition, we give efficient agnostic process tomography algorithms for a wide variety of concept classes, including Pauli strings, Pauli channels, quantum junta channels, low-degree channels, and a class of channels produced by Q A C 0 circuits. The main technical tool we use is Pauli spectrum analysis of operators and superoperators. We also prove that, using ancilla qubits, any agnostic state tomography algorithm can be extended to one solving agnostic process tomography for a compatible concept class of unitaries, immediately giving us efficient agnostic learning algorithms for Clifford circuits, Clifford circuits with few T gates, and circuits consisting of a tensor product of single-qubit gates. Together, our results provide insight into the conditions and new algorithms necessary to extend the learnability of a concept class from the standard tomographic setting to the agnostic one.
Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy nnn-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit (γ=0γ= 0γ=0) and the strong-decoherence regime (γ=Θ(1)γ= Θ(1)γ=Θ(1)). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.
Preparing complex quantum states is of limited value without efficient methods for extracting useful classical information from them. This thesis studies when such information can be extracted efficiently, given copies of an unknown quantum state or query access to an unknown unitary transformation. We begin with pure state tomography. We present an algorithm that uses only nonadaptive single-qubit Pauli measurements yet achieves optimal copy and time complexities up to logarithmic factors. This is the first full state tomography algorithm with near-optimal running time. We then show how additional structure can make tomography time-efficient, giving algorithms for two structured classes of quantum states: non-interacting fermions and near-stabilizer states. We also introduce a new learning task, agnostic tomography, where the goal is to find the best approximation to an arbitrary quantum state from a structured class of states, and give efficient algorithms in this model. Turning to property testing, we give an efficient tester for stabilizer dimension, which implies that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare n-qubit computationally pseudorandom states. We also prove copy-complexity lower bounds for testing low-degree phase states, showing that testing is nearly as hard as learning these states. More strongly, for every fixed degree d, ensembles of n-qubit degree-d phase states form exponentially accurate approximate state t-designs for t=Ω(n^{⌊(d-1)/2⌋}). Finally, we extend these questions from states to unitary transformations. We develop a general framework for learning unitary transformations by exploiting low-complexity Pauli spectra. This framework unifies and extends prior learning algorithms for Clifford and near-Clifford circuits, shallow circuits, quantum juntas, and fermionic matchgate circuits.
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 complexity of two closely related learning problems, one quantum and one classical. In the quantum setting, we consider agnostic tomography for the natural class of product mixed states. Given NNN copies of an nnn-qubit state ρρρ, the goal is to output a nearly optimal product mixed state approximation in trace distance. While recent work has focused on pure-state ansatz (e.g., product or stabilizer states), no polynomial-time guarantees were previously known for mixed-state ansatz. In the classical setting, we study robust learning of binary product distributions: given samples from an unknown distribution on 0,1n{0,1}^n0,1n, the goal is to output a nearly optimal product approximation. Our main contributions are as follows. (1) We give a semi-agnostic tomography algorithm for product mixed states with polynomial sample and computational complexity achieving error O(optlog⁡(1/opt))O(\mathrm{opt}\log(1/\mathrm{opt}))O(optlog(1/opt)), where opt\mathrm{opt}opt is the trace distance to the best product approximation. This is the first efficient algorithm with any nontrivial agnostic guarantee for mixed-state ansatz, using only single-qubit, single-copy measurements. We also prove a Quantum Statistical Query lower bound showing near-optimality, and an unconditional lower bound demonstrating that adaptivity is necessary under single-qubit measurements. (2) We give a semi-agnostic algorithm for robustly learning binary product distributions with matching guarantees and establish a Statistical Query lower bound, essentially resolving the efficient robust learnability of this class and improving on prior work since Diakonikolas et al. (2016).
We define a quantum learning task called agnostic tomography , where given copies of an arbitrary state ρ and a class of quantum states C , the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε ). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ .We give an efficient agnostic tomography algorithm for the class C of n -qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time n O ( log ⁡ ( 2 / τ ) ) / ε 2 , which is p o l y ( n / ε ) for any constant τ .
Quantum process tomography, the task of estimating an unknown quantum channel, is a central problem in quantum information theory. A long-standing open question is how many uses of an unknown channel are required to learn it in diamond distance, the standard metric for distinguishing quantum processes. While quantum state tomography is well understood, for general channels the problem remained open beyond the unitary case. Here we establish the query complexity of channel tomography with optimal dependence on the dimension parameters, at any fixed constant accuracy. We design an algorithm showing that any channel with input/output dimensions din,doutd_{\mathrm{in}},d_{\mathrm{out}}din​,dout​ and Kraus rank at most kkk can be learned to accuracy ε\varepsilonε using O(dindoutk/ε2)O(d_{\mathrm{in}}d_{\mathrm{out}}k/\varepsilon^{2})O(din​dout​k/ε2) channel uses. Conversely, we prove that Ω(dindoutk)Ω(d_{\mathrm{in}}d_{\mathrm{out}}k)Ω(din​dout​k) uses are necessary at constant accuracy and that, for non-minimal Kraus rank, a separate Ω(1/ε2)Ω(1/\varepsilon^{2})Ω(1/ε2) contribution is unavoidable. Since channels subsume states, unitaries, isometries, and measurements as special cases, our protocol provides a unified framework for these tomography tasks, yielding new guarantees for isometry and measurement tomography while recovering known optimal scalings for state and unitary tomography. Our algorithm follows the natural strategy of performing optimal tomography on the Choi state. The main technical contribution is to show that this suffices to control the induced diamond-distance error, avoiding the dimension loss incurred by a naive conversion from Choi-state trace distance to channel diamond distance. The protocol uses the channel non-adaptively to prepare Choi-state copies, purifies them in parallel, and performs optimal pure-state tomography on the resulting purifications. Hence, we reduce channel tomography to pure-state tomography.