Document Open Access Logo

Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem

Authors Kai-Min Chung , Han-Hsuan Lin

PDF
Thumbnail PDF

File

LIPIcs.TQC.2021.3.pdf
  • Filesize: 1.38 MB
  • 22 pages

Document Identifiers

Author Details

Kai-Min Chung
  • Institute of Information Science, Academia Sinica, Taipei, Taiwan
Han-Hsuan Lin
  • Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan

Funding

  • Chung, Kai-Min: This research is partially supported by the 2016 Academia Sinica Career Development Award under Grant no. 23-17.
  • Lin, Han-Hsuan: This material is based on research/work supported by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13.

Cite AsGet BibTex

Kai-Min Chung and Han-Hsuan Lin. Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.TQC.2021.3

Abstract

The probably approximately correct (PAC) model [Leslie G. Valiant, 1984] is a well studied model in classical learning theory. Here, we generalize the PAC model from concepts of Boolean functions to quantum channels, introducing PAC model for learning quantum channels, and give two sample efficient algorithms that are analogous to the classical "Occam’s razor" result [Blumer et al., 1987]. The classical Occam’s razor algorithm is done trivially by excluding any concepts not compatible with the input-output pairs one gets, but such an approach is not immediately possible with a concept class of quantum channels, because the outputs are unknown quantum states from the quantum channel. To study the quantum state learning problem associated with PAC learning quantum channels, we focus on the special case where the channels all have constant output. In this special case, learning the channels reduce to a problem of learning quantum states that is similar to the well known quantum state discrimination problem [Joonwoo Bae and Leong-Chuan Kwek, 2017], but with the extra twist that we allow ε-trace-distance-error in the output. We call this problem Approximate State Discrimination, which we believe is a natural problem that is of independent interest. We give two algorithms for learning quantum channels in PAC model. The first algorithm has sample complexity O((log|C| + log(1/ δ))/(ε²)), but only works when the outputs are pure states, where C is the concept class, ε is the error of the output, and δ is the probability of failure of the algorithm. The second algorithm has sample complexity O((log³|C|(log|C|+log(1/ δ)))/(ε²)), and work for mixed state outputs. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples, and approximate state discrimination can be solved in polynomial samples even when the size of the input set is exponential in the number of qubits, exponentially better than a naive state tomography.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum information theory
  • Theory of computation → Quantum complexity theory
Keywords
  • PAC learning
  • Quantum PAC learning
  • Sample Complexity
  • Approximate State Discrimination
  • Quantum information

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. Quantum algorithmic measurement. arXiv preprint arXiv:2101.04634, 2021. Google Scholar
  2. Noga Alon, Shai Ben-David, Nicolo Cesa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM (JACM), 44(4):615-631, 1997. Google Scholar
  3. Srinivasan Arunachalam and Ronald de Wolf. Guest column: A survey of quantum learning theory. SIGACT News, 48(2):41-67, 2017. URL: https://doi.org/10.1145/3106700.3106710.
  4. Srinivasan Arunachalam and Ronald de Wolf. Optimal quantum sample complexity of learning algorithms. In Computational Complexity Conference, volume 79 of LIPIcs, pages 25:1-25:31. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  5. Srinivasan Arunachalam, Alex B Grilo, and Aarthi Sundaram. Quantum hardness of learning shallow classical circuits. arXiv preprint arXiv:1903.02840, 2019. Google Scholar
  6. Koenraad MR Audenaert and Milán Mosonyi. Upper bounds on the error probabilities and asymptotic error exponents in quantum multiple state discrimination. Journal of Mathematical Physics, 55(10):102201, 2014. Google Scholar
  7. Costin Bădescu and Ryan O'Donnell. Improved quantum data analysis. arXiv preprint arXiv:2011.10908, 2020. Google Scholar
  8. Joonwoo Bae and Leong-Chuan Kwek. Quantum state discrimination and its applications. J. Phys. A: Math. Theor. 48 083001 (2015), 2017. URL: https://doi.org/10.1088/1751-8113/48/8/083001.
  9. Howard Barnum and Emanuel Knill. Reversing quantum dynamics with near-optimal quantum and classical fidelity. Journal of Mathematical Physics, 43(5):2097-2106, 2002. Google Scholar
  10. Peter L Bartlett, Philip M Long, and Robert C Williamson. Fat-shattering and the learnability of real-valued functions. journal of computer and system sciences, 52(3):434-452, 1996. Google Scholar
  11. Shai Bendavid, Nicolo Cesabianchi, David Haussler, and Philip M Long. Characterizations of learnability for classes of 0,..., n-valued functions. Journal of Computer and System Sciences, 50(1):74-86, 1995. Google Scholar
  12. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Occam’s razor. Information processing letters, 24(6):377-380, 1987. Google Scholar
  13. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929-965, 1989. Google Scholar
  14. Hao-Chung Cheng, Min-Hsiu Hsieh, and Ping-Cheng Yeh. The learnability of unknown quantum measurements. QIC, Vol. 16, No. 7-8, 0615-0656 (2016), 2015. URL: http://arxiv.org/abs/arXiv:1501.00559.
  15. Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 913-925, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2897518.2897585.
  16. Steve Hanneke. The optimal sample complexity of pac learning. The Journal of Machine Learning Research, 17(1):1319-1333, 2016. Google Scholar
  17. Aram W Harrow and Andreas Winter. How many copies are needed for state discrimination? IEEE Transactions on Information Theory, 58(1):1-2, 2012. Google Scholar
  18. David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput., 100(1):78-150, 1992. URL: https://doi.org/10.1016/0890-5401(92)90010-D.
  19. Hsin-Yuan Huang, Richard Kueng, and John Preskill. Information-theoretic bounds on quantum advantage in machine learning. arXiv preprint arXiv:2101.02464, 2021. Google Scholar
  20. Michael J Kearns and Robert E Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464-497, 1994. Google Scholar
  21. Michael J. Kearns, Robert E. Schapire, and Linda Sellie. Toward efficient agnostic learning. Machine Learning, 17(2-3):115-141, 1994. URL: https://doi.org/10.1007/BF00993468.
  22. Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA, 1994. Google Scholar
  23. Masoud Mohseni, AT Rezakhani, and DA Lidar. Quantum-process tomography: Resource analysis of different strategies. Physical Review A, 77(3):032322, 2008. Google Scholar
  24. Ashley Montanaro. On the distinguishability of random quantum states. Comm. Math. Phys. 273(3), pp. 619-636, 2007, 2006. URL: https://doi.org/10.1007/s00220-007-0221-7.
  25. Ashley Montanaro. A lower bound on the probability of error in quantum state discrimination. In Information Theory Workshop, 2008. ITW'08. IEEE, pages 378-380. IEEE, 2008. Google Scholar
  26. Balas K Natarajan. On learning sets and functions. Machine Learning, 4(1):67-97, 1989. Google Scholar
  27. Ryan O'Donnell and John Wright. Efficient quantum tomography. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 899-912, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2897518.2897544.
  28. Pranab Sen. Random measurement bases, quantum state distinction and applications to the hidden subgroup problem. In Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on, pages 14-pp. IEEE, 2005. Google Scholar
  29. J. Prabhu Tej, Syed Raunaq Ahmed, A. R. Usha Devi, and A. K. Rajagopal. Quantum hypothesis testing and state discrimination. arXiv:1803.04944, 2018. Google Scholar
  30. Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, 1984. URL: https://doi.org/10.1145/1968.1972.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact