Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-106 | 18th August 2006 00:00

The Learnability of Quantum States

RSS-Feed




TR06-106
Authors: Scott Aaronson
Publication: 28th August 2006 07:16
Downloads: 1474
Keywords: 


Abstract:

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible implications for experimental physics, our learning theorem has two applications to quantum computing: first, a new simulation of quantum one-way protocols, and second, the use of trusted classical advice to verify untrusted quantum advice.



ISSN 1433-8092 | Imprint