Related papers: Free Fermion Distributions Are Hard to Learn

Free Fermion Distributions Are Hard to Learn

URL: http://arxiv.org/abs/2306.04731v2
Date: Mon, 3 Jun 2024 13:28:19 GMT
Title: Free Fermion Distributions Are Hard to Learn
Authors: Alexander Nietner,
Abstract summary: We establish the hardness of this task in the particle number non-preserving case. We give an information theoretical hardness result for the general task of learning from expectation values. In particular, we give a computational hardness result based on the assumption for learning the probability density function.
Score: 55.2480439325792
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Free fermions are some of the best studied quantum systems. However, little is known about the complexity of learning free-fermion distributions. In this work we establish the hardness of this task in the particle number non-preserving case. In particular, we give an information theoretical hardness result for the general task of learning from expectation values and, in the more general case when the algorithm is given access to samples, we give a computational hardness result based on the LPN assumption for learning the probability density function.

Related papers

Bounds and guarantees for learning and entanglement [0.0]
Information theory provides tools to predict the performance of a learning algorithm on a given dataset. This work first extends this relationship by demonstrating that a small conditional entropy is also sufficient for successful learning. This connection between information theory and learning suggests that we might similarly apply quantum information theory to characterize learning tasks involving quantum systems.
arXiv Detail & Related papers (2024-04-10T18:09:22Z)
Entanglement capacity of fermionic Gaussian states [3.8265321702445267]
We study the capacity of entanglement as an alternative to entanglement entropies. We derive the exact entanglement and quantum formulas of average capacity of two different cases.
arXiv Detail & Related papers (2023-02-04T19:53:51Z)
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)
A super-polynomial quantum-classical separation for density modelling [9.980327191634071]
We show that fault-tolerant quantum computers can offer a super-polynomial advantage over classical learning algorithms. We also show that any weak pseudo-random function can be used to construct a classically hard density modelling problem.
arXiv Detail & Related papers (2022-10-26T18:00:03Z)
Phase Diagram Detection via Gaussian Fitting of Number Probability Distribution [0.0]
We investigate the number probability density function that characterizes sub-portions of a quantum many-body system with globally conserved number of particles. We put forward a linear fitting protocol capable of mapping out the ground-state phase diagram of the rich one-dimensional extended Bose-Hubbard model.
arXiv Detail & Related papers (2022-07-04T15:15:01Z)
Learnability of the output distributions of local quantum circuits [53.17490581210575]
We investigate, within two different oracle models, the learnability of quantum circuit Born machines. We first show a negative result, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable. We show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable.
arXiv Detail & Related papers (2021-10-11T18:00:20Z)
Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of Partially Observable Decision Processes (POMDPs) We present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works.
arXiv Detail & Related papers (2020-06-22T17:58:54Z)
Sample-efficient learning of quantum many-body systems [17.396274240172122]
We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs state. We give the first sample-efficient algorithm for the quantum Hamiltonian learning problem.
arXiv Detail & Related papers (2020-04-15T18:01:59Z)
On estimating the entropy of shallow circuit outputs [49.1574468325115]
Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
arXiv Detail & Related papers (2020-02-27T15:32:08Z)
Statistical Limits of Supervised Quantum Learning [90.0289160657379]
We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning cannot achieve polylogarithmic runtimes in the input dimension. We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most speedups over efficient classical algorithms.
arXiv Detail & Related papers (2020-01-28T17:35:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.