Pauli Measurements Are Near-Optimal for Single-Qubit Tomography

• URL: http://arxiv.org/abs/2507.22001v1
• Date: Tue, 29 Jul 2025 16:50:19 GMT
• Title: Pauli Measurements Are Near-Optimal for Single-Qubit Tomography
• Authors: Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu,
• Abstract summary: We show that at least $Omegaleft(frac10NsqrtN varepsilon2right)$ copies are required to learn an $N$-qubit state $rhoinmathbbCdtimes d,d=2N$ to within $varepsilon$ trace distance.
• Score: 34.83118849281207
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide the first non-trivial lower bounds for single-qubit tomography algorithms and show that at least ${\Omega}\left(\frac{10^N}{\sqrt{N} \varepsilon^2}\right)$ copies are required to learn an $N$-qubit state $\rho\in\mathbb{C}^{d\times d},d=2^N$ to within $\varepsilon$ trace distance. Pauli measurements, the most commonly used single-qubit measurement scheme, have recently been shown to require at most $O\left(\frac{10^N}{\varepsilon^2}\right)$ copies for this problem. Combining these results, we nearly settle the long-standing question of the complexity of single-qubit tomography.

Related papers

• Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach [2.956729394666618]
  We study the sample complexity of shadow tomography in the high-precision regime.<n>We use possibly adaptive measurements that act on $O(mathrmpolylog(d))$ number of copies of $$ at a time.
  arXiv  Detail & Related papers  (2026-02-04T19:00:00Z)
• Pauli Measurements Are Near-Optimal for Pure State Tomography [2.207442386128469]
  We give an algorithm for pure state tomography with near-optimal copy complexity using single-qubit measurements.<n>Specifically, given $widetildeO (2n/)$ copies of an unknown pure $n$-qubit state $lvertrangle$, the algorithm performs only textitnonadaptive Pauli measurements.
  arXiv  Detail & Related papers  (2026-01-07T23:16:37Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• The debiased Keyl's algorithm: a new unbiased estimator for full state tomography [1.4302622916198997]
  We present the debiased Keyl's algorithm, the first estimator for full state tomography which is both unbiased and sample-optimal.<n>We show that $n = O(rd/varepsilon2)$ copies are sufficient to learn a rank-$r$ mixed state to trace distance error $varepsilon$, which is optimal.<n>We further show that $n = O(rd/varepsilon2)$ copies are sufficient to learn to error $varepsilon$ in the more challenging Bures distance, which is also optimal.
  arXiv  Detail & Related papers  (2025-10-09T05:07:12Z)
• Optimal lower bounds for quantum state tomography [0.9969485010222057]
  We show that $n = Omega(rd/varepsilon2)$ copies are necessary to learn a rank $r$ mixed state $rho in mathbbCd times d$ up to error $varepsilon$ in trace distance.<n>A key technical ingredient in our proof, which may be of independent interest, is a reduction which converts any algorithm for projector tomography which learns to error $varepsilon$ in trace distance to an algorithm which learns to error $O(varepsilon)$ in the more stringent Bures
  arXiv  Detail & Related papers  (2025-10-09T02:36:48Z)
• Pauli measurements are not optimal for single-copy tomography [34.83118849281207]
  We prove a stronger upper bound of $O(frac10Nepsilon2)$ and a lower bound of $Omega(frac9.118Nepsilon2)$.<n>This demonstrates the first known separation between Pauli measurements and structured POVMs.
  arXiv  Detail & Related papers  (2025-02-25T13:03:45Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26:19Z)
• Testing multipartite productness is easier than testing bipartite productness [0.0]
  We show that $Omega(n / log n)$ copies are required (for fixed $epsilon leq frac12$) We discuss implications for testing graph states and computing the generalised geometric measure of entanglement.
  arXiv  Detail & Related papers  (2024-06-24T17:36:57Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$<n>We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Learning quantum graph states with product measurements [22.463154358632472]
  We consider the problem of learning $N$ identical copies of an unknown $n$-qubit quantum graph state with product measurements. We detail an explicit algorithm that uses product measurements on multiple identical copies of such graph states to learn them.
  arXiv  Detail & Related papers  (2022-05-13T02:55:21Z)
• Tight Bounds for Quantum State Certification with Incoherent Measurements [18.566266990940374]
  When $sigma$ is the maximally mixed state $frac1d I_d$, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of $rho$ at a time.
  arXiv  Detail & Related papers  (2022-04-14T17:59:31Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Improved quantum data analysis [1.8416014644193066]
  We give a quantum "Threshold Search" algorithm that requires only $O(log2 m)/epsilon2)$ samples of a $d$-dimensional state. We also give an alternative Hypothesis Selection method using $tildeO((log3 m)/epsilon2)$ samples.
  arXiv  Detail & Related papers  (2020-11-22T01:22:37Z)
• Sample efficient tomography via Pauli Measurements [11.98034899127065]
  We explore the power of Pauli measurements in the state tomography related problems. We show that the textitquantum state tomography problem of $n$-qubit system can be accomplished with $mathcalO(frac10nepsilon2)$ copies of the unknown state using Pauli measurements.
  arXiv  Detail & Related papers  (2020-09-10T00:04:44Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

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.