zbMATH — the first resource for mathematics

The learnability of quantum states. (English) Zbl 1140.81317
Summary: 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 one can do exponentially better in a statistical setting. In particular, to predict the outcomes of most measurements drawn from an arbitrary probability distribution, one needs only a number of sample measurements that grows linearly with \(n\). This theorem has the conceptual implication that quantum states, despite being exponentially long vectors, are nevertheless ‘reasonable’ in a learning theory sense. The theorem also has two applications to quantum computing: first, a new simulation of quantum one-way communication protocols and second, the use of trusted classical advice to verify untrusted quantum advice.

81P68 Quantum computation
94A05 Communication theory
91E40 Memory and learning in psychology
PDF BibTeX Cite
Full Text: DOI
[1] Aaronson, S. 2004 Limitations of quantum advice and one-way communication. In <i>Proc. 19th. IEEE Conf. on Computational Complexity</i>, pp. 320–332.
[2] Aaronson, S. 2005 Quantum computing, postselection, and probabilistic polynomial-time. <i>Proc. R. Soc. A</i> <b>461</b>, 3473–3482, (doi:10.1098/rspa.2005.1546). · Zbl 1337.81032
[3] Aaronson, S. 2006 QMA/qpoly is contained in PSPACE/poly: de-Merlinizing quantum protocols. In <i>Proc. 21st IEEE Conf. on Computational Complexity</i>, pp. 261–273.
[4] Aaronson, S. & Gottesman, D. 2004 Improved simulation of stabilizer circuits. <i>Phys. Rev. A</i> <b>70</b>, 052328. (doi:10.1103/PhysRevA.70.052328).
[5] O’Brien, J.L., Pryde, G.J., White, A.G., Ralph, T.C. & Branning, D. 2003 Demonstration of an all-optical quantum controlled-NOT gate. <i>Nature</i> <b>426</b>, 264–267, (doi:10.1038/nature02054).
[6] 2004 <i>Quantum state estimation</i>, Berlin, Germany: Springer
[7] Resch, K.J., Walther, P. & Zeilinger, A. 2005 Full characterization of a three-photon Greenberger–Horne–Zeilinger state using quantum state tomograph. <i>Phys. Rev. Lett.</i> <b>94</b>, 070402. (doi:10.1103/PhysRevLett.94.070402).
[8] Skovsen, E., Stapelfeldt, H., Juhl, S. & Mølmer, K. 2003 Quantum state tomography of dissociating molecules. <i>Phys. Rev. Lett.</i> <b>91</b>, 090406. (doi:10.1103/PhysRevLett.91.090406).
[9] Terhal, B.M. & DiVincenzo, D.P. 2002 Classical simulation of noninteracting-fermion quantum circuits. <i>Phys. Rev. A</i> <b>65</b>, 032325. (doi:10.1103/PhysRevA.65.032325).
[10] Valiant, L.G. 1984 A theory of the learnable. <i>Commun. ACM</i> <b>27</b>, 1134–1142, (doi:10.1145/1968.1972). · Zbl 0587.68077
[11] Aaronson, S. & Kuperberg, G. 2007 Quantum versus classical proofs and advice. In <i>Proc. 22nd IEEE Conf. on Computational Complexity</i>, pp. 115–128. · Zbl 1213.68290
[12] Alon, N., Ben-David, S., Cesa-Bianchi, N. & Haussler, D. 1997 Scale-sensitive dimensions, uniform convergence, and learnability. <i>J. ACM</i> <b>44</b>, 615–631, (doi:10.1145/263867.263927). · Zbl 0891.68086
[13] Ambainis, A., Nayak, A., Ta-Shma, A. & Vazirani, U.V. 2002 Quantum dense coding and quantum finite automata. <i>J. ACM</i> <b>49</b>, 496–511, (doi:10.1145/581771.581773). · Zbl 1326.68133
[14] Anthony, M. & Bartlett, P.L. 2000 Function learning from interpolation. <i>Combinat. Prob. Comput.</i> <b>9</b>, 213–225, (doi:10.1017/S0963548300004247). · Zbl 0959.68055
[15] Bartlett, P.L. & Long, P.M. 1998 Prediction, learning, uniform convergence, and scale-sensitive dimensions. <i>J. Comput. Syst. Sci.</i> <b>56</b>, 174–190, (doi:10.1006/jcss.1997.1557). · Zbl 0945.68529
[16] Bartlett, P.L., Long, P.M. & Williamson, R.C. 1996 Fat-shattering and the learnability of real-valued functions. <i>J. Comput. Syst. Sci.</i> <b>52</b>, 434–452, (doi:10.1006/jcss.1996.0033). · Zbl 0858.68076
[17] Blumer, A., Ehrenfeucht, A., Haussler, D. & Warmuth, M.K. 1989 Learnability and the Vapnik–Chervonenkis dimension. <i>J. ACM</i> <b>36</b>, 929–965, (doi:10.1145/76359.76371). · Zbl 0697.68079
[18] Bogdanov, A. & Trevisan, L. 2006 Average-case complexity. ECCC TR06-073.
[19] Bužek, V. 2004 Quantum tomography from incomplete data via MaxEnt principle. <i>Quantum state estimation</i> (eds. Paris, M.G.A. & Řeháček, J.), pp. 189–234, Berlin, Germany: Springer
[20] Bužek, V., Drobný, G., Derka, R., Adam, G. & Wiedemann, H. 1999 Quantum state reconstruction from incomplete data. <i>Chaos Soliton. Fract.</i> <b>10</b>, 981–1074, (doi:10.1016/S0960-0779(98)00144-1). · Zbl 0998.81016
[21] D’Ariano, G.M., De Laurentis, M., Paris, M.G.A., Porzio, A. & Solimeno, S. 2002 Quantum tomography as a tool for the characterization of optical devices. <i>J. Opt. B: Quant. Semiclass. Opt.</i> <b>4</b>, S127–S132, (doi:10.1088/1464-4266/4/3/366).
[22] Gavinsky, D. Kempe, J. Kerenidis, I. Raz, R. & de Wolf, R. 2007 Exponential separations for one-way quantum communication complexity, with applications to cryptography. In <i>39th Ann. ACM Symp. on Theory of Computing</i>, pp. 516–525. · Zbl 1232.68051
[23] Goldreich, O. 2004 On quantum computing. See www.wisdom.weizmann.ac.il/oded/on-qc.html. <a target=”_blank” href=’http://www.wisdom.weizmann.ac.il/oded/on-qc.html’>www.wisdom.weizmann.ac.il/oded/on-qc.html</a>
[24] Goldreich, O., Goldwasser, S. & Micali, S. 1984 How to construct random functions. <i>J. ACM</i> <b>33</b>, 792–807, (doi:10.1145/6490.6503). · Zbl 0596.65002
[25] Häffner, H. <i>et al.</i> 2005 Scalable multiparticle entanglement of trapped ions. <i>Nature</i> <b>438</b>, 643–646, (doi:10.1038/nature04279).
[26] Kearns, M.J. & Schapire, E. 1994 Efficient distribution-free learning of probabilistic concepts. <i>J. Comput. Syst. Sci.</i> <b>48</b>, 464–497, (doi:10.1016/S0022-0000(05)80062-5).
[27] Klauck, H. 2000 Quantum communication complexity. In <i>Proc. Int. Colloquium on Automata, Languages, and Programming (ICALP)</i>, pp. 241–252. ArXiv:quant-ph/0005032.
[28] Levin, L.A. 2003 Polynomial time and extravagant models, in the table of one-way functions. <i>Probl. Inform. Transm.</i> <b>39</b>, 92–103, (doi:10.1023/A:1023634616182).
[29] Linial, N., Mansour, Y. & Nisan, N. 1993 Constant depth circuits, Fourier transform, and learnability. <i>J. ACM</i> <b>40</b>, 607–620, (doi:10.1145/174130.174138). · Zbl 0781.94006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.