Sample Efficient Algorithms for Learning Quantum Channels in PAC Model
  and the Approximate State Discrimination Problem
  We generalize the PAC (probably approximately correct) learning model to the
quantum world by generalizing the concepts from classical functions to quantum
processes, defining the problem of \emph{PAC learning quantum process}, and
study its sample complexity. In the problem of PAC learning quantum process, we
want to learn an $\epsilon$-approximate of an unknown quantum process $c^*$
from a known finite concept class $C$ with probability $1-\delta$ using samples
$\{(x_1,c^*(x_1)),(x_2,c^*(x_2)),\dots\}$, where $\{x_1,x_2, \dots\}$ are
computational basis states sampled from an unknown distribution $D$ and
$\{c^*(x_1),c^*(x_2),\dots\}$ are the (possibly mixed) quantum states outputted
by $c^*$. The special case of PAC-learning quantum process under constant input
reduces to a natural problem which we named as approximate state
discrimination, where we are given copies of an unknown quantum state $c^*$
from an known finite set $C$, and we want to learn with probability $1-\delta$
an $\epsilon$-approximate of $c^*$ with as few copies of $c^*$ as possible. We
show that the problem of PAC learning quantum process can be solved with
$$O\left(\frac{\log|C| + \log(1/ \delta)} { \epsilon^2}\right)$$ samples when
the outputs are pure states and $$O\left(\frac{\log^3 |C|(\log |C|+\log(1/
\delta))} { \epsilon^2}\right)$$ samples if the outputs can be mixed. 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 concept class size $|C|$ is
exponential in the number of qubits, an exponentially improvement over a full
state tomography.
