Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises
We study quantum-classical separations between classical and quantum supervised learning models based on constant depth (i.e., shallow) circuits, in scenarios with and without noises. We construct a classification problem defined by a noiseless 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 separation originates from the quantum nonlocality property that distinguishes quantum circuits from their classical counterparts. We further derive the noise thresholds for demonstrating such a separation on near-term quantum devices under the depolarization noise model. We prove that this separation will persist if the noise strength is upper bounded by an inverse polynomial with respect to the system size, and vanish if the noise strength is greater than an inverse polylogarithmic function. 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 shallow Clifford circuits, independent of the structures of the circuits that specify the learning models.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning shallow quantum circuits
Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can gene…
An unconditional distribution learning advantage with shallow quantum circuits
One of the core challenges of research in quantum computing is concerned with the question whether quantum advantages can be found for near-term quantum circuits that have implications for practical applications. Motivat…
Quantum Kernel Methods: Convergence Theory, Separation Bounds and Applications to Marketing Analytics
This work studies the feasibility of applying quantum kernel methods to a real consumer classification task in the NISQ regime. We present a hybrid pipeline that combines a quantum-kernel Support Vector Machine (Q-SVM) w…
Structured Unitary Tensor Network Representations for Circuit-Efficient Quantum Data Encoding
Encoding classical data into quantum states is a central bottleneck in quantum machine learning: many widely used encodings are circuit-inefficient, requiring deep circuits and substantial quantum resources, which limits…
Quantum Machine LearningLearning and Generating Mixed States Prepared by Shallow Channel Circuits
Learning quantum states from measurement data is a central problem in quantum information and computational complexity. In this work, we study the problem of learning to generate mixed states on a finite-dimensional latt…