Sample-optimal single-copy quantum state tomography via shallow depth measurements

• URL: http://arxiv.org/abs/2509.12703v1
• Date: Tue, 16 Sep 2025 05:54:01 GMT
• Title: Sample-optimal single-copy quantum state tomography via shallow depth measurements
• Authors: Gyungmin Cho, Dohun Kim,
• Abstract summary: We make two contributions by employing circuits with depth $mathcalO!left(fracd3epsilon2right)$ on an $n$-qubit system.<n>First, QST for rank-$r$ $d$-dimensional state $$ can be achieved with sample complexity $mathcalO!left(tfracdr2 ln depsilon2right)$.<n>Second, for the general case of $r = d$, we can remove the $ln
• Score: 0.42970700836450487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum state tomography (QST) is one of the fundamental problems in quantum information. Among various metrics, sample complexity is widely used to evaluate QST algorithms. While multi-copy measurements are known to achieve optimal sample complexity, they are challenging to implement on near-term quantum devices. In practice, single-copy measurements with shallow-depth circuits are more feasible. Although a near-optimal QST algorithm under single-qubit measurements has recently been proposed, its sample complexity does not match the known lower bound for single-copy measurements. Here, we make two contributions by employing circuits with depth $\mathcal{O}(\log n)$ on an $n$-qubit system. First, QST for rank-$r$ $d$-dimensional state $\rho$ can be achieved with sample complexity $\mathcal{O}\!\left(\tfrac{dr^2 \ln d}{\epsilon^2}\right)$ to error $\epsilon$ in trace distance, which is near-optimal up to a $\ln d$ factor compared to the known lower bound $\Omega\left(\frac{dr^2}{\epsilon^2}\right)$. Second, for the general case of $r = d$, we can remove the $\ln d$ factor, yielding an optimal sample complexity of $\mathcal{O}\!\left(\frac{d^3}{\epsilon^2}\right)$.

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)
• Optimizing sparse quantum state preparation with measurement and feedforward [0.3222802562733787]
  Quantum state preparation (QSP) is a key component in many quantum algorithms.<n>We present two SQSP algorithms that reduce circuit depth to a few qubits.
  arXiv  Detail & Related papers  (2025-08-29T06:14:28Z)
• Fast quantum measurement tomography with dimension-optimal error bounds [0.6144680854063935]
  We present a two-step protocol for quantum measurement tomography that is light on classical co-processing cost.<n>We show that the protocol requires $mathcalO(d3 L ln(d)/epsilon2)$ samples to achieve error $epsilon$ in worst-case distance.<n>We also complement our findings with empirical performance studies carried out on a noisy superconducting quantum computer with flux-tunable transmon qubits.
  arXiv  Detail & Related papers  (2025-07-06T18:35:07Z)
• Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer [7.319050391449301]
  Trace distance and infidelity, as basic measures of the closeness of quantum states, are commonly used in quantum state discrimination, certification, and tomography. We present a quantum algorithm that estimates the trace distance and square root fidelity between pure states to within additive error $varepsilon$, given sample access to their identical copies.
  arXiv  Detail & Related papers  (2024-10-28T16:48:21Z)
• 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)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

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.