Quantum-classical separations in shallow-circuit-based learning with and without noises

Communications Physics, vol. 7

Abstract

Abstract An essential problem in quantum machine learning is to find quantum-classical separations between learning models. However, rigorous and unconditional separations are lacking for supervised learning. Here we construct a classification problem defined by a noiseless constant depth (i.e., shallow) quantum circuit and rigorously prove that any classical neural network with bounded connectivity requires logarithmic depth to output correctly with a larger-than-exponentially-small probability. This unconditional near-optimal quantum-classical representation power separation originates from the quantum nonlocality property that distinguishes quantum circuits from their classical counterparts. We further characterize the noise regimes for demonstrating such a separation on near-term quantum devices under the depolarization noise model. In addition, for quantum devices with constant noise strength, we prove that no super-polynomial classical-quantum separation exists for any classification task defined by Clifford circuits, independent of the structures of the circuits that specify the learning models.

Authors 4

1. Zhihan Zhang

   Harvard University · Tsinghua University

   Affiliation as printed

   Center for Quantum Information, IIIS, Tsinghua University, Beijing, 100084, China

   School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, 02138, USA

2. Weiyuan Gong

   Harvard University · Tsinghua University

   Affiliation as printed

   Center for Quantum Information, IIIS, Tsinghua University, Beijing, 100084, China

   School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, 02138, USA

3. Weikang Li Aachen Instituut-Lorentz

   Leiden University · Tsinghua University

   Affiliation as printed

   Center for Quantum Information, IIIS, Tsinghua University, Beijing, 100084, China

   Instituut-Lorentz, Universiteit Leiden, P.O. Box 9506, 2300 RA, Leiden, The Netherlands

4. Dong-Ling Deng corresponding

   Shanghai Qi Zhi Institute · Tsinghua University

   Affiliation as printed

   Center for Quantum Information, IIIS, Tsinghua University, Beijing, 100084, China

   Hefei National Laboratory, Hefei, 230088, China

   Shanghai Qi Zhi Institute, 41st Floor, AI Tower, No. 701 Yunjin Road, Xuhui District, Shanghai, 200232, China