Pseudo-dimension of quantum circuits
Tóm tắt
We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential gate complexity of state preparation, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable.
Tài liệu tham khảo
Aaronson S (2007) The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 463(2088):3089–3114. https://doi.org/10.1098/rspa.2007.0113
Aaronson S (2016) The complexity of quantum states and transformations: From quantum money to black holes. Electronic Colloquium on Computational Complexity (ECCC) 23:109
Aaronson S (2018) Shadow tomography of quantum states. http://dl.acm.org/ft_gateway.cfm?id=3188802&type=pdf
Aaronson S, Chen X, Hazan E, Kale S (2018) Online learning of quantum states. http://dl.acm.org/ft_gateway.cfm?id=3327572&type=pdf
Alon N, Ben-David S, Cesa-Bianchi N, Haussler D (1997) Scale-sensitive dimensions, uniform convergence, and learnability. J ACM 44(4):615–631. https://doi.org/10.1145/263867.263927
Anthony M, Bartlett PL (2000) Function learning from interpolation. Comb Probab Comput 9(3):213–225. https://doi.org/10.1017/S0963548300004247
Arunachalam S, de Wolf R (2017) Guest column: A survey of quantum learning theory. SIGACT News 48 , https://pure.uva.nl/ws/files/25255496/p41_arunachalam.pdf
Bartlett PL, Long PM (1998) Prediction, learning, uniform convergence, and scale-sensitive dimensions. J Comput Sys Sci 56(2):174–190. https://doi.org/10.1006/jcss.1997.1557
Bartlett PL, Mendelson S (2002) Rademacher and gaussian complexities: Risk bounds and structural results. J Mach Learn Res 3(Nov):463–482. http://www.jmlr.org/papers/volume3/bartlett02a/bartlett02a.pdf
Blumer A, Ehrenfeucht A, Haussler D, Warmuth M K (1989) Learnability and the vapnik-chervonenkis dimension. J ACM 36(4):929–965. https://doi.org/10.1145/76359.76371
Cheng HC, Hsieh MH, Yeh PC (2016) The learnability of unknown quantum measurements. Quantum Information & Computation 16(7-8):615–656
Chung KM, Lin HH (2018) Sample efficient algorithms for learning quantum channels in pac model and the approximate state discrimination problem. arXiv:1810.10938
Goldberg PW, Jerrum MR (1995) Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Mach Learn 18(2-3):131–148. https://doi.org/10.1007/BF00993408
Hanneke S (2016) The optimal sample complexity of pac learning. J Mach Learn Res 17(1):1319–1333. http://dl.acm.org/ft_gateway.cfm?id=2946683&type=pdf
Heinosaari T, Ziman M (2013) The mathematical language of quantum theory: From uncertainty to entanglement. Cambridge University Press, Cambridge
Karpinski M, Macintyre A (1997) Polynomial bounds for vc dimension of sigmoidal and general pfaffian neural networks. J Comput Sys Sci 54(1):169–176. https://doi.org/10.1006/jcss.1997.1477
Kiani BT, Lloyd S, Maity R (2020) Learning unitaries by gradient descent. arXiv:2001.11897
Koiran P (1996) VC dimension in circuit complexity. In: Cai J Y, Homer S (eds) Proceedings, Eleventh annual ieee conference on computational complexity. https://doi.org/10.1109/CCC.1996.507671. IEEE Computer Society Press, Los Alamitos, pp 81–85
Nielsen MA, Chuang IL (2010) Quantum computation and quantum information. Cambridge University Press, Cambridge and New York
Pollard D (1984) Convergence of stochastic processes. Springer Series in Statistics. Springer, New York
Rocchetto A (2017) Stabiliser states are efficiently pac-learnable. Quantum Information and Computation, 18
Rocchetto A, Aaronson S, Severini S, Carvacho G, Poderini D, Agresti I, Bentivegna M, Sciarrino F (2019) Experimental learning of quantum states. Science Advances 5(3), https://doi.org/10.1126/sciadv.aau1946
Torlai G, Mazzola G, Carrasquilla J, Troyer M, Melko R, Carleo G (2018) Neural-network quantum state tomography. Nat Phy 14(5):447–450 . https://doi.org/10.1038/s41567-018-0048-5, https://www.nature.com/articles/s41567-018-0048-5.pdf
Valiant LG (1984) A theory of the learnable. Commun ACM 27(11):1134–1142. https://doi.org/10.1145/1968.1972
Vapnik VN, Chervonenkis AY (1971) On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications 16(2):264–280. https://doi.org/10.1137/1116025
Warren HE (1968) Lower bounds for approximation by nonlinear manifolds. Trans Am Math Soc 133(1):167. https://doi.org/10.2307/1994937