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:2408.16244 · Physical Review Letters

Quantum Advantage via Efficient Postprocessing on Qudit Classical Shadow Tomography

Yu Wang

Published Nov 13, 2025• 1 citation
arXivHTMLPDF

Abstract

Computing inner products of the form tr(AB), where A is a d-dimensional density matrix [with tr(A)=1, A≥0] and B is a bounded-norm observable [Hermitian with tr(B^{2})≤O[poly(logd)] and tr(B) known], is fundamental across quantum science and artificial intelligence. Classically, both computing and storing such inner products require O(d^{2}) resources, which rapidly becomes prohibitive as d grows exponentially. In this Letter, we introduce a quantum approach based on qudit classical shadow tomography, significantly reducing computational complexity from O(d^{2}) down to O[poly(logd)] in typical cases and at least to O[dpoly(logd)] in the worst case. Specifically, for n-qubit systems (with n being the number of qubit and d=2^{n}), our method guarantees efficient estimation of tr(ρO) for any known stabilizer state ρ and arbitrary bounded-norm observable O, using polynomial computational resources. Crucially, it ensures constant-time classical postprocessing per measurement and supports qubit and qudit platforms. Moreover, classical storage complexity of A reduces from O(d^{2}) to O(mlogd), where the sample complexity m is typically exponentially smaller than d^{2}. Our results establish a practical and modular quantum subroutine, enabling scalable quantum advantages in tasks involving high-dimensional data analysis and processing.

DOI
10.1103/92ky-ln8f

Related papers

Dimension-Free Polylogarithmic Quantum Shadow Tomography

Fernando Granha Jeronimo, Qizhao Huang, Lenny Liu

Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown $d$-dimensional quantum state $ρ$ and a known collection of observables $E_1,\ldots,E_M$, the goal is to estimate all expectation values $\{\text{Tr}(ρE_i)\}_{i=1}^M$ to additive accuracy $\varepsilon$ with probability at least $1-δ$. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on $M$, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity \[ O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), \] which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.

quant-pharXiv:2608.06345•Aug 7, 2026•0 citations

Reconstructing quantum states efficiently

M. Cramer, Martin Bodo Plenio

Quantum state tomography, the ability to deduce the density matrix of a quantum system from measured data, is of fundamental importance for the verification of present and future quantum devices. It has been realized in systems with few components but for larger systems it becomes rapidly infeasible because the number of quantum measurements and computational resources required to process them grow exponentially in the system size. Here we show that we can gain an exponential advantage over direct state tomography for quantum states typically realized in nature. Based on singular value thresholding and matrix product state methods we introduce a state reconstruction scheme that relies only on a linear number of measurements. The computational resources for the postprocessing required to reconstruct the state with high fidelity from these measurements is polynomial in the system size.

arXiv:1002.3780•Feb 19, 2010•5 citations

A computationally efficient approach to quantum state reconstruction using robust classical shadows

Sanjay Sharma, Shyam Akashe, Govind Murari Upadhyay +1 more

Quantum state tomography is a fundamental technique for characterizing quantum systems, but its scalability remains a significant challenge. This paper investigates an efficient alternative using classical shadows to reconstruct a Bell state with high fidelity. Classical shadows provide a compressed representation of a quantum state using randomized measurements, reducing the measurement complexity compared to full quantum tomography when full state reconstruction is not required. We employed a quantum circuit to generate a Bell state and utilize 1000 snapshots to construct its classical shadow. The reconstructed density matrix is evaluated using fidelity and norm difference metrics against the ideal Bell state. Our analysis demonstrates that as the number of snapshots increases, the fidelity of reconstruction stabilizes around 0.98-1.0, with the norm difference decreasing accordingly. The results also confirm the convergence of reconstructed states towards the ideal Bell state, highlighting the efficiency and accuracy of classical shadows in quantum state estimation. Shallow shadow tomography uses shallow random circuits to estimate global quantum state properties on noisy hardware. By combining low-depth entangling gates with randomized measurements and noise-aware postprocessing, it reduces sample complexity compared to Pauli shadows while remaining experimentally feasible. Recent experiments on superconducting processors confirmed up to fivefold measurement savings.

Scientific Reports•Feb 2, 2026•0 citations

Improved Quantum data analysis

Costin Bădescu, Ryan O’Donnell

We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum ”Threshold Search” algorithm that requires only O((log2 m)/є2) samples of a d-dimensional state ρ. That is, given observables 0 ≤ A1, A2, …, Am ≤ 1 such that (ρ Ai) ≥ 1/2 for at least one i, the algorithm finds j with (ρ Aj) ≥ 1/2−є. As a consequence, we obtain a Shadow Tomography algorithm requiring only O((log2 m)(logd)/є4) samples, which simultaneously achieves the best known dependence on each parameter m, d, є. This yields the same sample complexity for quantum Hypothesis Selection among m states; we also give an alternative Hypothesis Selection method using O((log3 m)/є2) samples.

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2021•41 citations

Sketch Tomography: Hybridizing Classical Shadow and Matrix Product State

Xun Tang, Haoxuan Chen, Yuehaw Khoo +1 more

We introduce Sketch Tomography, an efficient procedure for quantum state tomography based on the classical shadow protocol used for quantum observable estimations. The procedure applies to the case where the ground truth quantum state is a matrix product state (MPS). The density matrix of the ground truth state admits a tensor train ansatz as a result of the MPS assumption, and we estimate the tensor components of the ansatz through a series of observable estimations, thus outputting an approximation of the density matrix. The procedure is provably convergent with a sample complexity that scales quadratically in the system size. We conduct extensive numerical experiments to show that the procedure outputs an accurate approximation to the quantum state. For observable estimation tasks involving moderately large subsystems, we show that our procedure gives rise to a more accurate estimation than the classical shadow protocol. We also show that sketch tomography is more accurate in observable estimation than quantum states trained from the maximum likelihood estimation formulation.

quant-pharXiv:2512.03333•Dec 4, 2025•0 citations

High-dimensional subspace expansion using classical shadows

Gregory Boyd, Bálint Koczor, Zhenyu Cai

We introduce a postprocessing technique for classical shadow measurement data that enhances the precision of ground state estimation through high-dimensional subspace expansion; the dimensionality is only limited by the amount of classical postprocessing resources rather than by quantum resources. Crucial steps of our approach are the efficient identification of useful observables from shadow data, followed by our regularized subspace expansion that is designed to be numerically stable even when using noisy data. We analytically investigate noise propagation within our method, and upper bound the statistical fluctuations due to the limited number of snapshots in classical shadows. In numerical simulations, our method can achieve a reduction in the energy estimation errors in many cases, sometimes by more than an order of magnitude. We also demonstrate that our performance improvements are robust against both coherent errors (bad initial state) and gate noise in the state-preparation circuits. Furthermore, performance is guaranteed to be at least as good—and in many cases better—than direct energy estimation without using additional quantum resources, and the approach is thus a very natural alternative for estimating ground state energies directly from classical shadow data.

arXiv:2406.11533•Physical Review A•Feb 13, 2025•4 citations
Computing inner products of the form tr(AB), where A is a d-dimensional density matrix [with tr(A)=1, A≥0] and B is a bounded-norm observable [Hermitian with tr(B^{2})≤O[poly(logd)] and tr(B) known], is fundamental across quantum science and artificial intelligence. Classically, both computing and storing such inner products require O(d^{2}) resources, which rapidly becomes prohibitive as d grows exponentially. In this Letter, we introduce a quantum approach based on qudit classical shadow tomography, significantly reducing computational complexity from O(d^{2}) down to O[poly(logd)] in typical cases and at least to O[dpoly(logd)] in the worst case. Specifically, for n-qubit systems (with n being the number of qubit and d=2^{n}), our method guarantees efficient estimation of tr(ρO) for any known stabilizer state ρ and arbitrary bounded-norm observable O, using polynomial computational resources. Crucially, it ensures constant-time classical postprocessing per measurement and supports qubit and qudit platforms. Moreover, classical storage complexity of A reduces from O(d^{2}) to O(mlogd), where the sample complexity m is typically exponentially smaller than d^{2}. Our results establish a practical and modular quantum subroutine, enabling scalable quantum advantages in tasks involving high-dimensional data analysis and processing.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown ddd-dimensional quantum state ρρρ and a known collection of observables E1,…,EME_1,\ldots,E_ME1​,…,EM​, the goal is to estimate all expectation values {Tr(ρEi)}i=1M\{\text{Tr}(ρE_i)\}_{i=1}^M{Tr(ρEi​)}i=1M​ to additive accuracy ε\varepsilonε with probability at least 1−δ1-δ1−δ. An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on MMM, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(log⁡(M)log⁡(M/δ)ε2), O\left( \frac{\log(M)\log(M/δ)}{\varepsilon^2} \right), O(ε2log(M)log(M/δ)​), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright. Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.
Quantum state tomography, the ability to deduce the density matrix of a quantum system from measured data, is of fundamental importance for the verification of present and future quantum devices. It has been realized in systems with few components but for larger systems it becomes rapidly infeasible because the number of quantum measurements and computational resources required to process them grow exponentially in the system size. Here we show that we can gain an exponential advantage over direct state tomography for quantum states typically realized in nature. Based on singular value thresholding and matrix product state methods we introduce a state reconstruction scheme that relies only on a linear number of measurements. The computational resources for the postprocessing required to reconstruct the state with high fidelity from these measurements is polynomial in the system size.
Quantum state tomography is a fundamental technique for characterizing quantum systems, but its scalability remains a significant challenge. This paper investigates an efficient alternative using classical shadows to reconstruct a Bell state with high fidelity. Classical shadows provide a compressed representation of a quantum state using randomized measurements, reducing the measurement complexity compared to full quantum tomography when full state reconstruction is not required. We employed a quantum circuit to generate a Bell state and utilize 1000 snapshots to construct its classical shadow. The reconstructed density matrix is evaluated using fidelity and norm difference metrics against the ideal Bell state. Our analysis demonstrates that as the number of snapshots increases, the fidelity of reconstruction stabilizes around 0.98-1.0, with the norm difference decreasing accordingly. The results also confirm the convergence of reconstructed states towards the ideal Bell state, highlighting the efficiency and accuracy of classical shadows in quantum state estimation. Shallow shadow tomography uses shallow random circuits to estimate global quantum state properties on noisy hardware. By combining low-depth entangling gates with randomized measurements and noise-aware postprocessing, it reduces sample complexity compared to Pauli shadows while remaining experimentally feasible. Recent experiments on superconducting processors confirmed up to fivefold measurement savings.
We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum ”Threshold Search” algorithm that requires only O((log2 m)/є2) samples of a d-dimensional state ρ. That is, given observables 0 ≤ A1, A2, …, Am ≤ 1 such that (ρ Ai) ≥ 1/2 for at least one i, the algorithm finds j with (ρ Aj) ≥ 1/2−є. As a consequence, we obtain a Shadow Tomography algorithm requiring only O((log2 m)(logd)/є4) samples, which simultaneously achieves the best known dependence on each parameter m, d, є. This yields the same sample complexity for quantum Hypothesis Selection among m states; we also give an alternative Hypothesis Selection method using O((log3 m)/є2) samples.
We introduce Sketch Tomography, an efficient procedure for quantum state tomography based on the classical shadow protocol used for quantum observable estimations. The procedure applies to the case where the ground truth quantum state is a matrix product state (MPS). The density matrix of the ground truth state admits a tensor train ansatz as a result of the MPS assumption, and we estimate the tensor components of the ansatz through a series of observable estimations, thus outputting an approximation of the density matrix. The procedure is provably convergent with a sample complexity that scales quadratically in the system size. We conduct extensive numerical experiments to show that the procedure outputs an accurate approximation to the quantum state. For observable estimation tasks involving moderately large subsystems, we show that our procedure gives rise to a more accurate estimation than the classical shadow protocol. We also show that sketch tomography is more accurate in observable estimation than quantum states trained from the maximum likelihood estimation formulation.
We introduce a postprocessing technique for classical shadow measurement data that enhances the precision of ground state estimation through high-dimensional subspace expansion; the dimensionality is only limited by the amount of classical postprocessing resources rather than by quantum resources. Crucial steps of our approach are the efficient identification of useful observables from shadow data, followed by our regularized subspace expansion that is designed to be numerically stable even when using noisy data. We analytically investigate noise propagation within our method, and upper bound the statistical fluctuations due to the limited number of snapshots in classical shadows. In numerical simulations, our method can achieve a reduction in the energy estimation errors in many cases, sometimes by more than an order of magnitude. We also demonstrate that our performance improvements are robust against both coherent errors (bad initial state) and gate noise in the state-preparation circuits. Furthermore, performance is guaranteed to be at least as good—and in many cases better—than direct energy estimation without using additional quantum resources, and the approach is thus a very natural alternative for estimating ground state energies directly from classical shadow data.