Quantum Information and Quantum Computation
Open Problem Zoo
Random Unsolved Solved

Sample complexity of low-rank tomography with Pauli measurements

Unsolved ID op_df689759a5203415 Last edited 22 September 2026
Edit
Field
Topic

Problem

How many copies of an unknown low-rank \(N\)-qubit state does tomography with Pauli measurements need?

Let \(d=2^N\) and let \(\rho\) be a density operator on \((\mathbb{C}^2)^{\otimes N}\) with \(\operatorname{rank}(\rho)\leq r\), where \(1\leq r\leq d\) is known to the algorithm. A Pauli measurement is labeled by a string \(s\in\{X,Y,Z\}^N\). It measures every qubit \(j\) in the eigenbasis of the Pauli operator \(\sigma_{s_j}\) and records all \(N\) outcomes \(x\in\{-1,1\}^N\), so its POVM elements are

\begin{equation} M^{s}_{x}=\bigotimes_{j=1}^{N}\frac{I+x_j\,\sigma_{s_j}}{2}, \qquad \sigma_X=X,\quad\sigma_Y=Y,\quad\sigma_Z=Z. \tag{1} \end{equation}

An algorithm consumes one fresh copy of \(\rho\) per measurement, and the string \(s\) used on a copy may depend on the outcomes recorded on all earlier copies. After \(n\) copies it outputs a density operator \(\hat\rho\). It succeeds on \(\rho\) if

\begin{equation} \tfrac12\lVert\hat\rho-\rho\rVert_1\leq\epsilon \tag{2} \end{equation}

holds with probability at least \(2/3\). Let \(n_{\mathrm{P}}(N,r,\epsilon)\) be the least \(n\) for which some algorithm using only measurements of the form (1) satisfies (2) on every state of rank at most \(r\). The success probability is fixed at \(2/3\). Comparisons below with bounds stated at other constant success probabilities allow a constant rescaling of \(\epsilon\).

Determine how \(n_{\mathrm{P}}(N,r,\epsilon)\) grows with \(N\) and \(r\). In exponent form, fix a sufficiently small constant \(\epsilon>0\) and for \(0\leq\alpha\leq1\) set

\begin{equation} c(\alpha):=\lim_{N\to\infty}\frac{1}{N}\log_2 n_{\mathrm{P}}\bigl(N,\lceil2^{\alpha N}\rceil,\epsilon\bigr), \tag{3} \end{equation}

with the limit inferior and the limit superior taken separately if the limit does not exist. The endpoints are known, \(c(0)=1\) and \(c(1)=\log_2 10\). For \(0<\alpha<1\) the known bounds are

\begin{equation} \max\{1+\alpha,\ \alpha\log_2 10\}\leq c(\alpha)\leq\min\{\log_2 3+2\alpha,\ \log_2 10\}, \tag{4} \end{equation}

and the lower bound improves to \(\max\{1+2\alpha,\alpha\log_2 10\}\) for nonadaptive algorithms, those whose strings \(s\) are all fixed before the first copy is measured. Determine \(c(\alpha)\) for every \(\alpha\in(0,1)\), both for the adaptive algorithms defined above and for nonadaptive algorithms. Upper and lower bounds on \(n_{\mathrm{P}}(N,r,\epsilon)\) that agree up to a factor polynomial in \(N\) for every \(r\) would settle the question.

Source

Acharya, Dharmavarapu, Liu, and Yu, in Section 1.2 of the arXiv version of their STOC 2025 paper, name the extension of Pauli-measurement tomography to low-rank states as a direction for future work and collect the bounds available for intermediate rank [ADLY25]. The exponent (3) and the bounds (4) are formulated here from those bounds together with the pure-state result of Grewal, Gupta, He, Sen, and Singhal [GGH+26] and the full-rank lower bound of Acharya, Dharmavarapu, Liu, and Yu [ADLY25b]. No source states the question in this form.

Progress

Reports do not certify correctness or automatically change the problem's status. Progress policy.

  • Full rank. With every string \(s\) fixed in advance and each of the \(3^N\) strings applied to an equal share of the copies, \(n=O(10^N\log(1/\delta)/\epsilon^2)\) copies suffice to reach (2) with probability \(1-\delta\) for every state [Yu20], [ADLY25]. Every adaptive scheme built from arbitrary single-qubit measurements, of which (1) is a special case, needs \(n=\Omega(10^N/(\sqrt N\,\epsilon^2))\) copies [ADLY25b]. Hence \(c(1)=\log_2 10\), and the full-rank gap is the factor \(\sqrt N\). The lower bound appears in a preprint that has not been peer reviewed.

  • Pure states. Given \(\tilde O(2^N\log(1/\delta)/\epsilon)\) copies of a pure state, Pauli measurements with strings drawn at random in advance return a pure estimate with fidelity at least \(1-\epsilon\) with probability \(1-\delta\) (Theorem 1 of [GGH+26]). For pure \(\rho\) and \(\hat\rho\) the trace distance equals \(\sqrt{1-F}\), so \(\tilde O(2^N/\epsilon^2)\) copies achieve (2). Any scheme, even one measuring all copies jointly, needs \(\tilde\Omega(dr/\epsilon^2)\) copies for states of rank \(r\), where the tilde hides a logarithmic factor [HHJ+17]. Hence \(c(0)=1\).

  • Intermediate rank, upper bounds. Projected least squares on the outcomes of all \(3^N\) Pauli measurements, each applied to an equal share of the copies, reaches (2) with probability \(1-\delta\) once \(n\geq 43\,g(d)\,r^2\epsilon^{-2}\log(d/\delta)\), with \(g(d)\simeq d^{1.6}\) for Pauli basis measurements (Theorem 1 of [GKKT20]). Section 1.2 of [ADLY25] restates this as \(n=O(N\cdot 3^N r^2/\epsilon^2)\). Together with the rank-independent bound \(O(10^N/\epsilon^2)\) this gives the upper bound in (4). The projected least squares bound is not tight at either endpoint. It gives \(N\cdot 3^N\) against \(2^N\) at \(r=1\) and \(N\cdot 12^N\) against \(10^N\) at \(r=d\).

  • Intermediate rank, lower bounds. Any nonadaptive single-copy scheme needs \(\Omega(r^2 d/\epsilon^2)\) copies for states of rank \(r\) (Theorem 4.11 of [LN25]), which gives the term \(1+2\alpha\) for nonadaptive algorithms. For adaptive single-copy schemes the rank-\(r\) rate is unknown, since the adaptive bound \(\Omega(d^3/\epsilon^2)\) of [CHL+23] covers full rank only, a gap recorded in Section 1.2 of [ADLY25]. The term \(1+\alpha\) in (4) therefore rests on the bound \(\tilde\Omega(dr/\epsilon^2)\) for measurements entangled across copies [HHJ+17]. The term \(\alpha\log_2 10\) follows from the full-rank bound of [ADLY25b] by padding. It is a corollary drawn here and is not stated in that paper. For \(r\geq2\) let \(m=\lfloor\log_2 r\rfloor\) and embed an arbitrary \(m\)-qubit state \(\tau\) as \(\tau\otimes|0\rangle\langle0|^{\otimes(N-m)}\), a state of rank at most \(r\). One copy of \(\tau\) simulates one measurement (1) of the embedded state, since each padded qubit returns \(+1\) when measured in the \(Z\) basis and an independent fair coin in the \(X\) or \(Y\) basis, so the transcript and every adaptive choice made from it have the correct distribution. Tracing the padded qubits out of the estimate does not increase the trace distance. Hence \(n_{\mathrm{P}}(N,r,\epsilon)\geq n_{\mathrm{P}}(m,2^m,\epsilon)\). Theorem 1.1 of [ADLY25b] is stated for the trace norm without the factor \(\tfrac12\) and for success probability \(0.9\). An algorithm for (2) is therefore run a constant number of times and an estimate within \(2\epsilon\) of a majority of the others is selected, which raises the success probability to \(0.9\) at the price of error \(3\epsilon\), or \(6\epsilon\) in the convention of that theorem. The hard instances of the theorem are perturbations of the maximally mixed state that must remain states, so the corollary is claimed only for \(\epsilon\) below a universal constant. For such \(\epsilon\) it gives \(n_{\mathrm{P}}(N,r,\epsilon)=\Omega(10^m/(\sqrt m\,\epsilon^2))\), and \(10^m\geq r^{\log_2 10}/10\) yields \(c(\alpha)\geq\alpha\log_2 10\). This exceeds \(1+\alpha\) for \(\alpha>1/(\log_2 10-1)\approx0.431\) and \(1+2\alpha\) for \(\alpha>1/(\log_2 10-2)\approx0.756\). No other lower bound specific to Pauli measurements depends on \(r\).

  • Two-outcome Pauli measurements. When each copy is used to measure one Pauli observable, so that only the product of the outcomes in (1) is kept, \(O(r^2d^2\log d/\epsilon^2)\) copies suffice (Theorem 2 of [FGLE12]), \(\Omega(r^2d^2/\log d)\) copies are necessary for fixed \(0<\epsilon<1-r/d\), with a constant that depends on \(\epsilon\), even for adaptive sequences of observables (Theorem 6 of [FGLE12]), and \(\Omega(r^2d^2/\epsilon^2)\) copies are necessary for \(\epsilon<1/8\) and nonadaptive measurements with a constant number of outcomes (Theorem 4.12 of [LN25]). Thus, for fixed \(\alpha<1\) and sufficiently small fixed \(\epsilon\), both adaptive and nonadaptive two-outcome Pauli tomography need \(\tilde\Theta(r^2 4^N)\) copies, and for nonadaptive schemes the \(\epsilon^{-2}\) dependence is also tight up to logarithmic factors. At full rank, Corollary 4.7 of [LN25] gives \(\Omega(d^4/\epsilon^2)\) for nonadaptive two-outcome measurements, which is \(16^N\) against \(10^N\) for nonadaptive measurements of the form (1). This corollary does not assert the same lower bound for adaptive measurements. The upper bound transfers to (1). The lower bounds do not.

Comment

The open range is \(0<\alpha<1\). There is evidence that neither side of (4) is tight. The projected least squares bound misses the truth by an exponential factor at both endpoints. The lower bound \(1+2\alpha\) holds for every nonadaptive single-copy scheme, whereas at \(\alpha=1\) Pauli measurements already lose the factor \((10/8)^N\) against the best single-copy scheme, and the padding bound \(\alpha\log_2 10\) treats the \(N-m\) padded qubits as free. Whether \(c\) is convex or piecewise linear is not known. To give concrete numbers, at \(r=\sqrt d\) the nonadaptive lower bound is \(4^N/\epsilon^2\) copies, the upper bound is \(N\cdot 6^N/\epsilon^2\) copies, and the adaptive lower bound is \(10^{N/2}/(\sqrt N\,\epsilon^2)\) copies.

Nearby questions remain open as well. In the adaptive model the lower bound for \(\alpha<0.431\) is only \(1+\alpha\), because no adaptive single-copy lower bound is known beyond full rank. At full rank the factor \(\sqrt N\) between \(10^N/\epsilon^2\) and \(10^N/(\sqrt N\,\epsilon^2)\) remains, and [ADLY25b] asks whether \(10^N\) is the sample complexity of Pauli measurements. The same question with infidelity in place of (2) is listed with the low-rank extension in [ADLY25]. The two-outcome model of the last Progress item is settled up to logarithmic factors at fixed \(\epsilon\) and is a different problem from (1).

References

[ADLY25]
J. Acharya, A. Dharmavarapu, Y. Liu, and N. Yu, “Pauli measurements are not optimal for single-copy tomography,” in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), 718–729 (2025).DOIarXiv
[ADLY25b]
J. Acharya, A. Dharmavarapu, Y. Liu, and N. Yu, “Pauli measurements are near-optimal for single-qubit tomography,” arXiv preprint (2025).DOIarXiv
[Yu20]
N. Yu, “Sample efficient tomography via Pauli measurements,” arXiv preprint (2020).DOIarXiv
[GKKT20]
M. Guţă, J. Kahn, R. Kueng, and J. A. Tropp, “Fast state tomography with optimal error bounds,” Journal of Physics A: Mathematical and Theoretical 53, 204001 (2020).DOIarXiv
[GGH+26]
S. Grewal, M. Gupta, W. He, A. Sen, and M. Singhal, “Nearly time-optimal pure state tomography with Pauli measurements,” arXiv preprint (2026).DOIarXiv
[LN25]
A. Lowe and A. Nayak, “Lower bounds for learning quantum states with single-copy measurements,” ACM Transactions on Computation Theory 17(1), Article 7 (2025).DOIarXiv
[HHJ+17]
J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, “Sample-optimal tomography of quantum states,” IEEE Transactions on Information Theory 63(9), 5628–5641 (2017).DOIarXiv
[CHL+23]
S. Chen, B. Huang, J. Li, A. Liu, and M. Sellke, “When does adaptivity help for quantum state learning?,” in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 391–404 (2023).DOIarXiv
[FGLE12]
S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert, “Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators,” New Journal of Physics 14, 095022 (2012).DOIarXiv

Contributors

  • Haifei WangCentre for Quantum Technologies, National University of Singapore

Cite this problem

Please also cite the primary sources listed under References. Cite this page for the statement, status, and stable identifier.

BibTeX

@incollection{qiqcop_op_df689759a5203415,
  title = {Sample complexity of low-rank tomography with Pauli measurements},
  booktitle = {Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo)},
  year = {2026},
  howpublished = {\url{https://qiqc-op.com/problem/op_df689759a5203415/}},
  note = {Stable ID op_df689759a5203415; status: Unsolved; accessed 2026-09-27}
}

Plain text

“Sample complexity of low-rank tomography with Pauli measurements,” Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo), https://qiqc-op.com/problem/op_df689759a5203415/, ID op_df689759a5203415, accessed 2026-09-27.

Share this problem

Permanent link

Identifiers

op_df689759a5203415
01M2JMFAPYEDSSTG9R7CWHJGQ4