Triply efficient shadow tomography

• URL: http://arxiv.org/abs/2404.19211v1
• Date: Tue, 30 Apr 2024 02:22:52 GMT
• Title: Triply efficient shadow tomography
• Authors: Robbie King, David Gosset, Robin Kothari, Ryan Babbush,
• Abstract summary: Given copies of a quantum state $rho$, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables. We describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements. We also give a triply efficient scheme for the set of all $n$-qubit Pauli observables.
• Score: 1.587441214168911
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given copies of a quantum state $\rho$, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision $\epsilon$. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of $\rho$ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random single-copy Clifford measurements can be understood as arising from fractional colorings of a graph $G$ that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of $G$ with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all $n$-qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample-efficient schemes are provably impossible using only single-copy measurements. Finally, we give a shadow tomography protocol that compresses an $n$-qubit quantum state into a $\text{poly}(n)$-sized classical representation, from which one can extract the expected value of any of the $4^n$ Pauli observables in $\text{poly}(n)$ time, up to a small constant error.

Related papers

• Real classical shadows [0.0]
  We study the case where $mathcalU$ corresponds to either local or global Clifford gates, and $mathcalW$ consists of real-valued vectors. Our results show that for various situations of interest, this real'' classical shadow protocol improves the sample complexity over the standard scheme.
  arXiv  Detail & Related papers  (2024-10-30T22:15:39Z)
• Optimal high-precision shadow estimation [22.01044188849049]
  Formally we give a protocol that measures $O(log(m)/epsilon2)$ copies of an unknown mixed state $rhoinmathbbCdtimes d$. We show via dimensionality reduction that we can rescale $epsilon$ and $d$ to reduce to the regime where $epsilon le O(d-1/2)$.
  arXiv  Detail & Related papers  (2024-07-18T19:42:49Z)
• An optimal tradeoff between entanglement and copy complexity for state tomography [24.737530909081915]
  We study tomography in the natural setting where one can make measurements of $t$ copies at a time. This is the first smooth entanglement-copy protocol known for any quantum learning task. A key insight is to use SchurilonWeyl sampling not to estimate the spectrum of $rho$, but to estimate the deviation of $rho$ from the maximally mixed state.
  arXiv  Detail & Related papers  (2024-02-26T07:18:57Z)
• Sampling and Uniqueness Sets in Graphon Signal Processing [136.68956350251418]
  We study the properties of sampling sets on families of large graphs by leveraging the theory of graphons and graph limits. We exploit the convergence results to provide an algorithm that obtains approximately close to optimal sampling sets.
  arXiv  Detail & Related papers  (2024-01-11T22:31:48Z)
• Object Recognition as Next Token Prediction [99.40793702627396]
  We present an approach to pose object recognition as next token prediction. The idea is to apply a language decoder that auto-regressively predicts the text tokens from image embeddings to form labels.
  arXiv  Detail & Related papers  (2023-12-04T18:58:40Z)
• Efficient Local Classical Shadow Tomography with Number Conservation [0.0]
  Shadow tomography aims to build a classical description of a quantum state from a sequence of simple random measurements. We propose and analyze a new local shadow protocol adapted to systems with fundamental number conservation laws, such as ultracold atoms.
  arXiv  Detail & Related papers  (2023-11-15T19:00:01Z)
• On the Equivalence of Graph Convolution and Mixup [70.0121263465133]
  This paper investigates the relationship between graph convolution and Mixup techniques. Under two mild conditions, graph convolution can be viewed as a specialized form of Mixup. We establish this equivalence mathematically by demonstrating that graph convolution networks (GCN) and simplified graph convolution (SGC) can be expressed as a form of Mixup.
  arXiv  Detail & Related papers  (2023-09-29T23:09:54Z)
• Lower bounds for learning quantum states with single-copy measurements [3.2590610391507444]
  We study the problems of quantum tomography and shadow tomography using measurements performed on individual copies of an unknown $d$-dimensional state. In particular, this rigorously establishes the optimality of the folklore Pauli tomography" algorithm in terms of its complexity.
  arXiv  Detail & Related papers  (2022-07-29T02:26:08Z)
• 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)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  We propose a framework to generate adversarial examples in one of the most challenging black-box settings. Our framework is based on the observation that the decision boundary of deep networks usually has a small mean curvature in the vicinity of data samples.
  arXiv  Detail & Related papers  (2020-03-13T20:03:01Z)

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.