Cited By
View all- Arunachalam SMaity RDaumé HSingh A(2020)Quantum boostingProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3524974(377-387)Online publication date: 13-Jul-2020
Stabiliser states are efficiently PAC-learnable
Pages 541 - 552
Abstract
The exponential scaling of the wave function is a fundamental property of quantum systems with far reaching implications in our ability to process quantum information. A problem where these are particularly relevant is quantum state tomography. State tomography, whose objective is to obtain an approximate description of a quantum system, can be analysed in the framework of computational learning theory. In this model, Aaronson (2007) showed that quantum states are Probably Approximately Correct (PAC)-learnable with sample complexity linear in the number of qubits. However, it is conjectured that in general quantum states require an exponential amount of computation to be learned. Here, using results from the literature on the efficient classical simulation of quantum systems, we show that stabiliser states are efficiently PAC-learnable. Our results solve an open problem formulated by Aaronson (2007) and establish a connection between classical simulation of quantum systems and efficient learnability.
References
[1]
J. Haah, A.W. Harrow, Z. Ji, X. Wu and N. Yu (2017), Sample-optimal tomography of quantum states, IEEE Trans. Inf. Theory, 63, pp. 5628-5641.
[2]
R. O'Donnell and J. Wright (2016), Efficient quantum tomography, Proc. 48th annual ACM Symposium on Theory of Computing (STOC), pp. 899-912.
[3]
S. Aaronson (2007), The learnability of quantum states, Proc. Royal Soc. A, 2088, pp. 3089-3114.
[4]
A. Rocchetto, S. Aaronson, S. Severini, G. Carvacho, D. Poderini, I. Agresti, M. Bentivegna and F. Sciarrino (2017), Experimental learning of quantum states, quant-ph/1712.00127.
[5]
A.R. Klivans, R. O'Donnell and R. Servedio (2004), Learning intersections and thresholds of half-spaces, J. Comput. Syst. Sci., 68, pp. 808-840.
[6]
P. Fischer and H.U. Simon (1992), On learning ring-sum-expansions, SIAM J. Comput., 1, pp. 181-192.
[7]
D. Helmbold, R. Sloan and M. Warmuth (1992), Learning integer lattices, SIAM J. Comput., 2, pp. 240-266.
[8]
L. Hellerstein and R. Servedio (2007), On PAC learning algorithms for rich Boolean function classes, Theor. Comput. Sci., 1, pp. 66-76.
[9]
S. Arunachalam and R. de Wolf (2017), Guest Column: A Survey of Quantum Learning Theory SIGACT News, 48, pp. 41-67.
[10]
C. Ciliberto, M. Herbster, A.D. Ialongo, M. Pontil, A. Rocchetto, S. Severini and L. Wossnig (2018), Quantum machine learning: a classical perspective, Proc. Royal Soc. A, 474:20170551 (2018).
[11]
D. Gottesman (1996), Class of quantum error-correcting codes saturating the quantum Hamming bound, Phys. Rev. A, 54, p. 1862.
[12]
D. Gottesman (1997), Stabilizer codes and quantum error correction, quant-ph/9705052.
[13]
D. Gottesman (1998), The Heisenberg representation of quantum computers, quant-ph/9807006.
[14]
H.J. García, I.L. Markov and A.W. Cross (2014), On the geometry of stabilizer states, Quantum Inf. Comput., Vol. 14, pp. 683-720.
[15]
L.G. Valiant (1984), A theory of the learnable, Commun. ACM, 27.11, pp. 1134-1142.
[16]
P.L. Bartlett, P.M. Long and R.C. Williamson (1994), Fat-shattering and the learnability of real-valued functions, Proc. seventh annual conference on Computational Learning Theory (COLT), pp. 299-310.
[17]
E. Hazan (2008), Sparse approximate solutions to semidefinite programs, Latin American Symposium on Theoretical Informatics, Springer (Berlin and Heidelberg).
[18]
F.G. Brandão, A. Kalev, T. Li, C.Y.Y. Lin, K.M. Svore and X. Wu (2017), Exponential quantum speed-ups for semidefinite programming with applications to quantum learning, quant-ph/1710.02581.
[19]
S. Aaronson (2017), Shadow Tomography of Quantum States, quant-ph/1711.01053.
[20]
S. Aaronson, X. Chen, E. Hazan and A. Nayak (2018), Online learning of quantum states, quant-ph/1802.09025.
[21]
S. Aaronson and D. Gottesman (2008), Identifying stabilizer states, http://pirsa.org/08080052.
[22]
A. Montanaro (2017), Learning stabilizer states by Bell sampling, quant-ph/1707.04012.
[23]
R.A. Low (2009), Learning and testing algorithms for the Clifford group, Phys. Rev. A, 80, p. 052314.
[24]
L. Zhao, C.A. Pérez-Delgado and J.F. Fitzsimons (2016), Fast graph operations in quantum computation, Phys. Rev. A, 93, p. 032314.
[25]
M. Hamermesh (2012), Group theory and its application to physical problems, Courier Corporation (New York).
[26]
M.A. Nielsen and I. Chuang (2010), Quantum computation and quantum information, Cambridge University Press (Cambridge).
[27]
S. Aaronson and D. Gottesman (2004), Improved simulation of stabilizer circuits, Phys. Rev. A, 70, p.052328.
[28]
L.G. Valiant (2001), Quantum computers that can be simulated classically in polynomial time, Proc. 33rd annual ACM Symposium on Theory of Computing (STOC), pp. 114-123.
[29]
B.M. Terhal and D.P. DiVincenzo (2002), Classical simulation of noninteracting-fermion quantum circuits, Phys. Rev. A, 65, 032325 (2002).
[30]
R. Jozsa and A. Miyake (2008), Matchgates and classical simulation of quantum circuits, Proc. Royal Soc. A, 2100, pp. 3089-3106.
[31]
M. Van den Nest (2011), Simulating quantum computers with probabilistic methods, Quantum Inf. Comput., Vol. 11, pp. 784-812.
[32]
M. Schwarz and M. Van den Nest (2013), Simulating quantum circuits with sparse output distributions, quant-ph/1310.6749.
[33]
F.G. Brandão and K. Svore (2017), Quantum Speed-ups for Semidefinite Programming, Proc. IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 403-414.
[34]
J. van Apeldoorn, A. Gilyn, S. Gribling and R. de Wolf (2017), Quantum SDP-Solvers: Better upper and lower bounds, Proc. IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 403-414.
- Stabiliser states are efficiently PAC-learnable
Recommendations
Reconstruction of bipartite states via unambiguous state discrimination and mutually unbiased measurement
We propose a scheme for reconstructing an unknown two-particle mixed state by means of unambiguous state discrimination. In this protocol, an ancillary particle is introduced for distinguishing four nonorthogonal states. The discrimination process is ...
Experimental realization of quantum teleportation using coined quantum walks
AbstractThe goal of teleportation is to transfer the state of one particle to another particle. In coined quantum walks, conditional shift operators can introduce entanglement between position space and coin space. This entanglement resource can be used ...
Spin coherent states phenomena probed by quantum state tomography in Zeeman perturbed nuclear quadrupole resonance
Recently, we reported an experimental implementation of quantum information processing (QIP) by nuclear quadrupole resonance (NQR). In this work, we present the first quantum state tomography (QST) experimental implementation in the NQR QIP context. Two ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Rinton Press, Incorporated
Paramus, NJ
Publication History
Published: 01 June 2018
Revised: 15 March 2018
Received: 31 December 2017
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024
Other Metrics
Citations
Cited By
View all- Arunachalam SMaity RDaumé HSingh A(2020)Quantum boostingProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3524974(377-387)Online publication date: 13-Jul-2020