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 inputoutput 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 LeongChuan Kwek, 2017], but with the extra twist that we allow εtracedistanceerror 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((logC + 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(logC+log(1/ δ)))/(ε²)),
and work for mixed state outputs. Some implications of our results are that we can PAClearn 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.
BibTeX  Entry
@InProceedings{chung_et_al:LIPIcs.TQC.2021.3,
author = {Chung, KaiMin and Lin, HanHsuan},
title = {{Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem}},
booktitle = {16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
pages = {3:13:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771986},
ISSN = {18688969},
year = {2021},
volume = {197},
editor = {Hsieh, MinHsiu},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13998},
URN = {urn:nbn:de:0030drops139984},
doi = {10.4230/LIPIcs.TQC.2021.3},
annote = {Keywords: PAC learning, Quantum PAC learning, Sample Complexity, Approximate State Discrimination, Quantum information}
}
Keywords: 

PAC learning, Quantum PAC learning, Sample Complexity, Approximate State Discrimination, Quantum information 
Collection: 

16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) 
Issue Date: 

2021 
Date of publication: 

22.06.2021 