Search

Quantum devices are subject to natural decay. We propose to study these decay processes as the Markovian evolution of quantum channels, which leads us to dynamical semigroups of superchannels. A superchannel is a linear map that maps quantum channels to quantum channels, while satisfying suitable consistency relations. If the input and output quantum channels act on the same space, then we can consider dynamical semigroups of superchannels. No useful constructive characterization of the generators of such semigroups is known. We characterize these generators in two ways: First, we give an efficiently checkable criterion for whether a given map generates a dynamical semigroup of superchannels. Second, we identify a normal form for the generators of semigroups of quantum superchannels, analogous to the GKLS form in the case of quantum channels. To derive the normal form, we exploit the relation between superchannels and semicausal completely positive maps, reducing the problem to finding a normal form for the generators of semigroups of semicausal completely positive maps. We derive a normal for these generators using a novel technique, which applies also to infinite-dimensional systems. Our work paves the way to a thorough investigation of semigroups of superchannels: Numerical studies become feasible because admissible generators can now be explicitly generated and checked. And analytic properties of the corresponding evolution equations are now accessible via our normal form., 33 pages, 6 figures; corrected some typos and updated the list of references

A large body of recent work has begun to explore the potential of parametrized quantum circuits (PQCs) as machine learning models, within the framework of hybrid quantum-classical optimization. In particular, theoretical guarantees on the out-of-sample performance of such models, in terms of generalization bounds, have emerged. However, none of these generalization bounds depend explicitly on how the classical input data is encoded into the PQC. We derive generalization bounds for PQC-based models that depend explicitly on the strategy used for data-encoding. These imply bounds on the performance of trained PQC-based models on unseen data. Moreover, our results facilitate the selection of optimal data-encoding strategies via structural risk minimization, a mathematically rigorous framework for model selection. We obtain our generalization bounds by bounding the complexity of PQC-based models as measured by the Rademacher complexity and the metric entropy, two complexity measures from statistical learning theory. To achieve this, we rely on a representation of PQC-based models via trigonometric functions. Our generalization bounds emphasize the importance of well-considered data-encoding strategies for PQC-based models., Comment: 35 pages, 3 figures; corrected a mistake in Eq. (38) of the previous version, results remain unchanged except for a restriction to frequency vectors with integer entries; added a conjecture to recover results in full

We characterize the expressive power of quantum circuits with the pseudo-dimension, a measure of complexity for probabilistic concept classes. We prove pseudo-dimension bounds on the output probability distributions of quantum circuits; the upper bounds are polynomial in circuit depth and number of gates. Using these bounds, we exhibit a class of circuit output states out of which at least one has exponential state complexity, and moreover demonstrate that quantum circuits of known polynomial size and depth are PAC-learnable., 22 pages, 1 figure; corrected Lemma 3.8, this does not change our results

In classical statistical learning theory, one of the most well studied problems is that of binary classification. The information-theoretic sample complexity of this task is tightly characterized by the Vapnik-Chervonenkis (VC) dimension. A quantum analog of this task, with training data given as a quantum state has also been intensely studied and is now known to have the same sample complexity as its classical counterpart. We propose a novel quantum version of the classical binary classification task by considering maps with classical input and quantum output and corresponding classical-quantum training data. We discuss learning strategies for the agnostic and for the realizable case and study their performance to obtain sample complexity upper bounds. Moreover, we provide sample complexity lower bounds which show that our upper bounds are essentially tight for pure output states. In particular, we see that the sample complexity is the same as in the classical binary classification task w.r.t. its dependence on accuracy, confidence and the VC-dimension., 17 pages (main body) + 23 pages (references and appendix); improved presentation including illustrative examples

Characterizing those quantum channels that correspond to Markovian time evolutions is an open problem in quantum information theory, even different notions of quantum Markovianity exist. One such notion is that of infinitesimal Markovian divisibility for quantum channels introduced in arXiv:math-ph/0611057. Whereas there is a complete characterization for infinitesimal Markovian divisible qubit channels, no necessary or sufficient criteria are known for higher dimensions, except for necessity of non-negativity of the determinant. We describe how to extend the notion of infinitesimal Markovian divsibility to general linear maps and closed and convex sets of generators. We give a general approach towards proving necessary criteria for (infinitesimal) Markovian divisibility that involve singular values of the linear map. With this approach, we prove two necessary criteria for infinitesimal divisibility of quantum channels that work in any finite dimension $d$: an upper bound on the determinant in terms of a $\Theta(d)$-power of the smallest singular value, and in terms of a product of $\Theta(d)$ smallest singular values. Our criteria allow us to analytically construct, in any given dimension, a set of channels that contains provably non infinitesimal Markovian divisible ones. We also discuss the classical counterpart of this scenario, i.e., stochastic matrices with the generators given by transition rate matrices. Here, we show that no necessary criteria for infinitesimal Markovian divisibility of the form proved for quantum channels can hold in general. However, we describe subsets of all transition rate matrices for which our reasoning can be applied to obtain necessary conditions for Markovian divisibility., Comment: 22 pages (main body) + 5 pages (references and appendix); 1 figure; V2: extended related works section to provide better context, slight change in the wording of the main definitions, notions and results remain the same; V3: added a previously missing assumption in Lemma 4.26

The problem of learning Boolean linear functions from quantum examples w.r.t. the uniform distribution can be solved on a quantum computer using the Bernstein-Vazirani algorithm. A similar strategy can be applied in the case of noisy quantum training data, as was observed in arXiv:1702.08255v2 [quant-ph]. However, extensions of these learning algorithms beyond the uniform distribution have not yet been studied. We employ the biased quantum Fourier transform introduced in arXiv:1802.05690v2 [quant-ph] to develop efficient quantum algorithms for learning Boolean linear functions on $n$ bits from quantum examples w.r.t. a biased product distribution. Our first procedure is applicable to any (except full) bias and requires $\mathcal{O}(\ln (n))$ quantum examples. The number of quantum examples used by our second algorithm is independent of $n$, but the strategy is applicable only for small bias. Moreover, we show that the second procedure is stable w.r.t. noisy training data and w.r.t. faulty quantum gates. This also enables us to solve a version of the learning problem in which the underlying distribution is not known in advance. Finally, we prove lower bounds on the classical and quantum sample complexities of the learning problem. Whereas classically, $\Omega (n)$ examples are necessary independently of the bias, we are able to establish a quantum sample complexity lower bound of $\Omega (\ln (n))$ only under an assumption of large bias. Nevertheless, this allows for a discussion of the performance of our suggested learning algorithms w.r.t. sample complexity. With our analysis we contribute to a more quantitative understanding of the power and limitations of quantum training data for learning classical functions., Comment: 27 pages main text, 12 pages Appendix; 2 figures; improved and extended presentation containing a strengthened quantum sample complexity lower bound; accepted for publication in Quantum Information Processing

This dissertation treats questions from quantum learning theory, at the intersection point of quantum information theory and machine learning. We prove guarantees on how variational quantum machine learning models generalize from training data to unseen data. And we explore the complexity of tasks of learning an unknown map from quantum data. Finally, we discuss questions related to Markovianity in quantum evolutions and aspects of undecidability in learning theory. Diese Dissertation befasst sich mit Fragen der Quantenlerntheorie, an der Schnittstelle von Quanteninformationstheorie und maschinellem Lernen. Wir beweisen Garantien darüber, wie variationelle Quantenlernmodelle von Trainingsdaten auf unbeobachtete Daten verallgemeinern. Und wir untersuchen Lernprobleme, in denen von Quantendaten gelernt wird. Schließlich diskutieren wir Fragen zur Markovianität von Quantenevolutionen und Aspekte von Unentscheidbarkeit in der Lerntheorie.