Pseudo-dimension of quantum circuits
- URL: http://arxiv.org/abs/2002.01490v3
- Date: Mon, 9 Nov 2020 08:10:00 GMT
- Title: Pseudo-dimension of quantum circuits
- Authors: Matthias C. Caro and Ishaun Datta
- Abstract summary: We prove pseudo-dimension bounds on the output probability of quantum circuits.
We show that circuits of known size and depth are PAC-learnable.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We characterize the expressive power of quantum circuits with the
pseudo-dimension, a measure of complexity for probabilistic concept classes. We
prove pseudo-dimension bounds on the output probability distributions of
quantum circuits; the upper bounds are polynomial in circuit depth and number
of gates. Using these bounds, we exhibit a class of circuit output states out
of which at least one has exponential state complexity, and moreover
demonstrate that quantum circuits of known polynomial size and depth are
PAC-learnable.
Related papers
- Learning shallow quantum circuits with many-qubit gates [1.879968161594709]
We present the first computationally-efficient algorithm for average-case learning of quantum circuits with many-qubit gates.
We show that the learned unitary can be efficiently synthesized in poly-logarithmic depth.
arXiv Detail & Related papers (2024-10-22T04:48:36Z) - The multimode conditional quantum Entropy Power Inequality and the squashed entanglement of the extreme multimode bosonic Gaussian channels [53.253900735220796]
Inequality determines the minimum conditional von Neumann entropy of the output of the most general linear mixing of bosonic quantum modes.
Bosonic quantum systems constitute the mathematical model for the electromagnetic radiation in the quantum regime.
arXiv Detail & Related papers (2024-10-18T13:59:50Z) - 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) - Short Proofs of Linear Growth of Quantum Circuit Complexity [3.8340125020400366]
The complexity of a quantum gate, defined as the minimal number of elementary gates to build it, is an important concept in quantum information and computation.
It is shown recently that the complexity of quantum gates built from random quantum circuits almost surely grows linearly with the number of building blocks.
arXiv Detail & Related papers (2022-05-11T17:53:57Z) - Gaussian initializations help deep variational quantum circuits escape
from the barren plateau [87.04438831673063]
Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years.
However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number.
This result leads to a general belief that deep quantum circuits will not be feasible for practical tasks.
arXiv Detail & Related papers (2022-03-17T15:06:40Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - Effects of quantum resources on the statistical complexity of quantum
circuits [4.318152590967423]
We investigate how the addition of quantum resources changes the statistical complexity of quantum circuits.
We show that the increase in the statistical complexity of a quantum circuit when an additional quantum channel is added is upper bounded by the free robustness of the added channel.
arXiv Detail & Related papers (2021-02-05T16:42:35Z) - Quantum State Complexity in Computationally Tractable Quantum Circuits [0.0]
We discuss a special class of numerically tractable quantum circuits, known as quantum automaton circuits.
We show that automaton wave functions have high quantum state complexity.
We present evidence of a linear growth of design complexity in local quantum circuits.
arXiv Detail & Related papers (2020-09-11T16:25:11Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling.
We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
arXiv Detail & Related papers (2020-05-05T20:11:53Z) - 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)
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.