Dimension Independent and Computationally Efficient Shadow Tomography

• URL: http://arxiv.org/abs/2411.01420v1
• Date: Sun, 03 Nov 2024 03:07:35 GMT
• Title: Dimension Independent and Computationally Efficient Shadow Tomography
• Authors: Pulkit Sinha,
• Abstract summary: We describe a new shadow tomography algorithm that uses $n=Theta(sqrtmlog m/epsilon2)$ samples, for $m$ measurements and additive error $epsilon$. This stands in contrast to all previously known algorithms that improve upon the naive approach.
• Score: 0.0
• License:
• Abstract: We describe a new shadow tomography algorithm that uses $n=\Theta(\sqrt{m}\log m/\epsilon^2)$ samples, for $m$ measurements and additive error $\epsilon$, which is independent of the dimension of the quantum state being learned. This stands in contrast to all previously known algorithms that improve upon the naive approach. The sample complexity also has optimal dependence on $\epsilon$. Additionally, this algorithm is efficient in various aspects, including quantum memory usage (possibly even $O(1)$), gate complexity, classical computation, and robustness to qubit measurement noise. It can also be implemented as a read-once quantum circuit with low quantum memory usage, i.e., it will hold only one copy of $\rho$ in memory, and discard it before asking for a new one, with the additional memory needed being $O(m\log n)$. Our approach builds on the idea of using noisy measurements, but instead of focusing on gentleness in trace distance, we focus on the \textit{gentleness in shadows}, i.e., we show that the noisy measurements do not significantly perturb the expected values.

Related papers

• Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
  Estimating the trace of powers of identical $k$ density matrices is a crucial subroutine for many applications. Inspired by the Newton-Girard method, we developed an algorithm that uses only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates.
  arXiv  Detail & Related papers  (2024-08-01T06:23:52Z)
• Weak Schur sampling with logarithmic quantum memory [0.0]
  We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group.
  arXiv  Detail & Related papers  (2023-09-21T10:02:46Z)
• 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)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
  Shadow tomography for quantum states provides a sample efficient approach for predicting the properties of quantum systems. We develop an online shadow tomography procedure that solves this problem with high success probability.
  arXiv  Detail & Related papers  (2022-09-07T09:08:58Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• 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)
• Exponential separations between learning with and without quantum memory [17.763817187554096]
  We study the power of quantum memory for learning properties of quantum systems and dynamics. Many state-of-the-art learning algorithms require access to an additional external quantum memory. We show that this trade-off is inherent in a wide range of learning problems.
  arXiv  Detail & Related papers  (2021-11-10T19:03:49Z)
• 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.