Stabiliser states are efficiently PAC-learnable
The exponential scaling of the wave function is a fundamental property of quantum systems with far reaching implications in our ability to process quantum information. A problem where these are particularly relevant is quantum state tomography. State tomography, whose objective is to obtain a full description of a quantum system, can be analysed in the framework of computational learning theory. In this model, quantum states have been shown to be Probably Approximately Correct (PAC)-learnable with sample complexity linear in the number of qubits. However, it is conjectured that in general quantum states require an exponential amount of computation to be learned. Here, using results from the literature on the efficient classical simulation of quantum systems, we show that stabiliser states are efficiently PAC-learnable. Our results solve an open problem formulated by Aaronson [Proc. R. Soc. A, 2088, (2007)] and propose learning theory as a tool for exploring the power of quantum computation.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryQuantum State TomographySimilar Papers 제목 키워드 기반
Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
Bell sampling is a simple yet powerful tool based on measuring two copies of a quantum state in the Bell basis, and has found applications in a plethora of problems related to stabiliser states and measures of magic. How…
Discretionary vs nondiscretionary in fiscal mechanism. Non-automatic fiscal stabilisers vs automatic fiscal stabilisers
The goal of the present study is to increase the intelligibility of macroeconomic phenomena triggered by governmental intervention in economy by means of fiscal policies. During cyclical movements, fiscal policy can play…
Mixture of States: Routing Token-Level Dynamics for Multimodal Generation
We introduce MoS (Mixture of States), a novel fusion paradigm for multimodal diffusion models that merges modalities using flexible, state-based interactions. The core of MoS is a learnable, token-wise router that create…
Text-to-Image Generationmultimodal generationProvable learning of quantum states with graphical models
The complete learning of an $n$-qubit quantum state requires samples exponentially in $n$. Several works consider subclasses of quantum states that can be learned in polynomial sample complexity such as stabilizer states…
PAC learningNonlinear Robust Periodic Output Regulation of Minimum Phase Systems
In linear systems theory it's a well known fact that a regulator given by the cascade of an oscillatory dynamics, driven by some regulated variables, and of a stabiliser stabilising the cascade of the plant and of the os…
Blocking