A single $T$-gate makes distribution learning hard
- URL: http://arxiv.org/abs/2207.03140v1
- Date: Thu, 7 Jul 2022 08:04:15 GMT
- Title: A single $T$-gate makes distribution learning hard
- Authors: Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp,
Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Eisert, Ryan Sweke
- Abstract summary: This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
- Score: 56.045224655472865
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The task of learning a probability distribution from samples is ubiquitous
across the natural sciences. The output distributions of local quantum circuits
form a particularly interesting class of distributions, of key importance both
to quantum advantage proposals and a variety of quantum machine learning
algorithms. In this work, we provide an extensive characterization of the
learnability of the output distributions of local quantum circuits. Our first
result yields insight into the relationship between the efficient learnability
and the efficient simulatability of these distributions. Specifically, we prove
that the density modelling problem associated with Clifford circuits can be
efficiently solved, while for depth $d=n^{\Omega(1)}$ circuits the injection of
a single $T$-gate into the circuit renders this problem hard. This result shows
that efficient simulatability does not imply efficient learnability. Our second
set of results provides insight into the potential and limitations of quantum
generative modelling algorithms. We first show that the generative modelling
problem associated with depth $d=n^{\Omega(1)}$ local quantum circuits is hard
for any learning algorithm, classical or quantum. As a consequence, one cannot
use a quantum algorithm to gain a practical advantage for this task. We then
show that, for a wide variety of the most practically relevant learning
algorithms -- including hybrid-quantum classical algorithms -- even the
generative modelling problem associated with depth $d=\omega(\log(n))$ Clifford
circuits is hard. This result places limitations on the applicability of
near-term hybrid quantum-classical generative modelling algorithms.
Related papers
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties?
We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.
We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
arXiv Detail & Related papers (2024-08-22T08:21:28Z) - On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
We show that getting $1/textpoly(n)$ peakedness from such circuits requires $tau_p = Omega(tau_r/n)0.19)$ with overwhelming probability.
We also give numerical evidence that nontrivial peakedness is possible in this model.
arXiv Detail & Related papers (2024-04-22T18:00:06Z) - Learning shallow quantum circuits [7.411898489476803]
We present an algorithm for learning the description of any unknown $n$-qubit shallow quantum circuit $U$.
We also provide a classical algorithm for learning the description of any unknown $n$-qubit state $lvert psi rangle$.
Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions.
arXiv Detail & Related papers (2024-01-18T16:05:00Z) - Adaptive Circuit Learning of Born Machine: Towards Realization of
Amplitude Embedding and Data Loading [7.88657961743755]
We present a novel algorithm "Adaptive Circuit Learning of Born Machine" (ACLBM)
Our algorithm is tailored to selectively integrate two-qubit entangled gates that best capture the complex entanglement present within the target state.
Empirical results underscore the proficiency of our approach in encoding real-world data through amplitude embedding.
arXiv Detail & Related papers (2023-11-29T16:47:31Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z) - Quantum Extremal Learning [0.8937790536664091]
We propose a quantum algorithm for extremal learning', which is the process of finding the input to a hidden function that extremizes the function output.
The algorithm, called quantum extremal learning (QEL), consists of a parametric quantum circuit that is variationally trained to model data input-output relationships.
arXiv Detail & Related papers (2022-05-05T17:37:26Z) - 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) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions.
Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
arXiv Detail & Related papers (2021-06-24T20:16:02Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06: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.