Related papers: Pauli Measurements Are Near-Optimal for Single-Qubit Tomography

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

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.