Sample Complexity of Learning Parametric Quantum Circuits

2021/07/19 by Haoyuan Cai, Cai, Haoyuan, Qi Ye +3 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Mathematical Physics (math-ph) #Quantum Physics (quant-ph) #cs.LG #math-ph #math.MP #quant-ph

paper · pdf · doi:10.48550/arxiv.2107.09078

19 pages, 1 figure

arxiv created 2022/01/01 · arxiv updated 2022/01/04

Abstract

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 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.

Cited by

• Near-optimal Prediction Error Estimation for Quantum Machine Learning Models
• Data Complexity: a threshold between Classical and Quantum Machine Learning -- Part I

Related

• Quantum learning algorithms imply circuit lower bounds
• An Introduction to Quantum Machine Learning for Engineers
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Quantum hardness of learning shallow classical circuits
• Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness