ECCC-Report TR06-106https://eccc.weizmann.ac.il/report/2006/106Comments and Revisions published for TR06-106en-usMon, 28 Aug 2006 07:16:53 +0300
Paper TR06-106
| The Learnability of Quantum States |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2006/106Traditional 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.
Mon, 28 Aug 2006 07:16:53 +0300https://eccc.weizmann.ac.il/report/2006/106