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:2009.04610

Sample efficient tomography via Pauli Measurements

Nengkun Yu

Published Sep 10, 2020• 7 citations
arXivHTMLPDF

Abstract

Pauli Measurements are the most important measurements in both theoretical and experimental aspects of quantum information science. In this paper, we explore the power of Pauli measurements in the state tomography related problems. Firstly, we show that the \textit{quantum state tomography} problem of $n$-qubit system can be accomplished with ${\mathcal{O}}(\frac{10^n}{ε^2})$ copies of the unknown state using Pauli measurements. As a direct application, we studied the \textit{quantum overlapping tomography} problem introduced by Cotler and Wilczek in Ref. \cite{Cotler_2020}. We show that the sample complexity is $\mathcal{O}(\frac{10^k\cdot\log({{n}\choose{k}}/δ))}{ε^{2}})$ for quantum overlapping tomography of $k$-qubit reduced density matrices among $n$ is quantum system, where $1-δ$ is the confidential level, and $ε$ is the trace distance error. This can be achieved using Pauli measurements. Moreover, we prove that $Ω(\frac{\log(n/δ)}{ε^{2}})$ copies are needed. In other words, for constant $k$, joint, highly entangled, measurements are not asymptotically more efficient than Pauli measurements.

DOI
10.48550/arxiv.2009.04610

Related papers

Pauli Measurements Are Not Optimal for Single-Copy Tomography

Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu +1 more

Quantum state tomography is a fundamental problem in quantum computing. Given n copies of an unknown N -qubit state ρ∈ℂ d × d , d =2 N , the goal is to learn the state up to an accuracy ε in trace distance, say with at least constant probability 0.99. We are interested in the copy complexity, the minimum number of copies of ρ needed to fulfill the task. As current quantum devices are physically limited, Pauli measurements have attracted significant attention due to their ease of implementation. However, a large gap exists in the literature for tomography with Pauli measurements. The best-known upper bound is O ( N · 12 N /ε 2 ), and no non-trivial lower bound is known besides the general single-copy lower bound of Ω(8 N /ε 2 ), achieved by hard-to-implement structured POVMs such as MUB, SIC-POVM, and uniform POVM. We have made significant progress on this long-standing problem. We first prove a stronger upper bound of O (10 N /ε 2 ). To complement it, we also obtain a lower bound of Ω(9.118 N /ε 2 ), which holds even with adaptivity. To our knowledge, this demonstrates the first known separation between Pauli measurements and structured POVMs. The new lower bound is a consequence of a novel framework for adaptive quantum state tomography with measurement constraints. The main advantage is that we can use measurement-dependent hard instances to prove tight lower bounds for Pauli measurements, while prior lower-bound techniques for tomography only work with measurement-independent constructions. Moreover, we connect the copy complexity lower bound of tomography to the eigenvalues of the measurement information channel, which governs the measurement’s capacity to distinguish between states. To demonstrate the generality of the new framework, we obtain tight bounds for adaptive quantum state tomography with k -outcome measurements, where we recover existing results and establish new ones.

arXiv:2502.18170•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•1 citation

Efficient quantum state tomography with auxiliary systems

Wenlong Zhao, Da Zhang, Huili Zhang +2 more

Quantum state tomography is a technique in quantum information science used to reconstruct the density matrix of an unknown quantum state, providing complete information about the quantum state. It is of significant importance in fields such as quantum computation, quantum communication, and quantum simulation. However, as the size of the quantum system increases, the number of measurement settings and sampling requirements for quantum state tomography grow exponentially with the number of qubits. This not only makes experimental design and implementation more complex, but also exacerbates the consumption of experimental resources. These limitations severely hinder the application of state tomography in large-scale quantum systems. To reduce measurement settings and improve sampling efficiency, this study proposes a state tomography method based on auxiliary systems. This method can be implemented through either entanglement between the quantum system to be measured and a quantum auxiliary system or through correlation between the quantum system and a probabilistic classical auxiliary system. Measurements on the entire joint system enable more efficient extraction of information about the quantum state to be measured. This method relies on standard quantum gate operations and requires only two measurement settings, with a total sampling complexity of $O(d^2)$, significantly simplifying experimental operations and measurement processes. Additionally, this study provides two schemes for measuring purity based on the proposed circuit, one of which achieves measurement precision at the Heisenberg limit. This study validates the effectiveness of the proposed method through a detailed theoretical analysis, a series of numerical simulations, and experiments.

arXiv:2507.16532•Physical Review A•Mar 2, 2026•0 citations

Learning Quantum States Without Entangled Measurements

Angus Lowe

How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.

•Oct 22, 2021•4 citations

Nearly Time-Optimal Pure State Tomography with Pauli Measurements

Sabee Grewal, Meghal Gupta, William He +2 more

We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given $\widetilde{O}(2^n/ε)$ copies of an unknown $n$-qubit pure state $|ψ\rangle$, the algorithm performs only nonadaptive Pauli measurements, runs in time $\widetilde{O}(2^n/ε)$, and outputs $|\widehatψ \rangle$ with fidelity at least $1-ε$ with $|ψ\rangle$ with high probability. This is the first algorithm for pure state tomography that achieves near-optimal running time.

quant-pharXiv:2601.04444•Jan 9, 2026•0 citations

Almost Tight Sample Complexity Analysis of Quantum Identity Testing by Pauli Measurements

Nengkun Yu

This paper studies the quantum identity testing problem, a quantum analogue of distribution identity testing. The goal is to determine whether a quantum state is identical to another fixed quantum state, using as few state samples as possible. Rather than general entangled measurements, we consider the less powerful but experimentally friendly Pauli measurements. We follow the standard setting where Pauli measurements are regarded as two-outcome measurements, i.e., each$n$-qubit Pauli measurement has a one-bit outcome. We prove that for an$n$-qubit quantum system, the sample complexity of this problem is$\Theta \left({\mathrm {poly}(n)\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)$if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether two$n$-qubit quantum states,$\rho $and$\sigma $, are identical or$\epsilon $-far in trace distance using Pauli measurements, using$O\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)$copies of$\rho $and$\sigma $. Interestingly,$\mathcal {O}\left({\frac {4^{n}}{\epsilon ^{2}}}\right)$copies are not sufficient under this setting.

IEEE Transactions on Information Theory•Apr 27, 2023•3 citations

Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators

Steven T. Flammia, David Gross, Yi-Kai Liu +1 more

Intuitively, if a density operator has small rank, then it should be easier to estimate from experimental data, since in this case only a few eigenvectors need to be learned. We prove two complementary results that confirm this intuition. Firstly, we show that a low-rank density matrix can be estimated using fewer copies of the state, i.e. the sample complexity of tomography decreases with the rank. Secondly, we show that unknown low-rank states can be reconstructed from an incomplete set of measurements, using techniques from compressed sensing and matrix completion. These techniques use simple Pauli measurements, and their output can be certified without making any assumptions about the unknown state. In this paper, we present a new theoretical analysis of compressed tomography, based on the restricted isometry property for low-rank matrices. Using these tools, we obtain near-optimal error bounds for the realistic situation where the data contain noise due to finite statistics, and the density matrix is full-rank with decaying eigenvalues. We also obtain upper bounds on the sample complexity of compressed tomography, and almost-matching lower bounds on the sample complexity of any procedure using adaptive sequences of Pauli measurements. Using numerical simulations, we compare the performance of two compressed sensing estimators—the matrix Dantzig selector and the matrix Lasso—with standard maximum-likelihood estimation (MLE). We find that, given comparable experimental resources, the compressed sensing estimators consistently produce higher fidelity state reconstructions than MLE. In addition, the use of an incomplete set of measurements leads to faster classical processing with no loss of accuracy. Finally, we show how to certify the accuracy of a low-rank estimate using direct fidelity estimation, and describe a method for compressed quantum process tomography that works for processes with small Kraus rank and requires only Pauli eigenstate preparations and Pauli measurements.

arXiv:1205.2300•New Journal of Physics•Sep 27, 2012•356 citations
Pauli Measurements are the most important measurements in both theoretical and experimental aspects of quantum information science. In this paper, we explore the power of Pauli measurements in the state tomography related problems. Firstly, we show that the \textit{quantum state tomography} problem of nnn-qubit system can be accomplished with O(10nε2){\mathcal{O}}(\frac{10^n}{ε^2})O(ε210n​) copies of the unknown state using Pauli measurements. As a direct application, we studied the \textit{quantum overlapping tomography} problem introduced by Cotler and Wilczek in Ref. \cite{Cotler_2020}. We show that the sample complexity is O(10k⋅log⁡((nk)/δ))ε2)\mathcal{O}(\frac{10^k\cdot\log({{n}\choose{k}}/δ))}{ε^{2}})O(ε210k⋅log((kn​)/δ))​) for quantum overlapping tomography of kkk-qubit reduced density matrices among nnn is quantum system, where 1−δ1-δ1−δ is the confidential level, and εεε is the trace distance error. This can be achieved using Pauli measurements. Moreover, we prove that Ω(log⁡(n/δ)ε2)Ω(\frac{\log(n/δ)}{ε^{2}})Ω(ε2log(n/δ)​) copies are needed. In other words, for constant kkk, joint, highly entangled, measurements are not asymptotically more efficient than Pauli measurements.
Quantum state tomography is a fundamental problem in quantum computing. Given n copies of an unknown N -qubit state ρ∈ℂ d × d , d =2 N , the goal is to learn the state up to an accuracy ε in trace distance, say with at least constant probability 0.99. We are interested in the copy complexity, the minimum number of copies of ρ needed to fulfill the task. As current quantum devices are physically limited, Pauli measurements have attracted significant attention due to their ease of implementation. However, a large gap exists in the literature for tomography with Pauli measurements. The best-known upper bound is O ( N · 12 N /ε 2 ), and no non-trivial lower bound is known besides the general single-copy lower bound of Ω(8 N /ε 2 ), achieved by hard-to-implement structured POVMs such as MUB, SIC-POVM, and uniform POVM. We have made significant progress on this long-standing problem. We first prove a stronger upper bound of O (10 N /ε 2 ). To complement it, we also obtain a lower bound of Ω(9.118 N /ε 2 ), which holds even with adaptivity. To our knowledge, this demonstrates the first known separation between Pauli measurements and structured POVMs. The new lower bound is a consequence of a novel framework for adaptive quantum state tomography with measurement constraints. The main advantage is that we can use measurement-dependent hard instances to prove tight lower bounds for Pauli measurements, while prior lower-bound techniques for tomography only work with measurement-independent constructions. Moreover, we connect the copy complexity lower bound of tomography to the eigenvalues of the measurement information channel, which governs the measurement’s capacity to distinguish between states. To demonstrate the generality of the new framework, we obtain tight bounds for adaptive quantum state tomography with k -outcome measurements, where we recover existing results and establish new ones.
Quantum state tomography is a technique in quantum information science used to reconstruct the density matrix of an unknown quantum state, providing complete information about the quantum state. It is of significant importance in fields such as quantum computation, quantum communication, and quantum simulation. However, as the size of the quantum system increases, the number of measurement settings and sampling requirements for quantum state tomography grow exponentially with the number of qubits. This not only makes experimental design and implementation more complex, but also exacerbates the consumption of experimental resources. These limitations severely hinder the application of state tomography in large-scale quantum systems. To reduce measurement settings and improve sampling efficiency, this study proposes a state tomography method based on auxiliary systems. This method can be implemented through either entanglement between the quantum system to be measured and a quantum auxiliary system or through correlation between the quantum system and a probabilistic classical auxiliary system. Measurements on the entire joint system enable more efficient extraction of information about the quantum state to be measured. This method relies on standard quantum gate operations and requires only two measurement settings, with a total sampling complexity of O(d2)O(d^2)O(d2), significantly simplifying experimental operations and measurement processes. Additionally, this study provides two schemes for measuring purity based on the proposed circuit, one of which achieves measurement precision at the Heisenberg limit. This study validates the effectiveness of the proposed method through a detailed theoretical analysis, a series of numerical simulations, and experiments.
How many samples of a quantum state are required to learn a complete description of it? As we will see in this thesis, the fine-grained answer depends on the measurements available to the learner, but in general it is at least Ω(d^2/ϵ^2) where d is the dimension of the state and ϵ the trace distance accuracy. Optimal algorithms for this task -- known as quantum state tomography -- make use of powerful, yet highly impractical entangled measurements, where some joint measurement is performed on all copies of the state. What can be accomplished without such measurements, where one must perform measurements on individual copies of the states? \n \nIn Chapter 2 we show a relationship between the recently proposed quantum online learning framework and quantum state tomography. Specifically, we show that tomography can be accomplished using online learning algorithms in a black-box manner and O(d^4/ϵ^4) two-outcome measurements on separate copies of the state. The interpretation of this approach is that the experimentalist uses informative measurements to teach the learner by helping it make "mistakes" on measurements as early as possible. \n \nWe move on to proving lower bounds on tomography in Chapter 3. First, we review a known lower bound for entangled measurements as well as a Ω(d^3/ϵ^2) lower bound in the setting where non-entangled measurements are made non-adaptively, both due to Ref.[18]. We then derive a novel bound of Ω(d^4/ϵ^2) samples when the learner is further restricted to observing a constant number of outcomes (e.g., two-outcome measurements). This implies that the folklore "Pauli tomography" algorithm is optimal in this setting. \n \nUnderstanding the power of adaptive measurements, where measurement choices can depend on previous outcomes, is currently an open problem. In Chapter 4 we present two scenarios in which adapting on previous outcomes makes no difference to the number of samples required. In the first, the learner is limited to adapting on at most o(d^2/ϵ^2) of the previous outcomes. In the second, measurements are drawn from some set of at most exp(O(d)) measurements. In particular, this second lower bound implies that adaptivity makes no difference in the regime of efficiently implementable measurements, in the context of quantum computing. \n \nFinally, we apply the above technique to the problems of classical shadows and shadow tomography to obtain similar lower bounds. Here, one is interested only in determining the expectations of some fixed set of observables. We once again find that, for the worst-case input of observables, adaptivity makes no difference to the sample complexity when considering efficient, non-entangled measurements. As a corollary, we find a straightforward algorithm for shadow tomography is optimal in this setting.
We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given O~(2n/ε)\widetilde{O}(2^n/ε)O(2n/ε) copies of an unknown nnn-qubit pure state ∣ψ⟩|ψ\rangle∣ψ⟩, the algorithm performs only nonadaptive Pauli measurements, runs in time O~(2n/ε)\widetilde{O}(2^n/ε)O(2n/ε), and outputs ∣ψ^⟩|\widehatψ \rangle∣ψ​⟩ with fidelity at least 1−ε1-ε1−ε with ∣ψ⟩|ψ\rangle∣ψ⟩ with high probability. This is the first algorithm for pure state tomography that achieves near-optimal running time.
This paper studies the quantum identity testing problem, a quantum analogue of distribution identity testing. The goal is to determine whether a quantum state is identical to another fixed quantum state, using as few state samples as possible. Rather than general entangled measurements, we consider the less powerful but experimentally friendly Pauli measurements. We follow the standard setting where Pauli measurements are regarded as two-outcome measurements, i.e., eachnnn-qubit Pauli measurement has a one-bit outcome. We prove that for annnn-qubit quantum system, the sample complexity of this problem isΘ(poly(n)⋅4nϵ2)\Theta \left({\mathrm {poly}(n)\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)Θ(poly(n)⋅ϵ24n​)if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether twonnn-qubit quantum states,$\rho andandand\sigma ,areidenticalor, are identical or,areidenticalor\epsilon −farintracedistanceusingPaulimeasurements,using-far in trace distance using Pauli measurements, using−farintracedistanceusingPaulimeasurements,usingO\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)copiesofcopies ofcopiesof\rho andandand\sigma .Interestingly,. Interestingly,.Interestingly,\mathcal {O}\left({\frac {4^{n}}{\epsilon ^{2}}}\right)$copies are not sufficient under this setting.
Intuitively, if a density operator has small rank, then it should be easier to estimate from experimental data, since in this case only a few eigenvectors need to be learned. We prove two complementary results that confirm this intuition. Firstly, we show that a low-rank density matrix can be estimated using fewer copies of the state, i.e. the sample complexity of tomography decreases with the rank. Secondly, we show that unknown low-rank states can be reconstructed from an incomplete set of measurements, using techniques from compressed sensing and matrix completion. These techniques use simple Pauli measurements, and their output can be certified without making any assumptions about the unknown state. In this paper, we present a new theoretical analysis of compressed tomography, based on the restricted isometry property for low-rank matrices. Using these tools, we obtain near-optimal error bounds for the realistic situation where the data contain noise due to finite statistics, and the density matrix is full-rank with decaying eigenvalues. We also obtain upper bounds on the sample complexity of compressed tomography, and almost-matching lower bounds on the sample complexity of any procedure using adaptive sequences of Pauli measurements. Using numerical simulations, we compare the performance of two compressed sensing estimators—the matrix Dantzig selector and the matrix Lasso—with standard maximum-likelihood estimation (MLE). We find that, given comparable experimental resources, the compressed sensing estimators consistently produce higher fidelity state reconstructions than MLE. In addition, the use of an incomplete set of measurements leads to faster classical processing with no loss of accuracy. Finally, we show how to certify the accuracy of a low-rank estimate using direct fidelity estimation, and describe a method for compressed quantum process tomography that works for processes with small Kraus rank and requires only Pauli eigenstate preparations and Pauli measurements.