Pseudo-dimension of quantum circuits

Warren HE (1968) Lower bounds for approximation by nonlinear manifolds. Transactions of the American Mathematical Society 133(1):167, DOI 10.2307/1994937

1968

Earlier work this paper cites.

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, DOI 10.1137/1116025

1971

Earlier work this paper cites.

Valiant LG (1984) A theory of the learnable. Communications of the ACM 27(11):1134–1142, DOI 10.1145/1968.1972

1972

Earlier work this paper cites.

Pollard D (1984) Convergence of Stochastic Processes. Springer Series in Statistics, Springer, New York, NY, DOI 10.1007/978-1-4612-5254-2

1984

Earlier work this paper cites.

Blumer A, Ehrenfeucht A, Haussler D, Warmuth MK (1989) Learnability and the vapnik-chervonenkis dimension. Journal of the ACM 36(4):929–965, DOI 10.1145/76359.76371

1989

Earlier work this paper cites.

Goldberg PW, Jerrum MR (1995) Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning 18(2-3):131–148, DOI 10.1007/BF00993408

1995

Earlier work this paper cites.

Koiran P (1996) VC dimension in circuit complexity. In: Cai JY, Homer S (eds) Proceedings, Eleventh Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, Calif, pp 81–85, DOI 10.1109/CCC.1996.507671

1996

Earlier work this paper cites.

Alon N, Ben-David S, Cesa-Bianchi N, Haussler D (1997) Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM 44(4):615–631, DOI 10.1145/263867.263927

1997

Earlier work this paper cites.

Bartlett PL, Long PM (1998) Prediction, learning, uniform convergence, and scale-sensitive dimensions. Journal of Computer and System Sciences 56(2):174–190, DOI 10.1006/jcss.1997.1557

1997

Earlier work this paper cites.

Karpinski M, Macintyre A (1997) Polynomial bounds for vc dimension of sigmoidal and general pfaffian neural networks. Journal of Computer and System Sciences 54(1):169–176, DOI 10.1006/jcss.1997.1477

1997

Cited alongside, same era.

Anthony M, Bartlett PL (2000) Function learning from interpolation. Combinatorics, Probability and Computing 9(3):213–225, DOI 10.1017/S0963548300004247

2000

Cited alongside, same era.

Kiani BT, Lloyd S, Maity R (2020) Learning unitaries by gradient descent. URL https://arxiv.org/pdf/2001.11897

Original

2001

Cited alongside, same era.

Bartlett PL, Mendelson S (2002) Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research 3(Nov):463–482, URL http://www.jmlr.org/papers/volume3/bartlett02a/bartlett02a.pdf

2002

Cited alongside, same era.

Hanneke S (2016) The optimal sample complexity of pac learning. The Journal of Machine Learning Research 17(1):1319–1333, URL http://dl.acm.org/ft_gateway.cfm?id=2946683&type=pdf

2016

Later among the works it cites.

Arunachalam S, de Wolf R (2017) Guest column: A survey of quantum learning theory. SIGACT News 48, DOI 10.1145/3106700.3106710

2017

Later among the works it cites.

Rocchetto A (2017) Stabiliser states are efficiently pac-learnable. Quantum Information and Computation 18

2017

Later among the works it cites.

Aaronson S (2018) Shadow tomography of quantum states. DOI 10.1145/3188745.3188802

2018

Later among the works it cites.

Aaronson S, Chen X, Hazan E, Kale S (2018) Online learning of quantum states. URL http://dl.acm.org/ft_gateway.cfm?id=3327572&type=pdf

2018

Later among the works it cites.