Sample Complexity of Learning Parametric Quantum Circuits
Quantum computers hold unprecedented potentials for machine learning applications. Here, we prove that physical quantum circuits are PAC (probably approximately correct) learnable on a quantum computer via empirical risk minimization: to learn a parametric quantum circuit with at most $n^c$ gates and each gate acting on a constant number of qubits, the sample complexity is bounded by $\tilde{O}(n^{c+1})$. In particular, we explicitly construct a family of variational quantum circuits with $O(n^{c+1})$ elementary gates arranged in a fixed pattern, which can represent all physical quantum circuits consisting of at most $n^c$ elementary gates. Our results provide a valuable guide for quantum machine learning in both theory and practice.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningQuantum Machine LearningSimilar Papers 제목 키워드 기반
Data Complexity Measures for Quantum Circuits Architecture Recommendation
Quantum Parametric Circuits are constructed as an alternative to reduce the size of quantum circuits, meaning to decrease the number of quantum gates and, consequently, the depth of these circuits. However, determining t…
Quantum Policy Gradient in Reproducing Kernel Hilbert Space
Parametrised quantum circuits offer expressive and data-efficient representations for machine learning. Due to quantum states residing in a high-dimensional Hilbert space, parametrised quantum circuits have a natural int…
Variational Quantum Circuit Model for Knowledge Graphs Embedding
In this work, we propose the first quantum Ans\"atze for the statistical relational learning on knowledge graphs using parametric quantum circuits. We introduce two types of variational quantum circuits for knowledge gra…
Graph EmbeddingKnowledge Graph EmbeddingKnowledge Graphsmodel+2A learning theory for quantum photonic processors and beyond
We consider the tasks of learning quantum states, measurements and channels generated by continuous-variable (CV) quantum circuits. This family of circuits is suited to describe optical quantum technologies and in partic…
Learning TheoryLearnability and Complexity of Quantum Samples
Given a quantum circuit, a quantum computer can sample the output distribution exponentially faster in the number of bits than classical computers. A similar exponential separation has yet to be established in generative…
Benchmarking