No free lunch theorems for quantum state measurements as resources in classical sampling and generative modelling

• URL: http://arxiv.org/abs/2309.13967v2
• Date: Fri, 19 Jan 2024 14:03:21 GMT
• Title: No free lunch theorems for quantum state measurements as resources in classical sampling and generative modelling
• Authors: Steven Herbert
• Abstract summary: We prove that $textitalmost all$ quantum states, when sampled according to the Haar measure over the unitary group, have the following property. If copies of the state are measured to provide latent random variables, then any alternative state whose measurements can generate the same set of target distributions will do so with the same overall cost.
• Score: 0.29008108937701327
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We prove that $\textit{almost all}$ quantum states, when sampled according to the Haar measure over the unitary group, have the following property: if copies of the state are measured to provide latent random variables which are taken as an input in a classical generative model or sampling algorithm, then any alternative state whose measurements can generate the same set of target distributions will do so with the same overall cost. Here, we define the overall cost as the aggregate computational complexity of sampling from all possible distributions that can be prepared from the given input distribution. Our result holds for any length of input and output bitstring and when a uniformly random bitstring of any length is optionally provided as an additional resource. As it is easy to construct scenarios where a pair of alternative candidate states are such that classical simulation of the preparation thereof is easy in one case and hard in the other, the result can be viewed as decoupling how hard it is to obtain a latent random variable, and how useful it is as a resource in classical sampling and generative modelling.

Related papers

• Optimal Fidelity Estimation from Binary Measurements for Discrete and Continuous Variable Systems [6.253919624802852]
  In continuous variable (CV) systems, we utilise the Wigner function, which can be measured via displaced parity measurements. For target states of particular interest, such as Fock and Gaussian states, we find that this sample complexity is characterised by the $L1$-norm of the Wigner function. In a general black box model, we prove that, for any target state, the optimal sample complexity for fidelity estimation is characterised by the smoothed $L1$-norm of the target state.
  arXiv  Detail & Related papers  (2024-09-06T11:07:55Z)
• Testing properties of distributions in the streaming model [0.0]
  We study distribution testing in the standard access model and the conditional access model. The goal is to test the properties of distribution using an optimal number of samples subject to a memory constraint.
  arXiv  Detail & Related papers  (2023-09-06T10:53:29Z)
• Conformal Language Modeling [61.94417935386489]
  We propose a novel approach to conformal prediction for generative language models (LMs) Standard conformal prediction produces prediction sets with rigorous, statistical guarantees. We demonstrate the promise of our approach on multiple tasks in open-domain question answering, text summarization, and radiology report generation.
  arXiv  Detail & Related papers  (2023-06-16T21:55:08Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Predicting Out-of-Domain Generalization with Neighborhood Invariance [59.05399533508682]
  We propose a measure of a classifier's output invariance in a local transformation neighborhood. Our measure is simple to calculate, does not depend on the test point's true label, and can be applied even in out-of-domain (OOD) settings. In experiments on benchmarks in image classification, sentiment analysis, and natural language inference, we demonstrate a strong and robust correlation between our measure and actual OOD generalization.
  arXiv  Detail & Related papers  (2022-07-05T14:55:16Z)
• Direct sampling of projected entangled-pair states [0.0]
  Variational Monte Carlo studies employing projected entangled-pair states (PEPS) have recently shown that they can provide answers on long-standing questions. We propose a sampling algorithm that generates independent samples from a PEPS, bypassing all problems related to finite autocorrelation times.
  arXiv  Detail & Related papers  (2021-09-15T15:09:20Z)
• Deterministic Gibbs Sampling via Ordinary Differential Equations [77.42706423573573]
  This paper presents a general construction of deterministic measure-preserving dynamics using autonomous ODEs and tools from differential geometry. We show how Hybrid Monte Carlo and other deterministic samplers follow as special cases of our theory.
  arXiv  Detail & Related papers  (2021-06-18T15:36:09Z)
• Uncorrelated problem-specific samples of quantum states from zero-mean Wishart distributions [4.289102530380288]
  We present a two-step algorithm for sampling from the quantum state space. We establish the explicit form of the induced Wishart distribution for quantum states. We demonstrate that this sampling algorithm is very efficient for one-qubit and two-qubit states, and reasonably efficient for three-qubit states.
  arXiv  Detail & Related papers  (2021-06-16T03:06:41Z)
• Probabilistic Kolmogorov-Arnold Network [1.4732811715354455]
  The present paper proposes a method for estimating probability distributions of the outputs in the case of aleatoric uncertainty. The suggested approach covers input-dependent probability distributions of the outputs, as well as the variation of the distribution type with the inputs. Although the method is applicable to any regression model, the present paper combines it with KANs, since the specific structure of KANs leads to computationally-efficient models' construction.
  arXiv  Detail & Related papers  (2021-04-04T23:49:15Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)

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.