On the Fundamental Resource for Exponential Advantage in Quantum Channel Learning

Abstract

Quantum resources enable us to achieve an exponential advantage in learning the properties of unknown physical systems by employing quantum memory. While entanglement with quantum memory is recognized as a necessary qualitative resource, its quantitative role remains less understood. In this work, we distinguish between two fundamental resources provided by quantum memory -- entanglement and ancilla qubits -- and analyze their separate contributions to the sampling complexity of quantum learning. Focusing on the task of Pauli channel learning, a prototypical example of quantum channel learning, remarkably, we prove that vanishingly small entanglement in the input state already suffices to accomplish the learning task with only a polynomial number of channel queries in the number of qubits. In contrast, we show that without a sufficient number of ancilla qubits, even learning partial information about the channel demands an exponentially large sample complexity. Thus, our findings reveal that while a large amount of entanglement is not necessary, the dimension of the quantum memory is a crucial resource. Hence, by identifying how the two resources contribute differently, our work offers deeper insight into the nature of the quantum learning advantage.

References in corpus (24)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum sensing
• Advances in Quantum Metrology
• Concentrating Partial Entanglement by Local Operations
• Quantum metrology
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum Computational Supremacy
• Quantum advantage in learning from experiments
• Noise tailoring for scalable quantum computation via randomized compiling
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors
• Information-theoretic bounds on quantum advantage in machine learning
• Measurement Optimization in the Variational Quantum Eigensolver Using a Minimum Clique Cover
• The Entanglement of Formation for Isotropic States
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Efficient estimation of Pauli channels
• Phase transition in Random Circuit Sampling
• Quantum advantages for Pauli channel estimation
• Pauli error estimation via Population Recovery
• Efficiently improving the performance of noisy quantum computers
• Entanglement-enabled advantage for learning a bosonic random displacement channel
• Tight bounds on Pauli channel learning without entanglement
• Quantum learning advantage on a scalable photonic platform