Sample complexity of learning parametric quantum circuits
Haoyuan Cai, Qi Ye, Dong-Ling Deng
Abstract
Abstract Quantum computers hold unprecedented potentials for machine learning applications. Here, we prove that physical quantum circuits are 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mover accent="true"> <mml:mrow> <mml:mi>O</mml:mi> </mml:mrow> <mml:mo>~</mml:mo> </mml:mover> </mml:mrow> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow> <mml:msup> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> . 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.