Learning about quantum systems and their evolution over time is a task of fundamental importance in quantum physics. “Learning”, broadly speaking, refers to the extraction of useful classical information from quantum-mechanical systems and their evolution through experiments. Such learning tasks first appeared in quantum information in the form of quantum state and process tomography, in which the aim is to extract all classical information about the system, in terms of the density matrix of the system in the case of quantum state tomography [1–6], and the transfer matrix in the case of quantum process tomography [7–9]. These tomographic tasks, with their strict measures of performance in terms of worst-case distance measures such as the trace and diamond
Figure 1: Learning of quantum processes. (a) To learn about the unknown evolution of a quantum system (symbolized by the blue shaded region and represented mathematically by the quantum channel N), we prepare a probe quantum state , let it evolve, and then measure it according to the POVM
. We encapsulate this process in the circuit diagram shown in (b). (c) More generally, we can prepare an entangled probe state of two systems, let only one of them evolve, and then jointly measure both systems. Our results apply to this more general class of tests, and also more generally to classes of multi-time quantum processes, in which the unknown evolution could be non-Markovian.
norm, require resources scaling exponentially with the system size [10–14]. Consequently, recent years have seen a growing interest in less strict variants of state and process learning, defined by relaxing the requirement of extracting full classical information about the objects of interest and instead requiring that we learn only the values of certain observables of our state or process. In the case of quantum states, notable such learning tasks include “pretty good tomography” in the spirit of probably approximately correct (PAC) learning [15], shadow tomography [16–19], online learning [20, 21], and classical shadows [22–24]. Inspired by this progress in understanding state learning, also new perspectives on quantum channel learning have been explored [25–32].
We consider the following channel learning task, see also Figure 1. Let N be an unknown quantum channel, describing the evolution of a quantum system. In order to learn the behavior of the channel, we can prepare our system in a state of our choice, let it evolve according to the channel N, and then measure the output. The input state and measurement constitute a “test” for the quantum channel, and the probability of “passing” the test is given by Tr[)], where
is the input state and M is the measurement operator corresponding to passing the test. Tests of this type are ubiquitous in real-world physical setups used to learn the dynamics of quantum systems, see, e.g., Refs. [7, 9, 33–35]. Our task is to accurately predict values of quantities of the form
)] for test pairs
), and in this sense “learn” the evolution of the system.
In the typical setting of supervised learning used to achieve our task of interest, there is a training phase, in which a set of pairs of tests and their passing probabilities is given to the learner, and the learner uses these tests to form a hypothesis for the unknown channel. This hypothesis should accurately predict passing probabilities on new, unseen tests, typically drawn from the same distribution that generated the tests during training. Learning algorithms in this setting are analyzed within the framework of PAC learning [36]. In this work, we go beyond the setting of PAC learning. Instead of the data pairs (x, f(x)) being given to the learner in a batch, we suppose that they are given to the learner sequentially, one by one, and perhaps even in an adaptive and adversarial manner. The learner must produce a hypothesis for the unknown channel at every step, using which they estimate the passing probability of the test pair. Upon learning the true passing probability, they can update their hypothesis. The goal now is for the learner to devise a sequence of hypotheses such that, over time, they make few mistakes in their estimates; see Section 1.1 for a more formal description of this setting.
The framework of online learning [37] (see, e.g., Refs. [38, Chapter 21] and [39, Chapter 8] for pedagogical introductions) has been developed precisely to address this arguably more realistic learning setting. After all, data will often be processed sequentially, and it only makes sense to update the hypothesis step by step. Indeed, the importance of online learning derives from its ability to describe scenarios in which data is presented to the learner sequentially and adaptively. Thereby, it removes assumptions on the data-generating process, such as the i.i.d. assumption typical in PAC learning [36]. As such, it provides a more stringent type of learning compared to PAC learning. In fact, broadly speaking, it has been shown that online learning implies PAC learning [40–44]. Furthermore, if the learning algorithm is allowed unbounded computational resources, then something stronger holds: any concept class of Boolean functions is learnable in the online model if and only if is also learnable in the (distribution-free) PAC model [45].
While online learning of quantum states has been considered already [20, 21], and it has also been lifted to shadow tomography of quantum states with adaptively chosen observables [16, 17], the overwhelming majority of results on quantum process learning so far do not allow for accurate predictions based on an adaptive choice of the state-measurement pairs. To fill this gap, we initiate the study of online learning for quantum processes. We first show that general quantum channels cannot be online learned with subexponential regret or number of mistakes. However, a priori knowledge about the complexity or the structure of the unknown channel can make online learning feasible. Indeed, we identify two physically relevant classes of channels—efficiently implementable channels and Pauli channels—that can be online learned with regret and mistake bounds scaling polynomially in the system size. We extend these results to classes of more general multi-time processes, in particular quantum processes that are non-Markovian, establishing that they, too, can be online learned with regret and mistake bounds scaling polynomially in the system size.
1.1 Statement of the problem
Consider an interaction between a learner and an adversary. At time step , the adversary picks a state-measurement pair, (
), where
is an input state and
is an effect operator of a two-outcome POVM. More generally, we can allow for states and measurements with arbitrary auxiliary systems, as in Figure 1(c) (see Section 2.4). The task for the learner is to predict Tr[
)] for an unknown channel N. To do so, the learner produces their own channel hypothesis,
, and outputs Tr[
)] as their prediction. The adversary then provides the learner with feedback on what would have been the correct expectation value
. The goal of the learner is to ensure that their output values are not too far from correct in most rounds of the interaction. We can quantify the loss suffered by the learner at time step t by the absolute difference between learner’s estimate of the expectation value and the correct expectation value,
The learner-adversary interaction proceeds for a total of
Now, how do we measure the learner’s performance over the course of T rounds of its interaction with the adversary? Note that due to the adversarial nature of the problem, statistical extrapolations are of little use. Indeed, as soon as the learner models the interaction using some probability distribution, the adversary can immediately change their strategy to make the learner fail. One way to gauge the learner’s performance is to compare their total loss at the end of the T rounds of interaction with the loss that they would have incurred if they were allowed to make all predictions at the end of the T rounds, after having seen all of the state-measurement pairs. We do this by considering the quantity
where the minimization is over channels N from some class of interest. The larger this quantity, the more the learner would lament their choice of hypotheses at the end of the T rounds; hence, this quantity is called regret. It is well-known [46] that any online learner suffers Ω(
) regret in general. We aim for online learners that saturate this lower bound and achieve a regret scaling as
is the dimension of the quantum system acted on by the channel.
Another intuitive way to evaluate whether the learner’s performance is “good” is in terms of the number of rounds ] in which the learner makes a mistake. By a “mistake”, we mean that the learner’s estimate of the expectation value is more than a given accuracy
away (in absolute-value distance) from the correct expectation value revealed by the adversary. In other words, the learner should minimize the number of rounds in which
. More formally, we say that the learner makes an
-mistake in round t if
. Viewed this way, the goal in online learning is to upper bound the number of
-mistakes for any number T of rounds and any adversarial/adaptive choice of state-measurement pairs presented to the learner. This is the so-called mistake-bounded model of Littlestone [37]. In our work, we more specifically are interested in online learners that incur a mistake bound scaling logarithmically with D and inverse polynomially in the accuracy
for, ideally, a low-degree polynomial.
1.2 Overview of the main results
For the task of online learning arbitrary n-qubit quantum states, it was shown in Ref. [20] that there exist procedures that make at most linearly-in-n many mistakes. (Here, for ease of presentation, we consider to be a constant, say 1/3, and then simply speak of a mistake instead of an
-mistake.)
Table 1: Overview of our main results. For channels of gate complexity G as well as for n-qubit Pauli channels, we give regret and mistake upper bounds that scale favorably with G and n, respectively. Our bounds hold for general loss functions with Lipschitz constant L. Additionally, complementary mistake lower bounds show that the dependencies on G and n are almost optimal. Finally, we give computational complexity lower bounds for online learning either of the two classes of channels with polynomially many mistakes.
In terms of channel learning, this implies the same mistake bound for online learning arbitrary n-qubit state-preparation channels. However, as pointed out in Ref. [15, Footnote 18] and as we formalize further in Section 4.1, if the underlying concept class consists of all n-qubit unitary channels, then any (even computationally unbounded) online channel learner can be forced to make exponentially-in-n many mistakes. Thus, in contrast to the case of quantum states, we have to consider restricted classes of channels to achieve online channel learning with a polynomial-in-n number of -mistakes. In fact, it was left open in Ref. [15] to find restricted classes of quantum channels for which this goal, which is an online version of “pretty good process tomography”, can be realized. While recent years have seen some progress on the batch version of this task, see, e.g., Refs. [47–50], the online case remains open.
In this work, we answer the question of pretty good process tomography within the online learning framework for the following two concrete classes of channels (see Table 1 for a summary of our results):
1. Channels that can be implemented by dissipative quantum circuits with a limited number of local gates. Channels in this class can be regarded as having limited complexity.
2. Pauli channels or, more generally, mixtures of a fixed set of (potentially exponentially many) known channels, each of which could have arbitrarily high gate complexity. This is a structural assumption on the channel.
First, we show that there exists an online learner whose regret and number of mistakes can be controlled in terms of the gate complexity of the class of channels to be learned.
Theorem 1 (Online learning channels of bounded complexity—informal). The class of n-qubit channels that can be implemented by circuits consisting of G arbitrary two-qubit channels can be online learned with regret bound -mistake bound
Theorem 1 extends beyond the absolute-value loss function from Equation (1.1) to more general loss functions, in which case our bounds depend also on their Lipschitz constant L. General channels require exponentially many gates to be implemented by a 2-local circuit, so Theorem 1 does not provide useful guarantees in this case. However, if we focus on the physically relevant class of channels with a polynomial gate complexity, then Theorem 1 gives polynomial regret and mistake bounds. Additionally, we show with an O(1)-mistake lower bound of Ω(min) for general G and of Ω(G) for
that the G-dependence in the online learning guarantees of Theorem 1 cannot be significantly improved (Corollary 37).
Second, we prove regret and mistake bounds for Pauli channel online learning that scale efficiently in the number of qubits. Pauli channels play an important role in quantum information theory, specifically in the field of quantum computation, where Pauli channel noise either naturally emerges or is achievable via group twirls [51]. Thus, the following result establishes adaptive/online learnability of an important class of quantum noise channels.
Theorem 2 (Online learning Pauli channels—informal). The class of n-qubit Pauli channels can be online learned with regret bound -mistake bound
The linear-in-n scaling in the -mistake bound is optimal for constant
(Corollary 39). Moreover, establishing a connection to important notions from classical learning theory, we demonstrate that Theorem 2 yields bounds on the (sequential) fat-shattering dimension of Pauli channels, and gives rise to a sample compression scheme for Pauli channels (Section 3.4).
Theorems 1 and 2 give favorably scaling regret and mistake bounds. However, the respective online learning procedures are computationally inefficient. We show that, under reasonable cryptographic assumptions, this is unavoidable when aiming for good regret and mistake bounds in these online learning problems:
Theorem 3 (Computational lower bounds for online learning—informal). On the one hand, any online learner that makes at most O(poly(n)) many (1/3)-mistakes in online learning n-qubit Pauli channels has to use runtime exponential in n. On the other hand, assuming that RingLWE cannot be solved by classical polynomial-time algorithms, then already for G = O(npolylog(n)) there is no polynomial-time online learner that makes at most O(poly(n)) many (1/3)-mistakes in online learning G-gate n-qubit quantum channels.
While the computational inefficiency of our online learning procedures is of course undesirable, Theorem 3 shows that this is not a flaw of our specific procedures. Rather, it is simply not possible to computationally efficiently learn Pauli channels with a good mistake bound. And given that RingLWE is widely believed to be hard [52–54], then as soon as G scales only slightly superlinearly in n, we also do not expect there to be any computationally efficient online learners that achieve a good regret for the class of G-gate channels.
A problem related to online learning quantum processes is shadow tomography of quantum processes. By analogy with shadow tomography of quantum states [16, 17], shadow tomography of quantum processes is a stricter form of learning than mistake-bounded online learning: while in the online learning task the number of mistakes should be bounded, in shadow tomography one has to correctly estimate (i.e., with error ) the expectation values of all the M observables provided, with probability at least 1
. (See Problem 3 for a formal statement of the problem.) Furthermore, in shadow tomography, only quantum access to the channel is provided, while classical descriptions of tests and their passing probabilities (with respect to the unknown channel) are provided in online learning. The main observation underlying our proof of Theorem 2 implies that techniques from classical adaptive data analysis [55, 56] directly carry over to Pauli channel shadow tomography. In particular, we obtain the following result.
Theorem 4 (Pauli channel shadow tomography—informal). Shadow tomography of an arbitrary n-qubit Pauli channel can be solved using
copies of the channel. The strategy runs in time poly(4) per channel use.
We leverage Theorem 4 to make a more general statement about shadow tomography of arbitrary channels. In particular, we show in Corollary 49 that we can solve the shadow tomography problem for an arbitrary quantum channel N with a number of copies scaling as in (1.3), with therein replaced by
is the Pauli-twirled version of N.
1.3 Extensions of our results
Many of the techniques underlying our main results in Section 1.2 can be applied to more general settings, going beyond G-gate channels and Pauli channels. We now summarize these extensions.
Convex mixtures of known channels. While Theorem 2 is phrased for Pauli channels, we in fact show the following more general statement: If we consider a class of channels that can be written as probabilistic mixtures of a fixed set of K known quantum channels, then we can achieve online learning for this class with regret and number of mistakes bounded in terms of log(K). Notably, these bounds apply even if channels with high circuit complexity occur in the mixtures.
Theorem 5 (Online learning convex mixtures of known channels—informal). Given an arbitrary set of K > 0 known and fixed quantum channels, any convex mixture of these channels can be online learned with regret bound -mistake bound
Adaptive tests of channels. We may also want to learn the passing probabilities of more general channel tests that make use of the channel multiple times, perhaps adaptively. Such tests have the form shown in Figure 2(a). We can directly import results about convex mixtures of known
Figure 2: Extensions of our results to general quantum processes. (a) Going beyond one use of a channel N, as shown in Figure 1, we may want to learn the value of the channel on tests that make multiple, adaptive uses of the channel. Shown are three independent uses of N, whose Choi representation is C(N). (b) We can similarly perform adaptive tests of a non-Markovian process , characterized by the blue quantum comb, with Choi representation
). The generalized Born rule [57] tells us that the outcome probabilities of measurements, or “tests”, of quantum channels and multi-time quantum processes can be determined by an analogue of the usual Born rule for quantum states, in which the Choi representation takes the place of the quantum state, and the test is characterized by operators
that are generalizations of effect operators for quantum states. (See Section 2.1 for details.)
channels to this setting. Indeed, given a channel that is a convex mixture of known channels
, it holds that
This is itself a convex mixture of known channels, so Theorem 5 applies and yields regret and mistake bounds scaling with k log(K). We note, however, that Theorem 5 in this scenario will generally not give a proper online learner. Namely, the learner’s hypotheses will be (nk)-qubit channels given by convex combinations of
, which in general cannot be factorized into k copies of a single n-qubit channel.
Non-Markovian quantum processes. At the heart of the quantities that we aim to estimate is Born’s rule [58], which tells us that the expected value of an observable (Hermitian operator) H for a quantum state is given by Tr[
]. The Born rule generalizes not only to quantum channels but also to multi-time/non-Markovian quantum processes [57, 59], where we model multi-time processes mathematically as “quantum combs” [57], also called “quantum strategies” [60]; see also Refs. [61–63]. Within the framework of quantum combs, the Choi representation of the process takes the place of the state
and the observable H is replaced by a generalized “process observable” O; see Figure 2(b). We provide formal definitions of quantum combs and process observables in Section 2.1. Consequently, we can readily translate our results on bounded complexity channels and convex mixtures of known channels to bounded complexity non-Markovian processes and convex mixtures of known non-Markovian processes. While full tomography of multi-time/non-Markovian processes has been considered [64], to the best of our knowledge, the restricted tomographic setting that we consider here has so far not been considered for multi-time quantum processes.
We start by considering multi-time processes of bounded complexity. We formally define these processes by analogy with quantum channels of bounded gate complexity in Section 3.3. We can then extend Theorem 1 as follows.
Theorem 6 (Online learning multi-time processes of bounded complexity—informal). The class of n-qubit multi-time processes with complexity parameter G can be online learned with regret bound
We also extend Theorem 5 to an online learning result for convex mixtures of arbitrary known multi-time processes.
Theorem 7 (Online learning of convex mixtures of known multi-time processes—informal). Given an arbitrary set of K > 0 known and fixed quantum multi-time processes, any convex mixture of these processes can be online learned with regret bound and
-mistake bound
Finally, we extend the shadow tomography result of Theorem 4 to arbitrary multi-time processes. Here, the shadow tomography problem for multi-time processes is defined analogously as for channels; we refer to Problem 4 for the formal problem statement.
Theorem 8 (Shadow tomography of multi-time processes—informal). Shadow tomography of an arbitrary n-qubit multi-time process with time steps can be solved to accuracy
copies of the process, where N is the Choi representation of the process, is the Choi representation of the Pauli-twirled version of the process, and
is the strategy r-norm.
1.4 Related work
Online learning of quantum states. Ref. [20] introduced the problem of online learning quantum states and proposed three conceptually different approaches that all achieve mistake bounds scaling linearly in the system size. Recently, Ref. [21] investigated an adaptive variant of this online learning problem, in which the underlying state may change over time. A notable application of online state learning is its use as a subroutine in recent shadow tomography protocols [16, 17, 65].
A natural question to ask is whether we can simply apply known results on online learning quantum states to the Choi state of the unknown channel to accomplish the channel online learning task laid out above. This is certainly possible; however, we aim to predict quantities of the form Tr[)]. And while Choi states are efficiently (online) learnable, the so-called “Choi-to-channel” translation incurs a dimension factor:
where is the Choi matrix of
is the Choi state of N, and A and B are the input and output systems, respectively, of N; see Section 2.1 for formal definitions. Because of the dimension factor in the right-most equality above, we have
Consequently, good regret and mistake bounds for online learning the Choi state do not give rise to good regret and mistake bounds for online learning the channel. In Section 2.5, we discuss this and further issues arising when merely applying quantum state learning algorithms from Ref. [20] (such as the matrix multiplicative weights (MMW) algorithm) to the Choi state for channel online learning. In particular, noting that the MMW algorithm for online learning quantum states cannot be directly applied to the learning of Choi states (due to the fact that Choi states have an additional partial trace requirement), we provide a projected MMW algorithm that can be used to learn the Choi state, along with the associated regret bound analysis.
Learning channels of bounded complexity. With general quantum channels being impossible to learn in many scenarios, recent work has investigated the learnability of channels with bounded gate complexity in different settings. In variational quantum machine learning, a variety of works derived bounds on learning-theoretic complexity measures, and hence the sample complexity sufficient for good PAC generalization bounds, in terms of the number of gates [48–50, 66–69]. For learning classical-to-quantum mappings, Refs. [70–72] gave similar-in-spirit sample complexity bounds derived from gate complexity assumptions. Finally, Refs. [25, 32] considered different scenarios of state and process learning under assumptions of limited gate complexity.
Learning Pauli channels. Pauli channel learning has been considered in different (mostly nononline) scenarios. Ref. [73] gave procedures for approximating the Pauli error rates of a general unknown Pauli channel in different norms, with a recent improvement for the
norm in Ref. [74]. Ref. [75] proved that the query complexities achieved by these procedures are optimal among non-adaptive incoherent strategies, and also gave lower bounds for adaptive incoherent strategies. If the Pauli noise is known to have a local structure, the query complexity can be improved beyond the results of Refs. [73, 76], even if the conditional independence structure is not known in advance [77]. Refs. [78–80] highlight the importance of auxiliary systems and entanglement in learning the eigenvalues of an unknown Pauli channel. In Ref. [81], the authors provide an online algorithm for learning the eigenvalues of a Pauli channel
, while in this work we consider the task of learning the error rates of Pauli channels. Finally, Ref. [29] investigates the more general task of learning the Pauli transfer matrix of a general channel, giving both non-adaptive and adaptive procedures.
1.5 Techniques and proof overview
Sequential covering numbers. In our proof of Theorem 1, we combine tools from two recent lines of work in classical online learning and quantum machine learning. On the one hand, we rely on regret bounds for online learning in terms of sequential complexity measures for the underlying hypothesis class. In particular, we use regret bounds via sequential covering numbers [82, 83], which can be viewed as a sequential version of Dudley’s theorem. Namely, as we recall in Theorem 11,
where 2) denotes the worst-case sequential 2-norm
-covering number of
all complete binary trees x of depth T whose nodes are labeled by elements of X. On the other hand, for the class of channels with a given gate complexity G, we invoke covering number bounds with respect to the diamond norm distance [25, 32, 68], and we demonstrate that these also control sequential covering numbers. Concretely, in Corollary 19, we show that
where denotes the class of n-qubit channels with gate complexity G. Together, these results imply the regret bound from Theorem 1. This in turn leads to the claimed mistake bound via a standard argument (see Lemma 12).
Online convex optimization. Theorem 2 is based on efficient mistake-bounded learning of a convex mixture of exponentially many known channels. A simple but crucial observation is that the only unknown about such channels is a classical probability distribution p (for example, in the special case of Pauli channels, the Pauli error rate distribution). Consequently, online learning of these channels corresponds to online learning of p when the input states and the measurements (on the output state evolved by the unknown channel) are adversarially revealed to the learner. We show that this task can be achieved via an alternative online learning scenario, in which any adversarially chosen state and measurement can be encoded in a ‘channel observable’ when revealed to the learner is associated to a “challenge” vector
where )
, and Γ
is the Choi representation of the Pauli unitary channel
. The learner produces hypotheses
of the unknown probability distribution at times
. The learner’s hypotheses should be such that, for
,
is not too different from
. Using known guarantees [84], the difference between these two sums can be shown to scale only logarithmically with the size of p’s support for the multiplicative weights update method. This implies regret bounds, and therefore mistake bounds, that scale only linearly in the number of qubits.
Mistake lower bounds. We prove our lower bounds by embedding classical online learning problems into the quantum tasks of interest, thereby inheriting classical lower bounds. First, it is easy to embed the task of online learning a general function into that of online learning a general n-qubit unitary. (Alternatively, when allowing for non-unitary channels, we give such an embedding into (
1)-qubit channels.) Thus, the folklore mistake lower bound of Ω(2
) for the former problem immediately carries over to the latter, showing that the class of all n-qubit unitaries cannot be online learned with a sub-exponential number of mistakes.
Second, to prove mistake lower bounds for learning channels of gate complexity G, we use the fact that ) many gates suffice to implement an arbitrary function
with a classical circuit. We can quantumly realize such a circuit either by first measuring in the computational basis and then applying the classical circuit, or by implementing irreversible AND and OR gates with reversible Toffoli gates, where the auxiliary system gets reset to a suitable value after every gate. Both constructions demonstrate that the class of n-qubit channels of gate complexity G contains the class of all Boolean functions on the first
(Θ(
inputs (extended to the remaining subsystems by a trivial action). So, the classical folklore lower bound gives an Ω(2
) mistake bound here.
Third, by associating a general function -qubit Pauli channel
given by
, we prove that online learning n-qubit Pauli channels is at least as hard as online learning a general {0, 1}-valued function on
bits. Hence, the classical mistake lower bound for online learning arbitrary functions becomes a Ω(n) mistake lower bound for Pauli channel online learning.
Computational complexity lower bounds. Our exponential computational complexity lower bound for online learning Pauli channels with a polynomial mistake bound is a simple formalization of the following intuition: The channel observables posed as challenges by the adversary are exponentially-sized objects, and a successful online learner has to process all the exponentially many entries. We give a simple adversary demonstrating that this intuition is correct, and applies even if the adversary provides the channel observables already in the basis expansion that is most natural for Pauli channels, namely the (unnormalized) n-qubit Bell basis.
To prove our computational complexity lower bound for online learning bounded-complexity channels, we require a hardness assumption. Here, we consider the so-called ring learning with errors (LWE) problem [85] (RingLWE), which underlies much of lattice-based cryptography. To establish that hardness of RingLWE implies hardness of online learning slightly superlinear-sized quantum circuits, we first show, via a known construction, that this class of quantum circuits can implement a pseudorandom function class. This implies hardness of online learning, because pseudorandom function classes are hard to learn, an intuition that we formalize specifically for mistake-bounded online learning. Importantly, as the hardness arises from an underlying classical pseudorandom function class, it persists even when all challenges consists of input states and projective effect operators that are computational basis elements. In particular, online learning remains hard here, even though the learner can efficiently read all challenges. Additionally, as our pseudorandom function class is secure against adversaries that have query access to the function, the computational hardness of online learning holds even if the learner can actively choose the (pairwise distinct)
challenges, rather than those being chosen by the adversary.
Classical adaptive data analysis. In the problem of shadow tomography of quantum channels, the learner’s task is to output values such that
)]
for all
, where
)
is a set of state-measurement pairs. They should do so while minimizing the number k of times that they access the channel. The shadow tomography problem for multi-time processes is formulated in a similar manner.
Our shadow tomography results are based on Bell sampling of the Choi state of the channel, i.e., sending one-half of the maximally-entangled state through the channel and then performing a joint Bell-basis measurement on the output system and the second entangled copy of the input system. If the unknown channel is a Pauli channel, then this procedure directly gives us samples from the Pauli error rate distribution. Consequently, the desired expectation values Tr[be interpreted as (classical) statistical queries with respect to the (unknown) Pauli error rate vector. Specifically, we have that Tr[
is the Pauli error rate vector and
[((
)
)Γ
]. With this observation, we can make use of the classical adaptive data analysis algorithms presented in Ref. [56] in order to obtain our bound in Theorem 4 on the number k of accesses to the channel. For an arbitrary unknown channel, we show that the same Bell sampling strategy enables us to sample from the error-rate vector of the Pauli-twirled version of the channel, which we denote by
. Then, as long as
we obtain a similar guarantee as in Theorem 4.
Quantum combs. Our results on multi-time quantum processes make use of theory of quantum combs [57], also known as “quantum strategies” [60]. We provide formal definitions of quantum combs in Appendix B. In particular, the analysis of multi-time processes entails use of the so-called “strategy norm” and its Hölder dual [86], which are the multi-time generalizations of the trace and spectral norm, respectively, used in the analysis of algorithms for quantum states. They also generalize the diamond norm and its Hölder dual in the case of quantum channels. A crucial ingredient in the proof of Theorem 6 is submultiplicativity of the strategy norm under composition of multi-time processes. As the composition of multi-time processes is given by the link product [57], the technique for proving submultiplicativity of the diamond norm does not generalize straightforwardly to the strategy norm. To the best of our knowledge, a proof of submultiplicativity of the strategy norm under link product has not been provided before, and we provide such a proof in Appendix B.2 based on semi-definite programming duality.
1.6 Directions for future work
Motivated by the well known impossibility of online learning general unitaries and channels with a subexponential number of mistakes, our work initiates a study of subclasses of channels that allow for good regret and mistake bounds in online learning. We have identified two such classes: Channels of bounded gate complexity and mixtures of arbitrary known channels, with Pauli channels as a notable special case. However, we show that achieving favorably scaling regret and mistake bounds for these classes is not possible in a computationally efficient manner. Our results open up several directions for future research; here we outline some of them.
First, while our computational complexity lower bounds put limitations on where we can hope for computationally efficient channel online learning, they still leave relevant regions to explore. On the one hand, by the same reasoning as in Section 5.2, the channel class under consideration must not be expressive enough to implement known pseudorandom function constructions. Here, inspired by the recent work [87], one may investigate the online learnability of shallow quantum circuits. On the other hand, as we argue in detail in Section 5.1, a necessary condition for efficient online learning is that the channels of interest admit efficient descriptions. Candidates for such channel classes may be Clifford circuits or channels represented by matrix product operators of low bond-dimension.
Second, we believe that there is room for “onlinification” of other quantum learning scenarios. For instance, recent work [28, 29] has proposed to avoid the exponential bottleneck of general process tomography (compare, e.g., Refs. [13, 14]) by considering learning tasks with arbitrary channels but restricted or structured input states and output measurements. Similarly, one may attempt to circumvent exponential lower bounds in online learning arbitrarily complex channels by imposing restrictions on the behavior of the adversary, for instance, with respect to the challenges that they can pose. Another line of quantum learning research that has recently seen significant progress is learning a Hamiltonian from access to the associated dynamics [29, 88–100]. Online learning variants of the standard Hamiltonian learning task could give insights into whether one can learn to fine-tune a Hamiltonian evolution according to adaptive feedback.
Finally, while general shadow tomography for quantum channels is not possible, we have demonstrated that it can become feasible for a suitable subclass, in our case Pauli channels. Given the important role of online learning quantum states in state tomography procedures, we envision positive results, both ours and future ones, on online learning restricted classes of channels to serve as a stepping stone towards shadow tomography procedures for such classes. Achieving the latter would likely require analogues of threshold search [17] for these kinds of channels.
Acknowledgments
The authors thank Akshay Bansal, Ian George, Soumik Ghosh, Jamie Sikora, and Alice Zheng for sharing a draft of their independent and concurrent work on online learning quantum objects. The authors gratefully acknowledge support from the BMBF (QPIC-1, HYBRID), the ERC (DebuQC), the Munich Quantum Valley, the Einstein Foundation, and Berlin Quantum. MCC was partially supported by a DAAD PRIME fellowship.
Table of Contents
1 Introduction 1
1.1 Statement of the problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Overview of the main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Extensions of our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Techniques and proof overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6 Directions for future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Preliminaries 16
2.1 Basics of quantum information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Basics of online learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 The multiplicative weights framework and corresponding guarantees . . . . . . . . . 25
2.4 Problem statement: Online learning classes of quantum channels . . . . . . . . . . . 27
2.5 Obstacles to online learning via the Choi state . . . . . . . . . . . . . . . . . . . . . 28
3 Online learning upper bounds 30
3.1 Regret bound for channels of bounded gate complexity . . . . . . . . . . . . . . . . . 30
3.2 Regret bound for mixtures of known channels . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Regret bounds for multi-time processes . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4 Learning-theoretic implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Mistake lower bounds 45
4.1 Mistake lower bounds for general unitaries and channels . . . . . . . . . . . . . . . . 45
4.2 Mistake lower bounds for channels of bounded complexity . . . . . . . . . . . . . . . 47
4.3 Mistake lower bounds for Pauli channels . . . . . . . . . . . . . . . . . . . . . . . . . 48
5 Computational complexity lower bounds 49
5.1 Computational complexity lower bounds for Pauli channels . . . . . . . . . . . . . . 49
5.2 Computational complexity lower bounds for channels of bounded complexity . . . . 51
6 Shadow tomography of quantum processes 55
6.1 Shadow tomography of multi-time processes . . . . . . . . . . . . . . . . . . . . . . . 57
Bibliography 60
A From qubits to qudits 69
B Multi-time quantum processes 71
B.1 Definitions and basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
B.2 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
C Pauli-twirl of quantum channels 76
D Entropic analysis of the MMW algorithm 78
D.1 Proof of Proposition 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
D.2 The projected MMW algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
2.1 Basics of quantum information
Here we provide a brief review of fundamental quantum information concepts that we make use of throughout this work. We refer to, e.g., Ref. [101] for further details on the concepts and definitions presented in this subsection.
Pauli operators. For a quantum system of qubits, we define the n-qubit Pauli operators as
where the operation “” denotes addition modulo two. From this, we can define the n-qubit Bell states as
for all . The Bell state vectors
form an orthonormal basis for (
and the set
positive operator-valued measure (POVM).
Quantum channels. A quantum channel is a completely positive trace-preserving (CPTP) linear map ). We often write
to refer to a quantum channel with input system A and output system B, with corresponding Hilbert spaces
, respectively. We let CPTP(A; B) denote the set of all quantum channels mapping system A to system B. In this work, we mostly consider the case
, corresponding to a system of n qubits, and we use the notation
to refer to the set of all quantum channels mapping n qubits to n qubits.
The Choi representation (or Choi matrix) of a linear map ) is defined as
where id) is the identity superoperator, and
The Choi state of N is the normalized Choi matrix, defined as
We sometimes write ) for the Choi matrix and Choi state, respectively, of a quantum channel
when we want to indicate explicitly the input and output systems A and B of the channel. For a quantum channel
, its Choi representation
is positive semi-definite and satisfies Tr
The function C defined in (2.5) has an inverse, such that we can identify every Hermitian operator ) with a Hermiticity-preserving map
In particular, if is positive semi-definite, then
is completely positive. If in addition Tr
, then
is a quantum channel. Consequently, the set CPTP(A; B) of quantum channels is in one-to-one correspondence with the set
) :
L(
) :
denote the set of Choi matrices of quantum channels mapping n qubits to n qubits.
Quantum channels also have a Kraus representation, such that
where is a linear operator for every
Pauli channels. A Pauli channel is a quantum channel whose Kraus operators are proportional to the Pauli operators defined in Equation (2.1). Specifically, an n-qubit Pauli channel (by definition) has the form
where the Pauli error rates form a probability distribution, i.e.,
1] for all
and
where
are the unnormalized versions of the n-qubit Bell states defined in Equation (2.4). We let ) denote the 4
-dimensional probability vector of error rates.
We let be the set of all Pauli channels acting on n-qubit systems, and analogously to (2.9), we let
be the set of all Choi matrices of Pauli channels, where
denotes the probability simplex of elements. Depending on the context, we refer to a vectors
) with values
probability vector and a probability distribution.
Associated to every quantum channel N is its Pauli-twirled version, defined as [102]
where the superscript “P” in refers to the set
:
of n-qubit Pauli operators. In other words, the Pauli-twirled version of a channel is given by applying a Pauli operator, chosen uniformly at random, and its inverse at the input and output of the channel. As we recall in Appendix C, the Pauli-twirled channel
is indeed a Pauli channel, and the error rates are given by
. In particular, we show that the Choi representation of the Pauli-twirled channel can be obtained via the pinching channel
in the Bell basis, defined as
for every linear operator L((
). In particular, then, the Choi representation of the Pauli-twirled version
of a channel N is given by
Channel measurements and observables. An m-outcome measurement of a quantum state is given by a positive operator-valued measure (POVM), i.e., a set operators satisfying 0
such that
. Observables for states are simply Hermitian operators H, and the expected value of the observable H when measured on a state
Now, a measurement, or a test, for a quantum channel is given by a pair consisting of a bipartite state
and a POVM
, where R is an arbitrary memory/reference system; see Figure 2(a). Using Equation (1.6), the probability of obtaining a particular outcome
of the test is given by
where )] for all
. The right-hand side of this equation is the generalized Born rule for quantum channels; see Figure 1(c) for a depiction. The channel test operators
satisfy
0 for all
and
, where
]. The converse is also true [59, 103], meaning that every channel test can be characterized by a set
such that 0
for all
, for some density operator
, and
. The corresponding “physical realization” of the channel test is given by
is a purification of
An especially simple example of a channel test is one without memory, involving an input state the input of the channel and a measurement
at the output of a channel; see Figure 1(b). In this case, the channel test operators are in tensor-product form, given by
all
The statements above for measurements readily generalize to statements about observables (Hermitian operators), due to the fact that every Hermitian operator has a spectral decomposition, and the spectral projections form a POVM. Consequently, the expected value of an observable measured according to the general scenario depicted in Figure 1(c), is equal to
where the “channel observable” is )]. If the measurement scheme does not contain a memory, then
Let us now consider the case that the memory system R has the same dimension as the input system A of the channel, so let us make the relabeling . Let us also suppose that
is a pure state. Then, for every bipartite pure state
, there exists a state
such that
Note that a special case of the observable in Equation (2.22) is when , which corresponds to measuring
on the Choi state of the channel. In this case
which means that
Now, the operator/spectral norm is used to characterize measurement operators and observables for quantum states, because it is the (Hölder) dual to the trace norm
. For quantum channels, the relevant norm is the diamond norm [104]. Let N : L(
L(
) be a Hermiticity-preserving linear map. The diamond norm of
can be expressed as
The norm is referred to as the strategy 1-norm, and we define it formally in Appendix B. The relevant norm for channel observables is thus the Hölder dual of the strategy 1-norm, which is given by [86, 105]
for every Hermitian operator . We note that channel test operators satisfy
1. Also, for channel observables without memory, it holds that
as we might expect, and which is a property interesting in its own right; we refer to Appendix B for a proof. In general, we have that for all Hermitian
L(
). This follows immediately from (2.26), on account of the fact that
1
for every
in the optimization in (2.26), and the fact that
:
for all Hermitian
Multi-time quantum processes. Multi-time quantum processes are those that occur over multiple time steps, as opposed simply one time step for a quantum channel. A simple example of a multi-time quantum process is the one depicted in Figure 2(a), in which the process (in blue) consists of three (independent) uses of a quantum channel N. In Figure 2(b), we depict in blue a quantum multi-time process with memory, which can model non-Markovian dynamics [61]. Measurements, or testers, for multi-time processes consist of an input state to the process, several (possibly adaptive) interactions with the process over multiple time steps, and finally a measurement. The testers are depicted as the red processes in Figure 2.
The mathematical objects describing multi-time processes and testers are known as quantum combs [57, 106] and quantum strategies [60], and we provide formal definitions of these objects in Appendix B. Briefly, quantum combs are multipartite operators that are defined as the Choi representations of multi-time quantum processes. For , such that the systems
are the input systems and
are the output systems; see Figure 2. Then, the set of quantum combs describing r-step multi-time quantum processes is defined as follows:
We suppress the system labels and simply write when the systems are unimportant or understood in the context being considered. For the process in blue in Figure 2(b), its Choi representation belongs to the set
. We also note that
. The set of inputs to multi-time processes, sometimes called co-strategies, are defined as the Choi representations of multi-time processes in which the first input system is trivial. Specifically, let
. Then, the set of inputs to multi-time processes is defined as
An example is the red process in Figure 2(b) (excluding the measurement), which belongs to the set . Again, we suppress the system labels and simply write
when the systems are unimportant or understood in the context being considered. Observe that every element of
is a positive semi-definite operator with unit trace. In particular, the elements of
are density operators, and we can think of them as multi-time analogues of quantum states.
The analogue of a POVM for multi-time processes, and thus the multi-time generalization of a channel test as we defined them above, is a mult-time tester: a set of positive semi-definite test operators
L(
) such that 0
for all
, for some
The multi-time analogues of the norms in (2.25) and (2.26) are the strategy r-norm and its Hölder dual, which can be expressed as [86]
for every Hermitian operator L(
). It holds that
for every Hermitian operator
L(
). For a multi-time test
with r time steps, it holds that every test
for all Hermitian
2.2 Basics of online learning
We view online learning a hypothesis class of functions as an interactive game between a learner and an adversary. In round t of the interaction, the adversary challenges the learner with an input
. Then, the learner predicts the output
based on their current hypothesis
(We focus on proper online learning, where
.) To conclude the round, the adversary provides the learner with feedback in the form of a loss
)), and the learner uses this piece of information to update
their hypothesis to
. For our purposes, the target space is Y = [0, 1] and every
: [0, 1]
is convex and Lipschitz. Specific losses of interest are often of the form
) for some convex and Lipschitz
: [0, 1]
[0
) and
[0, 1]; for example, this gives rise to the
-losses with
. In these cases, we assume that the adversary provides the loss
) by explicitly revealing the value of
is known in advance. Note that in general, the
here can be arbitrary. If there is an “approximately true” underlying concept
3 holds for all t, then we speak of a realizable scenario, otherwise we call the setting non-realizable.
Regret-bounded online learning. One way of phrasing desiderata in online learning is in terms of bounds on the difference between the incurred and the in hindsight optimal incurred loss, the so-called regret. Namely, after T rounds of interaction, we say that the learner has incurred a regret of
The goal of an online learner now is to achieve a small regret, in particular scaling sub-linearly with T. Note that this model makes sense even if no restrictions on how the adversary chooses the in the more concrete case of
-losses, the
above) are imposed.
We make use of the following lemma throughout this work.
Lemma 9 (Regret bound). Consider the online learning scenario described above, in which the functions are convex and differentiable. Then, for every
, it holds that
The regret in (2.33) is therefore bounded from above as
Proof. Since is convex and differentiable, it readily follows that
for all 1]. (See, e.g., Ref. [46, Chapter 2].) Consequently, for every
for all . Therefore,
The first inequality is (2.34). The inequality in (2.35) follows because the function is arbitrary.
Next, we recall results from Refs. [82, 83], which demonstrate how to obtain regret bounds in terms of sequential complexity measures of the hypothesis class. To formulate these results, we introduce the following pieces of notation: We use z with labeling functions z
to describe a complete rooted binary tree of depth T with nodes labeled by elements of Z. That is, if we arrive at a node by following a path
of length
1 from the root, then z assigns the label z
) to that node. For notational convenience, if
is a path of length
1, we identify z
). We can now introduce a notion of sequential covering to capture the effective size of a function class.
Definition 10 (Sequential covering numbers [82]). Let , let z
be a complete rooted binary tree of depth T, and let
0,
1. We call a set V of R-valued complete binary trees of depth T a sequential
if the following holds:
The sequential -covering number of G on z is defined to be
We write ), where the supremum is over trees of depth T.
Note that Definition 10 does not require a cover to consist of R-valued trees that can be realized within G. In that sense, the above notion is one of exterior covering. Also, it will be useful to observe that sequential covering numbers satisfy the monotonicity relation for 1
Similarly to how empirical metric entropies, defined as the logarithm of covering numbers, control the generalization error in probably approximately correct learning, sequential metric entropies, the logarithm of sequential covering numbers, can be used to bound the regret in online learning. This result goes back to Refs. [82, 83], we state it in a form similar to Ref. [20, Theorem 9].
Theorem 11 (Regret bound from sequential covering [83, Theorem 3] and [82, Theorem 7]). Let . For every
be convex and L-Lipschitz. Then, there exists an online learning strategy that, when presented sequentially with
and associated loss functions
, outputs a sequence
of hypotheses whose regret is bounded as
Here, the supis a supremum over all complete binary trees of depth T with nodes labeled by elements of X.
Mistake-bounded online learning. As an alternative to measuring the performance of an online learner in terms of regret, we can count the number of rounds in which the learner incurs a loss that exceeds a certain threshold. More formally, given (0, 1), we say that the learner makes an
-mistake in round t if
. The goal of the online learner then becomes to make only a small number of
-mistakes. Note that this mistake-bounded model of online learning only makes sense in the realizable scenario, since the number of
-mistakes is in general infinite in the non-realizable scenario.
To conclude our introductory discussion of online learning, we note a well known connection between the models of regret- and mistake-bounded online learning. Informally, we can say that good regret bounds lead to good mistake bounds, and the next result makes this formal.
Lemma 12 (From regret to mistake bounds (compare, e.g., Ref. [20, Section 3.3] or [107, Corollary 2.1.4])). Let . Suppose we have an online learner for F that is sequentially presented with
and losses evaluated according to
, where there exists
such that
3 holds for all t. For an update rule that results in a sequence
of outputs from the learner, suppose that the regret is bounded as
) +
), where
: (0, 1)
and
: (0, 1)
. Assume that
) for every fixed
, and that
) be the smallest natural number such that
Then, applying the update rule only in rounds in which the learner makes an -mistake, and outputting the previous hypothesis otherwise, leads to a total number of
-mistakes bounded by
independently of the overall number of rounds.
Notice that the online learning procedure achieving the mistake bound in Lemma 12 is mistake-driven: It updates the hypothesis only when an
-mistake is made. After a round without an
-mistake, the learner just proceeds without changing their hypothesis.
Proof. Let denote the number of
-mistakes (i.e., the number of updates) and let us focus on the subsequence of rounds in which the learner makes a mistake. First note that, by assumption, there is a function
such that the prediction
) achieves loss
3 for all t. Hence, the optimal accumulated loss after
rounds is
3. As the described procedure applies the update rule only when a loss
is incurred, this mistake-driven online learning procedure incurs an accumulated loss of
. Thus, its regret is
3. Comparing this with the assumed regret upper bound of
and rearranging, we see that
the definition of
, we conclude
2.3 The multiplicative weights framework and corresponding guarantees
In this section, we provide a brief overview of the multiplicative weights framework and refer to Ref. [84] for a more comprehensive review. This toolkit has a variety of applications in areas such as game theory and economics [108], machine learning [37, 109], and semidefinite programming [110, 111]. In quantum computing, the matrix multiplicative weights algorithm was used to prove that the complexity classes QIP (problems with a quantum interactive proof system) and PSPACE (problems solvable in polynomial amount of space) coincide [112].
Consider an interactive game, in which a learner is tasked with picking the best option from a set of decisions over
rounds of interaction. In each round 1
, every decision
is associated with a cost
1]. Upon making their decision, the learner is informed of the associated cost, which they can use to make their decisions in subsequent rounds. The learner’s goal is to output a sequence of decisions over the T rounds such that their total accumulated cost after T rounds is minimized.
In the multiplicative weights framework, the decision in round 1 is made according to a d-dimensional probability vector
). Explicitly,
is the probability of making the decision
. The expected cost of the distribution
is then
, where
) is the vector of costs. The expected accumulated cost after T rounds is thus given by
multiplicative weights update (MWU) algorithm, presented in Algorithm 1, is a method for obtaining a sequence of probability distributions over decisions based on the costs incurred in the previous rounds.
Arora, Hazan and Kale [84] have shown that if a learner makes their decisions according to the MWU algorithm, then their expected accumulated cost only grows logarithmically in d, the number of possible decisions.
Theorem 13 ([84, Theorem 2.1 & Corollary 2.2]). Consider the setting of an interactive game, as described above, with cost vectors satisfying
1] for all
and for all
be an arbitrary probability distribution over the d decisions. Using the MWU algorithm (Algorithm 1), the expected accumulated cost over
rounds is bounded from
above as
The matrix multiplicative weights (MMW) algorithm [110, 113] is a generalization of the MWU algorithm to costs specified Hermitian matrices
that satisfy
; equivalently,
1. Here, the decisions are described by density operators
, and the expected cost in round t is equal to Tr[
]. The MMW algorithm, presented in Algorithm 2, is a method for obtaining a sequence of density operators
, based on the costs incurred in the previous rounds.
A bound on the expected accumulated cost for the MMW algorithm has been shown in Ref. [110, Theorem 3.1]. By modifying the arguments in Ref. [110] via use of the relative entropy, we provide a bound on the expected accumulated cost for the MMW algorithm that can in general be tighter than the one obtained in Ref. [110, Theorem 3.1].
Proposition 14 (Bound on the expected accumulated cost for the MMW algorithm). Let be an arbitrary density operator. Let
be the number of rounds of interaction, and consider a sequence
of cost matrices in dimension
along with the updates
provided by the MMW algorithm in Algorithm 2. Then, the expected accumulated cost over the T rounds is bounded from above as
where ] is the von Neumann entropy of
Proof. See Appendix D, where we also describe how the bound in Ref. [110, Theorem 3.1] arises as a special case of our bound in Equation (2.44).
Remark 15 (The Hedge algorithm). If the cost matrices in the MMW algorithm are all diagonal in the same basis, then Algorithm 2 reduces to the so-called Hedge algorithm, introduced by Freund and Schapire [114]. We state this algorithm in Appendix D, and in Corollary 61 we state the Hedge algorithm counterpart to Proposition 14 above.
2.4 Problem statement: Online learning classes of quantum channels
Our task is to online learn a class -qubit quantum channels, in the sense of predicting the quantities Tr[
)], with the state-measurement pairs (
) provided by an adversary, where R is an arbitrary finite-dimensional reference system; see Figure 1. Let us now cast this problem in terms of the general framework of online learning laid out in Section 2.2.
We fix finite-dimensional Hilbert spaces . Then, the input set/domain X comprises state-measurement pairs (
is an arbitrary finite reference system. Equivalently, due to (2.19), X comprises channel test operators
. Precisely,
where in the second equality we have used Equation (2.26). The output set is Y = [0, 1], and F is defined by the subclass of n-qubit channels (in which case
), such that for every
we define the function
as
)] for all
. In other words,
Notably, due to Equation (2.19), we can see that our online learning task is equivalently formulated as the task of learning a class Choi matrices defined by the channels in C, where
We therefore view the adversary as providing channel test operators and having the learner predict the quantities Tr[
] based on hypotheses for the Choi matrix of the unknown channel. We denote the learner’s hypothesis Choi matrices by
As outlined in Section 2.2, we will evaluate the performance of an online learner in terms of either the regret or the number of mistakes. That is, on the one hand, the learner aims to achieve a small regret
where the losses are revealed by the adversary. More precisely, we will aim for regret bounds scaling as
). On the other hand, in the realizable scenario, where there exists a (to
the learner unknown) channel such that all losses take the form
where is some fixed function and each
satisfies
3, the learner aims to achieve a small number of
-mistakes. Here, our goal will be to guarantee mistake bounds scaling as
)). We can summarize the formulation of our channel online learning task as follows:
Problem 1 (Online learning classes of quantum channels). Consider a subset of n-qubit quantum channels, and let
, with Choi representation
, be unknown. Given a sequence of
interactive rounds, in which two-outcome channel test operators
are presented sequentially by an adversary, the problem is to output a sequence of Choi matrices
, such that for losses
as defined in (2.49), the regret in (2.48) scales as
) and the number of
-mistakes scales as
Remark 16. In this work, we primarily consider the case that the input system dimension and the output system dimension
are equal and satisfy
, although Problem 1 applies also to quantum channels with different input and output system dimensions. In particular, if
, then every channel is a state-preparation channel for some n-qubit quantum state, and Problem 1 reduces to online learning of quantum states, as considered in Ref. [20].
Remark 17. Successfully solving Problem 1 does not imply learning of the unknown channel with respect to the diamond norm, i.e., the learner’s hypotheses could be very far from the true Choi matrix
with respect to the strategy 1-norm in (2.25). In our scenario, the learner’s only goal is to ensure that their hypotheses are such that Tr[
] well approximates Tr[
in most rounds, and this can be achieved by hypotheses that are not necessarily close to the true Choi matrix with respect to the strategy 1-norm.
2.5 Obstacles to online learning via the Choi state
As pointed out above, the problem of online learning classes of quantum channels (Problem 1) is equivalent to the problem of online learning classes of Choi matrices. A natural first strategy for solving this problem might then be to simply online learn the Choi state of the unknown channel using the protocols presented in Ref. [20] for online learning of quantum states, such as the MMW algorithm (Algorithm 2). However, we immediately encounter two issues.
First, the MMW algorithm (Algorithm 2) cannot be applied out of the box: while Choi states Φof quantum channels
have unit trace, they also have to satisfy Tr
, which the iterates of Algorithm 2 will generally not guarantee. Furthermore, the proof of Ref. [110, Theorem 3.1], as well as the proof of Proposition 14 above, relies crucially on the fact that the iterates of the MMW algorithm have unit trace. So, potential modifications of the update rule would have to simultaneously ensure the unit trace and the partial trace conditions.
We can modify the MMW algorithm by adding a projection step: for every iterate MMW algorithm, we find the closest Choi state
with respect to relative entropy and use that
as our hypothesis for the unknown Choi state. In other words, we let
where ] and the relative entropy
) of two positive semi-definite operators P and Q is defined as [101]
We present the modified MMW algorithm in Algorithm 3. Then, because the relative entropy is a Bregman divergence [115], we can regard Algorithm 3 as a particular instance of the online mirror descent algorithm [46, Section 5.3]. Consequently, we obtain a regret bound for Choi states that is similar to the regret bound in Proposition 14, thus similar to the MMW regret bound in Ref. [20] for online learning of quantum states. We provide the details in Appendix D.2.
The second issue is that the above strategy of learning the Choi state of the unknown channel leads to favorable regret and mistake bounds, but only as long as we modify Problem 1 as follows: instead of predicting expectation values of the form Tr[is the Choi matrix of the unknown channel
, we aim to predict values of the form Tr[
Choi state of
. Now, because of Equation (1.6), we see that Tr[
Thus, even though we show that the
) regret bound of [20] carries over to (properly) online learning the Choi state, this implies only a regret bound of
) when it comes to our actual task of learning the Choi matrix (and thus the channel), which has a favorable square root scaling in T but an unfavorable exponential scaling in the number of qubits
3.1 Regret bound for channels of bounded gate complexity
In this section, we show online learnability for quantum channels of bounded gate complexitysay that a quantum channel N has (exact) gate complexity (at most)
[116, 117] if there exists a (not necessarily geometrically) two-local
quantum circuit with G two-qubit channels as gates that implements N. Such quantum channels include, for example, noisy quantum circuits modeled in terms of perfect two-qubit unitary gates followed by single-qubit noise channels. The set of n-qubit channels of gate complexity (at most) G is denoted by
. We abuse notation and also use
to denote the class of [0, 1]-valued functions on channel test operators that arises from G-gate channels as described in Section 2.4. We first bound the sequential covering numbers for (the [0, 1]-valued function classes associated to) such channels. Theorem 11 then gives us a regret bound, from which we can derive a mistake bound via Lemma 12.
The (interior) covering number of the set of quantum channels with gate complexity at most G is defined to be
The fact that quantum channels of bounded gate complexity also have bounded complexity in the sense of covering numbers has previously been observed in Refs. [25, 32, 67, 68]. We recall this insight and its proof in the following lemma.
Lemma 18 (Covering number bounds from gate complexity (see Refs. [68, Theorem C.2] and [32, Theorem 8])). Let (0, 1). The (interior)
-covering number of
with respect to
is bounded as
Proof. Let . From Ref. [68, Lemma C.2], we have that the covering number for the set of two-qubit channels is
If we consider the set of all possible channels that act on two out of n qubits, which we denote by , then the covering number of this set is given by
with the binomial factorcoming from the fact that we allow the two-qubit channels to act on any pair of qubits.
Let us now consider an arbitrary . By definition, every such channel has the form
, where
for all
. By definition of
), for every channel
, we can find a corresponding
in an
-covering net for
such that
. Then, the channel
satisfies
where we made use of the subadditivity-under-composition property of the diamond norm; see, e.g., Ref. [101, Proposition 3.48]. Therefore, if we let -covering net for
then the set
is an -covering net for
. Noting that
, we obtain
, for every
-covering net for
. As the covering number
) is, by definition, the size of the smallest
-covering net for
, we can conclude that
as required.
We now observe that Lemma 18 immediately implies similar sequential covering number bounds. In fact, this can be seen by a reasoning analogous to how Ref. [68] went from covering w.r.t. a norm on the level of the channel to empirical covering.
Corollary 19 (Sequential covering number bounds from gate complexity). Let and let
Proof. Because of Lemma 18 and the monotonicity of sequential covering numbers w.r.t. p, it suffices to show that ) holds for any complete rooted binary tree z of depth T. This follows immediately from the fact that, if
are two quantum channels, then
holds for any bipartite effect operator and for any bipartite state
We can now plug this sequential covering number bound into Theorem 11. This leads to the following regret bound for online learning channels of bounded gate complexity:
Theorem 20 (Regret bound for online learning channels of bounded complexity). Let be convex and L-Lipschitz. There exists an online learning strategy that, when presented sequentially with channel test operators
, and associated loss functions
outputs a sequence of hypothesis Choi matrices
whose regret is bounded as
Proof. Combining Theorem 11 and Corollary 19, we obtain the regret bounds from gate complexity as
where we have used the inequalitiesfor
0 and the integral identity
), with the error function given as erf(
Finally, to conclude our discussion of online learning channels with gate complexity G, we can combine Theorem 20 with Lemma 12 to obtain the following mistake bound.
Corollary 21 (Mistake bound for online learning channels of bounded complexity). Let There exists an online learning strategy that, in a realizable setting for
, when presented sequentially with channel test operators
, and associated loss functions
), for some
, outputs a sequence
, of hypothesis Choi matrices that makes at most
Proof. Thanks to Theorem 20, we can apply Lemma 12 with for a suitable constant C > 0 and with
So, the mistake bound obtained from Lemma 12 in this case is exactly as claimed in the statement of the corollary.
Together, Theorem 20 and Corollary 21 establish Theorem 1. In particular, this implies: For the physically relevant class of channels implementable with polynomial-size circuits, we can solve the online learning task with only polynomially many mistakes.
3.2 Regret bound for mixtures of known channels
In the previous section, it was shown that online learning quantum channels of bounded gate complexity is possible with good regret and number of mistakes. Here we show that even if the channel has unbounded (exponentially many in the number of qubits) gates that act on the input state, regret- and mistake-bounded online learning is still possible if we know the gates but not the probability with which they act. Even more generally, we show that any channel composed of mixture of known channels is efficiently online learnable, even if the mixture is over exponentially many known channels, which could be arbitrary quantum channels. A notable example of such channels are mixed unitary channels (with known unitaries), for example Pauli channels. Since the Pauli channel framework is better understood and well-known, we first prove regret upper bounds in this setting for clearer exposition. Later we generalize this to mixtures of general known channels.
Theorem 22 (Regret bound for online learning Pauli channels). Let : [0, 1]
be convex and L-Lipschitz. There exists an online learning strategy that, when presented sequentially with channel test operators
, and associated losses
), outputs Pauli channel Choi matrix hypotheses
whose regret is bounded as
for every Pauli channel
Proof. The result follows by applying Lemma 9 and applying the multiplicative weights update (MWU) algorithm (Algorithm 1) with a particular choice of the loss vectors . Specifically, we let
where
with the probability vectors defined according to the MWU algorithm. Let us verify that
1] for all
, as required by the MWU algorithm. Indeed, we readily have that
1] because
is assumed to be L-Lipschitz. In addition, we have that
where we have used the fact that, because is a channel test operator, there exists a density operator
. Therefore,
1] for all
Now, for every Pauli channel with associated error-rate vector
, we can use Equation (2.12) to see that
and similarly, we find that
Therefore, it follows from the known regret bound in Theorem 13 on the MWU algorithm that
Finally, combining this inequality with the result of Lemma 9, we obtain
for every Pauli channel . The claimed bound then follows by setting
While Theorem 22 focused solely on Pauli channels, as we show below, it readily translates to any convex combination of known channels—even exponentially many known channels that may have arbitrarily large gate complexity. This generalization captures a wide class of channels of interest, such as mixed unitary channels, in which each known channel is a unitary. Pauli channels are themselves a special case of such channels, because they are convex combinations of the 4unitary channels defined by the Pauli strings.
Corollary 23 (Regret bound for convex combinations of known channels). Let , and let
be a set of K known n-qubit channels
. Let
: [0, 1]
be convex and L-Lipschitz. There exists an online learning strategy that, when presented sequentially with channel test operators
, and associated losses
), outputs Choi matrix hypotheses
of the form
for every
Proof. The proof is analogous to that of Theorem 22. In particular, we combine Lemma 9 with the MWU algorithm (Algorithm 1) applied to a particular choice of loss vectors
where
with the probability vectors defined according to the MWU algorithm. As in the proof of Theorem 22, it is straightforward to verify that
1] for all
as required by the MWU algorithm.
Now, consider an arbitrary channel N in the convex hull of the channels , specified as N =
for some probability vector
). By linearity of the Choi representation, and using Theorem 13, we obtain
Therefore, by Lemma 9, we obtain
Setting , we obtain the desired regret bound.
Corollary 24 (Mistake bounds for Pauli channels and convex combination of known channels). Let (0, 1). Let
, and let
be a set of K known n-qubit channels
. Let
) be a fixed channel unknown to the learner. There exists an online learning strategy that, in a realizable setting for conv(
), when presented sequentially with two-outcome channel test operators
, and associated losses
for some L-Lipschitz
, outputs a sequence
) of hypothesis Choi matrices that makes at most
Proof. Mimicking the proof of Corollary 21 by invoking Lemma 12, but now for the choice for a suitable
3.3 Regret bounds for multi-time processes
In this section, we generalize the developments of Sections 3.1 and 3.2 to multi-time processes. We start by presenting the problem of online learning classes of multi-time processes, by casting it in terms of the general framework of online learning laid out in Section 2.2. With that, we formally state the problem in Problem 2 below.
Let . We fix finite-dimensional Hilbert spaces
, and we let
. Then, the input set/domain X comprises multi-time test operators corresponding to two-outcome multi-time tests
The output set is Y = [0, 1], and F is defined via a subclass of interest, such that for every
we define the function
. In other words,
As in the case of channels, online learning proceeds is an interactive procedure with an adversary, who provides test operators ) for two-output multi-time tests to the learner, and the learner outputs hypotheses
. The goal of the learner is to achieve a small regret,
Figure 3: Multi-time processes with bounded complexity. (a) The basic unit of our multi-time processes with bounded complexity is a process consisting of two two-qubit channels connected by an inaccessible memory system. (b) By collapsing the causal structure of the inputs and outputs of the process in (a), we obtain a three-qubit channel belonging to the set . (c) An example of a multi-time process obtained by composing (ten of) the basic elements in (a) in a circuit.
where the losses are revealed by the adversary. We aim for regret bounds scaling as
On the other hand, in the realizable scenario, where there exists a (to the learner unknown) comb operator
such that all losses take the form
), where
is some fixed function and each
3, the learner aims to achieve a small number of
-mistakes. Here, our goal is to guarantee mistake bounds scaling as
)). We summarize the formulation of our multi-time process online learning problem as follows.
Problem 2 (Online learning of multi-time quantum processes). Consider a subset , for
, and let
be unknown. Given a sequence of
interactive rounds, in which test operators
are presented sequentially by an adversary, the problem is to output a sequence
of comb operators such that for losses
of the form
), where
is some fixed function and each
satisfies
3, the regret in (3.33) scales as
)) and the number of
-mistakes scales as
We note that for r = 1, Problem 2 is equivalent to Problem 1. We also note that the projected MMW algorithm for Choi states of quantum channels (Algorithm 3) generalizes straightforwardly to Choi states of multi-time processes; see Algorithm 4.
We provide an analysis of Algorithm 4 in Appendix D.2; see Remark 64 therein.
Multi-time processes with bounded gate complexity. We can extend the results above to the case of multi-time processes with bounded complexity. The generalized form of multi-time processes allows for many possibilities for how to define multi-time processes with bounded complexity. Just as we defined n-qubit quantum channels with gate complexity G as being composed of at most G two-qubit quantum channels, here we consider multi-time processes composed of the basic “unit” shown in Figure 3(a). Specifically, we define to be the set of all comb operators corresponding to multi-time processes on n qubits that can be implemented by the composition of at most G of the basic units in Figure 3(a), in the manner of a circuit as shown in Figure 3(c). The number of time steps, r, in the multi-time process depends on G.
First, we prove an analogue of Lemma 18 for multi-time processes with gate complexity G. While the diamond norm was the natural distance measure in the case of channels, here we use strategy norms instead (see Appendix B for a definition and a discussion of their properties).
Lemma 25 (Covering number bounds from gate complexity for multi-time processes). Let The (interior)
-covering number of
with respect to
is bounded as
Proof. The proof again follows similar ideas as employed in the covering number bounds of [32, 68]. First, we recall (compare, e.g., Ref. [118]) a well-known fact about covering numbers of norm balls in ) denotes the
-ball of radius
norm
To apply this in our scenario, notice that any basic unit as in Figure 3(a) lives in the -unitball in a ((2
(2
of two 2-qubit channels. Consequently, via the approximate monotonicity of covering numbers w.r.t. inclusion of sets, the above standard bound implies for our case that
, the class of basic units, admits
as a covering number bound. If we let be the set of all basic units in Figure 3(a) that act on two out of n qubits, then the covering number of this set is bounded from above as follows:
with the binomial factorcoming from the fact that we allow the basic units to act on any pair of qubits.
Now, consider an arbitrary . By definition, every such comb operator has the form
, where
. Let
. By definition of the covering number
), for every
, we can find a corresponding
in an
-covering net for
. Then, if we let
, and by making use of the subadditivity-under-composition property of the strategy norm, as shown in Corollary 57, we obtain
Therefore, if we let -covering net for
, then the set
is an -covering net for
. Noting that
, we obtain
-covering net for
. As the covering number
is, by definition, the size of the smallest
-covering net for
, we can conclude that
as required.
Theorem 26 (Regret bound for online learning multi-time processes of bounded complexity). Let : [0, 1]
be convex and L-Lipschitz. There exists an online learning strategy that, when presented sequentially with multi-time test operators
for r time steps,
, and associated loss functions
), outputs a sequence of hypothesis comb operators
, corresponding to r-step multi-time quantum processes, whose regret is bounded as
Proof. The proof is analogous to the proof of Theorem 20. First, it holds that
for (0, 1), and
1. This holds due to the fact that
), where z is an arbitrary complete rooted binary tree of depth T. The first of these inequalities is due to monotonicity of the sequential covering numbers with respect to p, and the second follows from the fact that
for arbitrary multi-time test operators E and arbitrary comb operators N and , which holds because of the Hölder inequality for strategy norms in (2.32) and the fact that
1, by definition of a multi-time test operator. We have thus established (3.42). From here, an application of Theorem 11, along with the reasoning in the proof of Theorem 20, gives us the desired result.
Corollary 27 (Mistake bound for online learning multi-time processes of bounded complexity). Let
(0, 1). There exists an online learning strategy that, in a realizable setting for
, when presented sequentially with multi-time test operator
, and associated loss functions
), for some L-Lipschitz
, outputs a sequence
of hypothesis comb operators that makes at most
Proof. The proof follows the analogous arguments as in the proof of Corollary 21, in which we make use of the regret bound from Theorem 26.
Convex mixtures of known multi-time processes. We now show that Theorem 22 and Corollary 23 generalize straightforwardly to convex mixtures of arbitrary, known multi-time processes.
Theorem 28 (Regret bound for online learning convex mixtures of multi-time processes). Let and
. Consider a convex combination of K known r-step multi-time processes, with Choi representations
, such that
, where the unknown probability distribution is given by
). Let
: [0, 1]
be convex and L-Lipschitz. There exists an online learning strategy that, when presented sequentially with multi-time test operators
, and associated losses
), outputs hypotheses
of the form
Proof. We combine Lemma 9 with the MWU algorithm (Algorithm 1) applied to a particular choice of loss vectors
where
Let us verify that 1] for all
, as required by the MWU algorithm. First, we readily have that
(Tr[
1], because
is assumed to be L-Lipschitz. In addition, we have that
where the inequality is due to the fact that 1, which means by (2.31) that there exists
such that
; the chain of equalities holds because of the fact that
and
, such that there exists
satisfying the constraints in (2.28) and there exists
satisfying the constraints in (2.29).
Now, let for some probability vector
). Using Theorem 13, we obtain
Therefore, by Lemma 9, we obtain
Setting , we obtain the desired regret bound.
Corollary 29 (Mistake bound for convex mixtures of multi-time processes). Let (0, 1). Let
and
. Consider a convex combination of K known r-step multi-time processes, with Choi representations
, such that
, where the unknown probability distribution is given by
). There exists an online learning strategy that, in a realizable setting for conv(
), when presented sequentially with multi-time test operator
, and associated loss functions
), for some
, outputs a sequence
of hypothesis comb operators of the form
with , that makes at most
Proof. Using Lemma 12, we can derive this mistake bound from the regret bound of Theorem 28, analogously to how Corollary 24 followed from Corollary 23.
3.4 Learning-theoretic implications
To conclude our discussion of regret and mistake upper bounds for online learning certain classes of quantum channels, we highlight some learning-theoretic implications of our bounds. On the one hand, we note that our regret bounds immediately give rise to bounds on a complexity measure called sequential fat-shattering dimension [82] of the respective channel classes. On the other hand, our mistake-bounded online learner can be used to construct sample compression schemes. For simplicity of presentation, we focus on Pauli channels in this discussion. However, these implications immediately extend to all the classes of channels and the multi-time quantum processes that we established regret and mistake bounds for. That is, also for these classes we obtain complexity bounds and (approximate) compression schemes.
For the first implication, we rely on known results ([82, Proposition 9] and [83, Lemma 2]) to derive a sequential fat-shattering dimension bound from the regret bound established in Theorem 22:
Corollary 30 (Sequential fat-shattering dimension bound). Let be the class of all n-qubit Pauli channels, and let
1). Then, sfat
Proof. We start from Theorem 22 for the special case of . This gives us a regret bound of
). Combining this with the first inequality in Ref. [82, Proposition 9] or with [83, Lemma 2], we get
We can now rearrange and, after plugging in 1, we get the claimed bound of sfat
Via Ref. [83, Corollary 1], this sequential fat-shattering dimension bounds also implies sequential covering number bounds. While obtaining these complexity bounds from our regret bounds (Theorem 22) is standard given prior work, we highlight that the obtained bounds are exponentially better than what would arise from naive parameter counting. Namely, while a Pauli channel is specified by a 4-dimensional probability vector, these complexity measure bounds show that the “effective” dimension relevant for online learning is only linear in n. Finally, we note that the sequential fat-shattering dimension and covering numbers are upper bounds on their non-sequential counterparts. Thus, the above upper bounds immediately carry over to the complexity measures relevant for (agnostic) probably approximately correct (PAC) learning and lead to corresponding generalization bounds for PAC learning Pauli channels. In particular, this implies that Pauli channels are a restricted class of operations that allow for “pretty good process tomography”, as asked for in Ref. [15, Section 4]. We note that Refs. [15, 20] obtained (sequential) fat-shattering bounds for quantum states from bounds on quantum random access coding. It would be interesting to see whether this implication can be reversed in our setting: Do our (sequential) fat-shattering bounds imply limitations for encoding classical information into Pauli channels in a random access coding fashion?
Next, we turn our attention to implications for compression. For the case of {0, 1}-valued functions, the connection between mistake-bounded online learning and sample compression via the so-called one-pass compression scheme has already been observed in Ref. [119, Section 4]. We notice that, with minor adaptations, this reasoning also applies to [0, 1]-valued function classes when considering -mistakes and uniformly
-approximate compression schemes (defined in Ref. [120]):
Lemma 31 (Compression from mistake-driven online learning). Let [0, 1]
. Let
(0, 1). Suppose X admits some total order and suppose F admits a mistake-driven online learner A that makes at most
-mistakes when sequentially presented with challenges
and the corresponding values
) for some unknown
. Then, F admits a uniformly
-approximate sample compression scheme.
The assumption that X admits a total order is trivially satisfied whenever X is finite, which is typically the case in computational learning theory. If we assume the ordering principle (i.e., that every set can be totally ordered), then we can apply Lemma 31 for a general instance space X. We note that the ordering principle is strictly weaker than the well-ordering theorem [121–123] (see also [124, Section 4.4]), which in turn is well known to be equivalent to the axiom of choice.
Proof of Lemma 31. We first describe the compression and reconstruction maps, then we prove that they have the desired compression scheme property. The compression map [0, 1])
is defined as follows: Given a dataset
[0, 1], reorder S according to the total order on X, run the online learner A with an adversary that sequentially presents the learner with the reordered elements of
) be the set of (labeled) examples on which A made an
-mistake. Next, we define the reconstruction map
[0, 1] and
. If
[0, 1] such that (
, then we set
. Otherwise, we reorder S according to the total order on X, run the online learner A with an adversary that sequentially presents the learner with the reordered elements of S that precede x in the total order on
) be the value predicted by A for x.
Now, we prove that as defined above indeed form a form a uniformly
-approximate sample compression scheme for F. That is, we show that, for all
and for all
[0, 1], the function ˆ
)) satisfies max
. So, let
and let
[0, 1]. If 1
is such that
[0, 1] : (
), then by definition of
is such that
then by definition of
, this means that the online learner A does not make an
-mistake on
when presented sequentially with the elements of S reordered according to the total order on X. As A is mistake-driven, this implies that A also does not make an
-mistake on
when presented sequentially only with the (reordered) elements of S that precede
in the total order on X and on which A made an
-mistake. This is exactly the sequence of examples that A is run on when determining the value that ˆ
)) assigns to
Remark 32. Let us comment on a natural variant of Lemma 31: If the online learner A for F makes at most -mistakes even when presented only with (
3)-accurate approximations to the true function values – as is for instance the case for our MWU-based Pauli channel online learner –, this translates over to the resulting compression scheme. That is, even when sequentially presented with a training data set
with
3 for all 1
(instead of a “perfect” data set with
) for all 1
), the function ˆ
)) after compression still satisfies
for all 1
. Thus, this sample compression scheme is successful also if applied to data that has been affected by (possibly adversarial) label noise of strength
We can combine this with our mistake bound for Pauli channel learning to get a compression scheme for Pauli channels:
Corollary 33 (Compression scheme for Pauli channels). The set -qubit Pauli channels admits a uniformly
-approximate sample compression scheme of size
. This sample compression scheme even succeeds on training data whose labels have been corrupted by adversarial label noise of strength
Proof. Given our mistake bound for online learning Pauli channels (Corollary 24) and Lemma 31 (together with Remark 32), we only have to show that our instance space, which is the space of channel test operators, admits a total order. This can be seen as follows: Similar to Section 3.2, we can associate to any channel test operator the vector (
The mapping
is injective, because the operators Γ
form an orthogonal basis. Thus, any total order on [0, 1]
, for instance the lexicographic order, induces a total order on the set of channel test operators.
Corollary 33 implies that, if we care about the statistics of quantum experiments, then Pauli channels admit a significantly more parsimonious representation than via an exponentially long vector of Pauli error rates. This can be illustrated as follows: Suppose A(lice) and B(ob) want to understand how an unknown Pauli channel N in A’s lab acts on the channel test operators , 1
. To do so, A performs experiments and collects data
, where the
are (
3)-approximations of the corresponding expectation values Tr[
]. She now wants to communicate her findings to B. Then, no matter how large m is, A can compress S to a set of size at most
data points, send those to B, and B can
-approximately reconstruct the expectation values for all m test operators without doing any further experiments.
In the previous section, we provided regret and mistake upper bounds for online learning certain subclasses of quantum channels and multi-time processes. In this section, we prove complementary mistake lower bounds. While these, in principle, lead to regret lower bounds via (the contrapositive of) Lemma 12, we only discuss mistake lower bounds here. Throughout this section, our focus is on the dependence on -mistake lower bounds for a constant
2. Thus, our lower bounds do not scale with
. We conjecture that the (1
)-scaling achieved in Sections 3.1 and 3.2 is optimal, but leave the proof to future work.
4.1 Mistake lower bounds for general unitaries and channels
We first recall the folkore result that the class of arbitrary Boolean functions on n bits cannot be online learned with subexponentially many mistakes.
Lemma 34 (Arbitrary Boolean functions cannot be online learned with subexponentially many mistakes). Let be the class of all Boolean functions on n bits. Any online learner for F makes at least 2
mistakes against a worst-case adversary. This remains true even if the adversary is forced to decide on a labeling function before the interaction with the learner.
Proof. The class F of all {0, 1}-valued functions on has VC-dimension [125] VCdim(
and thus Littlestone dimension [37] Ldim(
. Essentially by definition of the Littlestone dimension, any online learner for F makes at least Ldim(
mistakes. This proves the first part of the statement.
Now for the second part of the statement. Fix an arbitrary learning algorithm. Consider an adversary that initially chooses a function uniformly at random from and, in round 1
, asks for the label of
, where
is some (fixed) enumeration of
. Let F denote the function-valued random variable describing the function chosen by the learner, let
denote the instance-label pairs that the online learner has seen in the first t rounds. Moreover, let
be the label predicted by the online learner in round t + 1. Note that the random variable
depends only on
(and on the internal randomness of the online learner). Thus, as
) is uniformly random and independent of
(as well as of the online learning algorithm), also
) are independent. Therefore,
Hence, in each round, the online learner makes a mistake with probability 1/2. As mistakes occur independently in each round, the probability that the online learner makes a mistake in every round is strictly greater than zero. Thus, there exists a function that, when chosen initially by the adversary, forces the online learner to make 2
We can now embed the problem of online learning an arbitrary classical Boolean function into that of learning an arbitrary quantum channel and therefore inherit similar mistake lower bounds. In the following, we describe two different ways of achieving such lower bounds.
Corollary 35. Let be the class of all unitary n-qubit channels, let
2. Any online learner for
-mistakes against a worst-case adversary. This remains true even if the adversary is forced to decide on a unitary before the interaction with the learner.
Proof. Our proof is via reduction to Lemma 34. To do so, we associate to every the n-qubit unitary
defined via
for
and
. We denote the corresponding unitary channel by
. Now, if we consider a channel test operator
then
Thus, if 2, then any online learner for
that makes at most
-mistakes gives rise to an online learner for
that makes at most N mistakes, by rounding the produced estimates to obtain a label in {0, 1}. Hence, by Lemma 34, we conclude that
Corollary 36. Let be the class of all n-qubit quantum channels, let
2. Any online learner for
-mistakes against a worst-case adversary. This remains true even if the adversary is forced to decide on a channel before the interaction with the learner.
Proof. Our proof is via reduction to Lemma 34. To do so, we associate to every the n-qubit channel
defined via
Now, if we consider a channel test operator ) with
and
Thus, if 2, then any online learner for
that makes at most N
-mistakes gives rise to an online learner for
that makes at most N mistakes, by rounding the produced estimates to obtain a label in {0, 1}. Hence, by Lemma 34, we conclude
These lower bounds demonstrate that, unsurprisingly, arbitrary quantum channels cannot be online learned with a number of mistakes that scales efficiently with the system size. This should be contrasted with the case of states: Ref. [20] proved that we can online learn the class of all n-qubit states with a number of mistakes that grows only linearly in n. Moreover, the exponential mistake lower bounds above motivate the focus on restricted subclasses of channels, such as channels of bounded gate complexity or mixtures of known channels, which we considered in Sections 3.1 and 3.2. In the next two subsections, we prove mistake lower bounds to be juxtaposed with the upper bounds established in Sections 3.1 and 3.2.
4.2 Mistake lower bounds for channels of bounded complexity
Recall that Theorem 20 and Corollary 21 established regret and mistake upper bounds for online learning channels of gate complexity G that scaled effectively linearly in G. Our next result, which follows by combining Corollary 36 with a “zooming in” on a suitable subset of qubits (as previously employed in Ref. [32]) shows that this scaling is essentially optimal.
Corollary 37 (Essentially optimal scaling). Let be the class of all n-qubit G-gate channels, i.e., channels of gate complexity (at most) G, and let
2. Any online learner for
makes Ω(min
) many
-mistakes against a worst-case adversary. This remains true even if the adversary is forced to decide on a G-gate channel before the interaction with the learner.
Proof. As we explain in Remark 40 below, for the claimed lower bound follows from our analysis for Pauli channels. Therefore, for the rest of this proof, we consider only G > n.
Recall that there is a universal constant C > 0 such that every Boolean function {0, 1} can be implemented with a de Morgan circuit of size at most
]. Here, a de Morgan circuit is a circuit consisting of AND, OR, and NOT gates, where the AND and OR gates have fan-in two. Hence, as any classical two-bit gate can be implemented by a two-qubit quantum channel gate, and as a computational basis measurement on a single qubit corresponds to one single-qubit channel gate, we see that every k-qubit channel
as in the proof of Corollary 36, with
can be implemented with
many two-qubit channel gates. Therefore, if we set
, where we consider the channels
from the proof of Corollary 36 and where we set q = min{n, k}. We can now straightforwardly modify the states and effect operators used in the proof of Corollary 36 (by attaching, say, the all-zero state on the last
qubits) to show that the
-mistake bound from Lemma 34, with n replaced by q, applies to
. Because of the previously observed inclusion, we conclude that also
comes with an
-mistake lower bound of 2
Corollary 37 establishes a mistake lower bound for online learning the class whose G-dependence matches our upper bound up to logarithmic factors. However, as the construction in the proof above uses a measurement followed by an in general non-reversible classical circuit, it is far from unitary. Therefore, we next give an alternative proof for Corollary 37 that, while still using non-unitary building blocks, is motivated by reversible computation and therefore can maybe serve as a stepping stone towards an analogue of Corollary 37 for unitary channels.
Alternative proof of Corollary 37. As before, Ref. [126] tells us that every Boolean function f : can be implemented with a de Morgan circuit of size at most
. As any OR gate can be rewritten in terms of three NOT gates and one AND gate, we can also achieve such implementations with circuit size
using only AND and NOT gates. The NOT gate can trivially be quantumly implemented by the Pauli-X gate. Using what Ref. [127] called the AND/NAND gate, and which (with a different ordering convention for the inputs) is now known as the Toffoli gate, we can implement an AND with a reversible three-bit gate when the “source” is a suitable constant bit, thereby producing two garbage output bits in the “sink”. Therefore, we can quantumly implement any two-bit AND gate using one three-qubit unitary in conjunction with a single-qubit channel gate that resets one of the “sink” qubits to the needed constant input, so that it can serve as a “source” for the next AND. The reset also allows us to use a single auxiliary qubit only throughout. Consequently, as any three-qubit unitary can be decomposed into a constant number of two-qubit unitaries, we can implement every function
with a (k + 1)-qubit quantum circuit of size
is now a new constant).
By this line of reasoning, if we set and
, then
, where we abused notation—by not writing out the restriction to computational basis inputs and measurements on the first q+1 qubits, and by ignoring the “source” and the “sink” subsystems at the output, which we can achieve by having identity tensor factors on the corresponding subsystems of the output effect operator. At this point, we again inherit a mistake lower bound from Corollary 36, which here becomes 2
This second proof already hints at a challenge in establishing the same Ω(minlower bound for
, the class of all unitary n-qubit channels of gate complexity G. Namely, when aiming to implement a unitary
, a natural approach is to take a classical circuit implementation for f and make it reversible. Above, we relied on Toffoli’s construction to achieve this with a small overhead in gate complexity. However, since there we need a specific constant input in the “source”, this required us to reset (some of) our “sink” qubits. Such a reset is a non-reversible operation. Without the ability to reset, making the implementation reversible naively requires to add one auxiliary qubit per gate, thus exceeding the number of available qubits if
. While we do not yet know how to overcome this obstacle when only using unitary gates, the following result at least demonstrates a lower bound for the unitary case that deviates from the G-dependence in the upper bound by only a square root.
Corollary 38 (Lower bound for the unitary case). Let be the class of all unitary n-qubit channels of gate complexity (at most)
2. Any online learner for
many
-mistakes against a worst-case adversary. This remains true even if the adversary is forced to decide on a G-gate channel before the interaction with the learner.
Proof. We first recall from Refs. [128–130]: There is a universal constant C > 0 such that any k-qubit unitary can be implemented with many two-qubit gates. Thus, if we set
many two-qubit gates suffice to implement arbitrary unitaries on k qubits. In particular, this implies that
, where q = min{n, k}. Therefore, a quantum circuit with G many unitary 2-qubit gates is able to implement all the unitaries
for functions
on the first q qubits. Hence, with a straightforward modification of the reasoning used in proving Corollary 35— tensoring the input states and output effects used there with, say, the all-zero state on the remaining
qubits—, we inherit the
-mistake bound from Lemma 34 with n replaced by q. That is, we obtain a
-mistake lower bound of
4.3 Mistake lower bounds for Pauli channels
To complement the linear-in-n mistake upper bound from Section 3.2, we now give a mistake lower bound for online learning Pauli channels. Again, we obtain this as a consequence of Lemma 34.
Corollary 39 (Mistake lower bound for online learning Pauli channels). Let be the class of all n-qubit Pauli channels, let
2. Any online learner for
against a worst-case adversary. This remains true even if the adversary is forced to decide on a Pauli channel before the interaction with the learner.
Proof. Our proof is via reduction to Lemma 34. To do so, we associate to any the unitary n-qubit Pauli channel
defined via
. Now, if we consider a channel test operator
Thus, if 2, then any online learner for
that makes at most
-mistakes gives rise to an online learner for
that makes at most N mistakes, by rounding the produced estimates to obtain a label in {0, 1}. Hence, by Lemma 34, we conclude
Corollary 39 shows that the linear-in-n scaling achieved in Section 3.2 is optimal for the special case of Pauli channel online learning. This also tells us that for learning a mixture of K known channels, the log(K)-dependence in the mistake bound can in general not be improved.
Remark 40. The channels used in the proof of Corollary 39 are unitary channels of gate complexity n. We can use essentially the same construction to show that for
, any online learner for
makes at least Ω(
-mistakes if
2. To see this, consider unitary n-qubit channels of the form
for functions
, and argue as in the proof of Corollary 39.
5.1 Computational complexity lower bounds for Pauli channels
In Section 4, we established mistake lower bounds for channels. In this section, we focus on computational complexity lower bounds for online learning classes of quantum channels. In particular, we show that while we achieve polynomial mistake upper bounds for learning classes of quantum channels, the exponential computational complexity of our learning algorithms cannot be avoided under standard cryptographic assumptions. But let us first start with an unconditional computational hardness lower bound for online learning Pauli channels. The heart of the proof strategy lies in exploiting the fact that any polynomial time learner is only ever able to access polynomially many entries of an exponentially sized input. By the adversarial nature of the game, the adversary can always ‘hide’ the information useful for answering a challenge in an entry that was never seen by the (polynomial-time) learner. We make this intuition formal in the following result.
Theorem 41. Consider any polynomial-time online learner of n-qubit Pauli channels that runs in time ) at time step
, for any polynomials
). There exists an explicit adversarial strategy that forces the learner to make
mistakes, where
Proof. Recall that for any unknown Pauli channel with associated Choi representation predicting Tr[
] (the task of the online learner) for a given channel observable
is exactly equivalent to predicting
, where p is the (unknown) error-rate distribution and the vector
has entries
We work in a simplified setting of a {0, 1}-valued game, in which the learner does not have to evaluate entries ] of the vector
for all
; the learner directly receives the vector
(which we shall refer to as the ‘challenge’ vector), instead of the test operators
. The learning task is still not obviously computationally tractable, because the challenge vector is of size 4
. We prove that a polynomial-time learner, who by definition only looks at polynomially-many entries of
, can be forced to make ˜Ω(4
) many mistakes by a simple adversarial strategy. The adversarial strategy is to always play
0), i.e., the all-zeros vector, corresponding to
We now show that by using the same all-zeros challenge vector in every round, the adversary can always contradict the learner’s prediction, and thereby claim that they made a mistake. In any T-round interaction with the adversary, let the (deterministic) learner predict
in round
. In response, the adversary claims the correct answer to be
. In other words, the adversary always contradicts the learner’s prediction, and thereby forces the learner to make a mistake. Note that this contradictory feedback indeed constitutes a mistake when we take the loss function to be
Let us now prove that after the end of the T rounds, the adversary can claim to be “consistent”, despite their contradictory feedback, as long as it does not contradict the entries that the learner has seen. In other words, after the end of the T rounds, the adversary can always exhibit a and challenge vectors ˜
such that, for all
and such that ˜
has 0-entries at the positions of the challenge vector that the online learner accessed in round t. The key to proving this is the fact that the learner is computationally bounded, and therefore, they can only query polynomially-many entries of
in every round.
In any given round, the adversarial feedback, , is either 0 or 1. For
claims to actually have played the all-zero challenge vector. For the rounds where the adversary claimed
such rounds, there was in fact a non-zero entry in
(that the learner did not look at) and that this entry leads to
that
had a single non-zero entry. Vectors
with this structure are indeed realized in our learning scenario by choosing
for some
, because
forms an orthogonal basis and Tr[(Γ
. Thus, choosing
ensures that
is has 4
1 entries equal to 0 and a single entry
equal to 1, when
Let us partition the set R := {1, 2, . . . , T} into two disjoint subsets as , where
is the set of time steps in which the adversary claimed the correct answer to be 0 and
is the set of time steps in which they claimed the correct answer to be 1. Let
) be the polynomial number of entries of
accessed by the learner at time step t. Also, let
indices corresponding to the entries of
accessed by the learner in round t. To be consistent, the adversary sets to 0 all entries of
corresponding to the indices in (
i.e., all entries that the learner saw. Then, retroactively, for the rounds in which they claimed 1 to be the correct answer, the adversary can always claim that the 1-entry in both
and
was an entry that the learner never saw, i.e., an entry whose index is in
sufficient that there exists at least one such index. Then, this adversarial strategy works as long as the number of entries seen by the learner does not exceed 4
1 (in order to account for at least one entry that the learner has not seen). In other words,
where ) :
) :
and
) :
) :
, and the final inequality holds because
(recall that
) :
), and
. Thus, the adversary can force the learner to make mistakes for
many rounds.
Remark 42. The computational complexity of MWU (Algorithm 1) for online learning convex combinations of K known channels scales polynomially with K, which in the worst case could be exponential in the number of qubits, as is the case for general Pauli channels. If, however, the learner is given challenge vectors with entries
)-sparse (with known sparsity structure), then an online learner can learn such a channel computationally efficiently and also saturate optimal regret and mistake bounds using MWU (Algorithm 1). A relevant example (from quantum error correction) of a class of channels that can be written as convex combinations of polynomially many known channels is that of polynomially-sparse Pauli channels with a known sparsity structure. Hence, our results imply that this class of channels is computationally efficiently online learnable with regret and mistake bounds that scale with log(
Remark 43. The proof strategy in Theorem 41 straightforwardly implies that any polynomial time learner for online learning quantum states (in the sense defined in Ref. [20]) can be forced to make exponentially many -mistakes as long as the ‘challenge’ effect operators admit exponentially long descriptions. To see this, write, in its spectral decomposition, any n-qubit state
that a learner wishes online learn. For the lower bound, it suffices to work in a simpler scenario in which the learner knows the eigenbasis
in advance but not the eigenvalues
. For every effect operator E, we have Tr[
. Defining a vector
with entries
, we can rewrite this as Tr[
, where
. Since e is still an exponentially long challenge vector, the strategy in the proof of Theorem 41 suffices to make the online learner make exponentially many mistakes.
5.2 Computational complexity lower bounds for channels of bounded complexity
The online learner for presented in Section 3.1 achieves good regret and
-mistake bounds, but is computationally inefficient. In this section, we prove that, under a widely held cryptographic hardness assumption, namely hardness of RingLWE, there cannot be a computationally efficient online learning algorithm for
that achieves favorably scaling mistake bounds. Via Lemma 12, this also implies that good regret bounds for online learning
cannot be achieved computationally efficiently, but we again focus on mistake bounds here. Our proof, which is conceptually analogous to arguments in [32, 131], is yet another instance of the well known fact that pseudorandom functions cannot be learned efficiently, which we phrase in an online learning framework.
First, we recall the definition of pseudorandom functions.
Definition 44 (Pseudorandom functions (PRFs) [132]). Let be a security parameter. Let K =
be key space, assumed to be efficiently sampleable. Let
be families of finite sets. Let
be a family of efficiently-computable functions
, where the input from
corresponds to the function key. The family F is a pseudorandom function (family) secure against (classical)
-time adversaries if for every
)-time probabilistic algorithm Adv, there exists a negligible function
)—that is, a function satisfying
(1) for every polynomial p—such that, for every security parameter
, it holds that
where the key k is drawn uniformly at random from is drawn uniformly at random from the set of all functions from
to
. Here, we use Adv with a function superscript to mean the action of the algorithm Adv when given oracle access to that function.
Typically, the runtime ) of interest in this definition is taken to be polynomial. However, other choices of
) are possible.
Next, we formalize the hardness of learning PRFs in the context of online learning:
Theorem 45 (Hardness of learning PRFs in online learning). Take the security parameter to be . Let
be a PRF that is secure against classical O(t(n))-time adversaries. Let ∆ :
be a polynomial and let
be a function such that
)). Suppose
[0, 1]
is a function class such that
and ln (
). There exists no classical O(t(n))-time algorithm for properly online learning G with at most 6(
3)-mistakes in an online game with 18(
Theorem 45 in particular says: If a hypothesis class of interest has polynomial sequential metric entropies and contains a class of PRFs secure against polynomial-time adversaries, then that class cannot be efficiently online learned with polynomially many O(1)-mistakes.
Proof. Suppose for contradiction that A is an O(t(n))-time algorithm for properly online learning G with at most m(n) = 6(p(n) +) many (1/3)-mistakes in an online learning game with at least T(n) = 3m(n) many rounds. Note that
)), by our assumptions on p and ∆. We then construct a procedure for distinguishing between a random element of F and a truly random function with success probability
). Namely, we define D, when given query access to a function f, to act as follows: First, simulate an online learning game between the learner A and an adversary that uses an arbitrary sequence of pairwise distinct challenges
and the corresponding true values
). Second, if A made at most m(n) many (1/3)-mistakes,
”, otherwise
truly random”.
Let us analyze the success probability of D. On the one hand, if , then the simulated online learning game takes place in a realizable scenario. So A makes at most p(n) many (1/3)-mistakes by assumption, and thus D correctly outputs “
”. On the other hand, suppose f is chosen as a truly random function from
to {0, 1}. As A is assumed to be proper, we know that for any 1
Next, notice that by the definition of sequential covering with , if we let V = V (x) be a smallest sequential
-norm (1/6)-cover for G, where x is a complete rooted binary tree of depth T(n) such that there is a path
), then for any
there exists a v
6. So, by the triangle inequality and a union bound,
As the are pairwise distinct and f is a random function, the values
independent Bernoulli random variables, each with parameter 1/2.
Hence, for any fixed v and for any 0 , the probability that at most m of the predictions made by v are (1/6)-mistakes is
where we have used a Chernoff-Hoeffding bound. Plugging this into our previous bound, we see that
where we have used T(n) = 3m(n) and our choice of m(n). Thus, in the case of a truly random f, the distinguisher D correctly outputs “f truly random” with probability . As ∆ is by assumption polynomial, this means that D successfully distinguishes between pseudorandom and random with non-negligible success probability.
Thus, to complete the proof by contradiction (to the pseudorandomness guarantee required in Definition 44), it remains to argue that D runs in time O(t(n)). This can be seen as follows. On the one hand, D plays the online learning game. Here, the learning side takes time O(t(n)) by assumption, and the adversary side takes time O(T(n)), since oracle queries take unit time. On the other hand, D checks how many mistakes the online learner makes, which takes time O(T(n)). Thus, the overall time taken by
Remark 46. Notice that in the proof of Theorem 45, the only property of the challenges that mattered to the argument was that they are chosen to be pairwise distinct. Hence, this line of reasoning can be extended to learner-adversary interactions in which the learner, rather than the adversary, actively chooses pairwise distinct inputs to the unknown function.
We now apply Theorem 45 for our scenario of online learning bounded-complexity quantum channels. To obtain efficiently implementable PRFs, we make a common hardness assumption, namely the hardness of the ring learning with errors (RingLWE) problem [85]. Note that despite our online learning problems revolving around function classes coming from quantum physics, the classes and learners under consideration are all classical. Therefore, we only assume classical hardness of RingLWE.
Corollary 47 (Computational hardness). Take the security parameter to be the class of all n-qubit channels of gate complexity at most G. If there is no classical polynomial-time algorithm for solving RingLWE, then already for G = O(npolylog(n)) there exists no (classical) polynomial-time algorithm for properly online learning
with at most polynomially many (1/3)-mistakes, even under the promise that all challenges consist of input states and output effect operators given by rank-1 projections on computational basis elements (without an auxiliary system).
Proof. First, recall from Corollary 19 that the sequential metric entropies of satisfy the bound ln
)), which scales at most polynomially in n if G does. Thus, to apply Theorem 45, it remains to argue that
contains a suitable PRF family. We combine results from prior work to obtain such a PRF from the assumed hardness of RingLWE. Namely, Ref. [133, Theorem 5.3] shows that polynomial-time hardness of (decision-)RingLWE with suitable parameters (see Ref. [85, 133] for more context and a formal discussion) gives rise to a PRF family
on
(log(
))-bit inputs that is secure against polynomial-time classical adversaries. Moreover, as shown in Ref. [134, Lemma 3.16], every
can be computed by a
circuit, that is, by a constant-depth, polynomial-size circuit consisting of AND, OR, NOT, and MAJORITY gates with unbounded fan-in. As shown in Ref. [32, Proposition 2], if
can be implemented by a
circuit, then there is a quantum circuit on n = O(poly(m)) qubits with size O(npolylog(n)) that implements the unitary
acting as
(ignoring auxiliary qubits). Consequently, choosing the security parameter as
, every function in RF can be implemented by a unitary quantum circuit of size O(npolylog(n)), and thus G = O(npolylog(n)) suffices to guarantee the inclusion
. (Note: Here, we slightly abused notation by not explicitly restricting
to the input space of RF, which can be embedded into the Boolean hypercube.)
Hence, for G = O(npolylog(n)), we can apply Theorem 45 with (again not writing out the restriction of the input space), ∆(n) = 3, p(n) = O(G log(Gn)), and t(n) = poly(n). This yields the claimed result.
As can be seen in the proof of Corollary 47, the hardness assumption on RingLWE is “only” used to obtain a PRF class implementable by relatively small circuits. Therefore, one may replace this widely believed assumption about the hardness of a concrete problem [52–54] by a more abstract cryptographic assumption on the existence of PRFs implementable by small circuits, and the above line of reasoning can still be applied.
For quantum states, shadow tomography [16, 17, 19] is the task of using few copies of an unknown state to predict the expectation values of M effect operators, which may be chosen adaptively/adversarially. In this section, we consider the analogous problem for quantum processes, starting with quantum channels and then going to multi-time processes.
Problem 3 (Shadow tomography of quantum channels). Let be an (unknown) n-qubit channel, and let
0. When sequentially presented with any adversarially chosen sequence of two-outcome test operators,
, return quantities
such that
for all
with probability at least 1
. Do this by querying the channel k times (adaptively or in parallel), with k being as small as possible.
Embedding classical functions into quantum channels similarly to Section 4.1, one can see that in the case of general quantum channels, no non-trivial shadow tomography strategy—achieving a query complexity that is simultaneously sublinear in M and polynomial in n—is possible. Therefore, we again have to consider restricted classes of channels. We primarily focus on Pauli channels and Pauli multi-time processes, for which we introduce a shadow tomography scheme via classical adaptive data analysis [55, 56] that requires few measurements (of the Choi state) of the unknown process.
Theorem 48 (Shadow tomography of Pauli channels). There exists an explicit strategy that solves Problem 3 for any n-qubit Pauli channel using
copies of the channel. The strategy runs in time poly(4) per query.
Proof. Let A and B be n-qubit systems, and consider a Pauli channel as in (2.11), with error-rate vector
. Consider also test operators
every such operator, we have
where we have defined ]. From this, we can see that every desired expectation value is exactly the expectation value of the function (
] with respect to the error-rate probability distribution p of the unknown Pauli channel
. Now, we can obtain samples from the error-rate distribution by performing Bell measurements on the Choi state. Specifically, to obtain one sample, we prepare a (2n)-qubit maximally-entangled state Φ
), send the
system through the channel, and then measure systems A and B with respect to the Bell basis POVM
. Note that this indeed amounts to measuring the Choi state of the channel with respect to the Bell basis POVM. Then, using the definition of the n-qubit Bell states in (2.4), the probability of obtaining an outcome (z, x) is given by
for all
We can now combine (6.2) with the ability to sample from the error-rate distribution obtained by Bell measurements to make use of known results in classical adaptive data analysis [55, 56]. In classical data analysis, the goal is to answer a sequence of adaptively chosen queries with answers
, such that
samples from the underlying (unknown) probability distribution p. This setting precisely matches our setting of Pauli channel shadow tomography, by recognizing that the underlying distribution p can be taken to be the error-rate distribution of the unknown Pauli channel, and the queries
can be taken to be
. Then, in the regime
, we make direct use of Ref. [56, Corollary 6.3] to obtain our desired result.
We highlight that Theorem 48 for restricted/approximate shadow tomography of Pauli channels can be used to perform shadow tomography of arbitrary channels, essentially by applying Theorem 48 to the Pauli twirled version of the channel. The upshot is that our bounds scale with the diamond norm distance between the unknown channel and its corresponding Pauli twirled version.
Corollary 49 (Shadow tomography of arbitrary quantum channels). Let be an arbitrary quantum channel. There exists an explicit strategy that solves Problem 3 for N using
copies of is the Pauli twirled version of
Proof. We perform a Bell measurement on the Choi state of the unknown channel. The measurement probabilities define the error-rate vector of the Pauli-twirled version of the channel, based on the developments in Appendix C. Then, we make use of the triangle inequality as follows, for an arbitrary and arbitrary channel test operator, to get
where in the final equality we made use of the fact that (see, e.g., [135, Section 4])
for arbitrary channels N and M. Finally, as we assume 0, can run the Pauli channel shadow tomography from Theorem 48 with accuracy parameter ˜
the desired approximation guarantee
with the claimed sample complexity bounds.
6.1 Shadow tomography of multi-time processes
By analogy with the shadow tomography problem for quantum channels, we can formulate the problem of shadow tomography for multi-time quantum processes.
Problem 4 (Shadow tomography of multi-time quantum processes). Let , let
be a comb operator corresponding to a multi-time quantum process with r time steps, and let
0. When sequentially presented with any adversarially chosen sequence of two-outcome multi-time test operators
, for
, return quantities
such that
with probability at least 1
. Do this by querying the process k times (adaptively or in parallel), with k being as small as possible.
By following arguments similar to those in the proof of Corollary 49, we can prove a shadow tomography result for arbitrary multi-time quantum processes as follows. In particular, this involves introducing the idea of Pauli-twirling a multi-time process, which we illustrate in Figure 4(a).
Corollary 50. Let , let
be a comb operator corresponding to a multi-time quantum process with r time steps. There exists an explicit strategy that solves Problem 4 for
where is the comb operator corresponding to the Pauli-twirled version of the multi-time process (see Figure 4(a) for a depiction), and
Proof. We proceed by performing “time-local” Bell measurements on the multi-time process; see Figure 4(b). This means that, for every time step, we prepare a Bell state, send one-half of it
Figure 4: Twirling of multi-time quantum processes. (a) A “time-local” Pauli twirl of a multi-time quantum process with r time steps consists of independently applying a random Pauli channel , to the input and output of every time step
. (b) After twirling, the process is characterized by an error-rate probability vector, in the same way as Pauli channels. This error-rate vector can be obtained via time-local Bell measurements, as shown. The outcomes of the measurements are
through the process, and then measure the output system and the other-half of the Bell state in the (2n)-qubit Bell basis. Doing this once for each time step leads to measurement outcomes (
). The probability of any such collection of measurement outcomes is given by
which is due to the fact that applying one-half of a maximally-entangled state to every input of the process defines the Choi state of the process, which is equal to ; see Appendix B.
Let us now consider the Pauli-twirl of the process, as depicted in Figure 4(a). By combining Lemma 58 and Proposition 59, we find that the comb operator for the Pauli-twirled process is equal to
We now observe that the comb operator for the Pauli-twirled process can be thought of as simply the Choi representation of an (nr)-qubit Pauli channel. As such, we can apply Theorem 48. Furthermore,
for an arbitrary and an arbitrary test operator E, we have
where for the final equality we made use of the fact that
for arbitrary . To conclude, we again invoke the Pauli channel shadow tomography of Theorem 48
with accuracy
0 to obtain the desired approximation error
with the claimed sample complexity bound.
[1] J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi. Quantum certification and benchmarking. Nature Reviews Physics, 2:382–390, 2020. doi: 10.1038/s42254-020-0186-4.
[2] Z. Hradil. Quantum-state estimation. Physical Review A, 55:R1561–R1564, 1997. doi: 10.1103/PhysRevA.55.R1561.
[3] G. Mauro D’Ariano, M. G.A. Paris, and M. F. Sacchi. Quantum tomography. Advances in Imaging and Electron Physics, 128:205–308, 2003. doi: 10.1016/S1076-5670(03)80065-4.
[4] D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert. Quantum state tomography via compressed sensing. Physical Review Letters, 105:150401, 2010. doi: 10.1103/PhysRevLett. 105.150401.
[5] R. Blume-Kohout. Optimal, reliable estimation of quantum states. New Journal of Physics, 12(4):043034, 2010. doi: 10.1088/1367-2630/12/4/043034.
[6] K. Banaszek, M. Cramer, and D. Gross. Focus on quantum tomography. New Journal of Physics, 15(12):125020, 2013. doi: 10.1088/1367-2630/15/12/125020.
[7] I. L. Chuang and M. A. Nielsen. Prescription for experimental determination of the dynamics of a quantum black box. Journal of Modern Optics, 44(11–12):2455–2467, 1997. doi: 10.1080/ 09500349708231894.
[8] G. M. D’Ariano and P. Lo Presti. Quantum tomography for measuring experimentally the matrix elements of arbitrary quantum operation. Physical Review Letters, 86:4195–4198, 2001. doi: 10.1103/PhysRevLett.86.4195.
[9] M. Mohseni, A. T. Rezakhani, and D. A. Lidar. Quantum-process tomography: Resource analysis of different strategies. Physical Review A, 77:032322, 2008. doi: 10.1103/PhysRevA. 77.032322.
[10] J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu. Sample-optimal tomography of quantum states. IEEE Transactions on Information Theory, 63(9):5628–5641, 2017. doi: 10.1109/TIT. 2017.2719044.
[11] R. O’Donnell and J. Wright. Efficient quantum tomography. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 899–912, 2016. doi: 10.1145/2897518. 2897544.
[12] S. Chen, J. Li, Brice Huang, and A. Liu. Tight bounds for quantum state certification with incoherent measurements. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1205–1213. IEEE, 2022. doi: 10.1109/FOCS54457.2022.00118.
[13] J. Haah, R. Kothari, R. O’Donnell, and E. Tang. Query-optimal estimation of unitary channels in diamond distance. 2023. arXiv:2302.14066.
[14] A. Oufkir. Sample-optimal quantum process tomography with non-adaptive incoherent measurements. 2023. arXiv:2301.12925.
[15] S. Aaronson. The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2088):3089–3114, 2007. doi: 10.1098/ rspa.2007.0113.
[16] S. Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 325–338, New York, NY, USA, 2018. Association for Computing Machinery. doi: 10.1145/3188745.3188802.
[17] C. Bădescu and R. O’Donnell. Improved quantum data analysis. TheoretiCS, Volume 3, 2024. doi: 10.46298/theoretics.24.7.
[18] H.-Y. Huang, R. Kueng, and J. Preskill. Information-theoretic bounds on quantum advantage in machine learning. Physical Review Letters, 126:190505, 2021. doi: 10.1103/PhysRevLett. 126.190505.
[19] R. King, D. Gosset, R. Kothari, and R. Babbush. Triply efficient shadow tomography. 2024. arXiv:2404.19211.
[20] S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak. Online learning of quantum states. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124019, 2019. doi: 10.1088/1742-5468/ab3988.
[21] X. Chen, E. Hazan, T. Li, Z. Lu, X. Wang, and R. Yang. Adaptive online learning of quantum states. 2022. arXiv:2206.00220.
[22] H.-Y. Huang, R. Kueng, and J. Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16:1050–1057, 2020.
[23] A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller. The randomized measurement toolbox. Nature Reviews Physics, 5:9–24, 2023.
[24] M. Ohliger, V. Nesme, and J. Eisert. Efficient and feasible state tomography of quantum many-body systems. New Journal of Physics, 15(1):015024, 2013. doi: 10.1088/1367-2630/15/ 1/015024.
[25] H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, R. Kueng, John Preskill, and Jarrod R. McClean. Quantum advantage in learning from experiments. Science, 376(6598):1182–1186, 2022. doi: 10.1126/science.abn7293.
[26] R. Levy, D. Luo, and R. K. Clark. Classical shadows for quantum process tomography on near-term quantum computers. Physical Review Research, 6(1):013029, 2024. doi: 10.1103/ PhysRevResearch.6.013029.
[27] J. Kunjummen, M. C. Tran, D. Carney, and J. M. Taylor. Shadow process tomography of quantum channels. Physical Review A, 107:042403, 2023. doi: 10.1103/PhysRevA.107.042403.
[28] Hsin-Yuan Huang, Sitan Chen, and John Preskill. Learning to predict arbitrary quantum processes. PRX Quantum, 4(4):040337, 2023. doi: 10.1103/PRXQuantum.4.040337.
[29] M. C. Caro. Learning quantum processes and Hamiltonians via the Pauli transfer matrix. 2022. arXiv:2212.04471.
[30] A. Angrisani. Learning unitaries with quantum statistical queries. 2023. arXiv:2310.02254.
[31] C. Wadhwa and M. Doosti. Learning quantum processes with quantum statistical queries. 2023. arXiv:2310.02075.
[32] H. Zhao, L. Lewis, I. Kannan, Y. Quek, H.-Y. Huang, and M. C. Caro. Learning quantum states and unitaries of bounded gate complexity. 2023. arXiv:2310.19882.
[33] M. Riebe, K. Kim, P. Schindler, T. Monz, P. O. Schmidt, T. K. Körber, W. Hänsel, H. Häffner, C. F. Roos, and R. Blatt. Process tomography of ion trap quantum gates. Phys. Rev. Lett., 97:220407, 2006. doi: 10.1103/PhysRevLett.97.220407.
[34] R. C. Bialczak, M. Ansmann, M. Hofheinz, E. Lucero, M. Neeley, A. D. O’Connell, D. Sank, H. Wang, J. Wenner, M. Steffen, A. N. Cleland, and J. M. Martinis. Quantum process tomography of a universal entangling gate implemented with Josephson phase qubits. Nature Physics, 6:409–413, 2010. doi: 10.1038/nphys1639.
[35] J. Helsen, M. Ioannou, J. Kitzinger, E. Onorati, A. H. Werner, J. Eisert, and I. Roth. Estimating gate-set properties from random sequences. Nature Communications, 14:5039, 2023. doi: 10.1038/s41467-023-39382-9.
[36] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. ISSN 00010782. doi: 10.1145/1968.1972.
[37] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2(4):285–318, 1988. ISSN 1573-0565.
[38] S. Shalev-Shwartz and S. Ben-D. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. doi: 10.1017/CBO9781107298019.
[39] M. Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2 edition, 2018.
[40] M. Kearns, M. Li, L. Pitt, and L. G. Valiant. Recent results on Boolean concept learning. In Pat Langley, editor, Proceedings of the Fourth International Workshop on Machine Learning, pages 337–352. Morgan Kaufmann, 1987. doi: https://doi.org/10.1016/B978-0-934613-41-5.50037-4.
[41] N. Littlestone. From on-line to batch learning. In Proceedings of the Second Annual Workshop on Computational Learning Theory, COLT ’89, page 269–284, San Francisco, CA, USA, 1989. Morgan Kaufmann Publishers Inc. doi: 10.1016/B978-0-08-094829-4.50022-2.
[42] L. Gretta and E. Price. An improved online reduction from PAC learning to mistake-bounded learning. In 2023 Symposium on Simplicity in Algorithms (SOSA), pages 373–380, 2023. doi: 10.1137/1.9781611977585.ch34.
[43] N. Cesa-bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. In T. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001.
[44] N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050–2057, 2004. doi: 10.1109/TIT.2004.833339.
[45] A. L. Blum. Separating distribution-free and mistake-bound learning models over the Boolean domain. SIAM Journal on Computing, 23(5):990–1000, 1994.
[46] E. Hazan. Introduction to online convex optimization. 2021. arXiv:1909.05207.
[47] H.-C. Cheng, M.-H. Hsieh, and P.-C. Yeh. The learnability of unknown quantum measurements. Quantum Information and Computation, 16(7), 2016.
[48] M. C. Caro and I. Datta. Pseudo-dimension of quantum circuits. Quantum Machine Intelligence, 2:14, 2020. doi: 10.1007/s42484-020-00027-5.
[49] C. M. Popescu. Learning bounds for quantum circuits in the agnostic setting. Quantum Information Processing, 20(9):1–24, 2021.
[50] H. Cai, Q. Ye, and D.-L. Deng. Sample complexity of learning parametric quantum circuits. Quantum Science and Technology, 7(2):025014, 2022.
[51] J. J. Wallman and J. Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94:052325, 2016. doi: 10.1103/PhysRevA.94.052325.
[52] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009. doi: 10.1145/1568318.1568324.
[53] P. Ananth, A. Poremba, and V. Vaikuntanathan. Revocable cryptography from learning with errors. In Theory of Cryptography Conference, pages 93–122. Springer, 2023. doi: 10.1007/978-3-031-48624-1_4.
[54] D. Aggarwal, H. Bennett, Z. Brakerski, A. Golovnev, R. Kumar, Z. Li, S. Peters, N. StephensDavidowitz, and V. Vaikuntanathan. Lattice problems beyond polynomial time. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1516–1526, 2023. doi: 10.1145/3564246.3585227.
[55] C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth. Preserving Statistical Validity in Adaptive Data Analysis. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, pages 117–126, New York, NY, USA, 2015. Association for Computing Machinery. doi: 10.1145/2746539.2746580.
[56] R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman. Algorithmic Stability for Adaptive Data Analysis. SIAM Journal on Computing, 50(3):STOC16–377–STOC16–405, 2016. doi: 10.1137/16M1103646.
[57] G. Chiribella, G. Mauro D’Ariano, and P. Perinotti. Theoretical framework for quantum networks. Physical Review A, 80:022339, 2009. doi: 10.1103/PhysRevA.80.022339.
[58] M. Born. Zur Quantenmechanik der Stoßvorgänge. Zeitschrift für Physik, 37:863–867, 1926.
[59] M. Ziman. Process positive-operator-valued measure: A mathematical framework for the description of process tomography experiments. Physical Review A, 77:062112, 2008. doi: 10.1103/PhysRevA.77.062112.
[60] G. Gutoski and J. Watrous. Toward a general theory of quantum games. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, pages 565–574, New York, NY, USA, 2007. Association for Computing Machinery. doi: 10.1145/1250790.1250873.
[61] F. A. Pollock, C. Rodríguez-Rosario, T. Frauenheim, M. Paternostro, and K. Modi. NonMarkovian quantum processes: Complete framework and efficient characterization. Physical Review A, 97:012127, 2018. doi: 10.1103/PhysRevA.97.012127.
[62] S. Milz and K. Modi. Quantum stochastic processes and quantum non-Markovian phenomena. PRX Quantum, 2:030201, 2021. doi: 10.1103/PRXQuantum.2.030201.
[63] G. D. Berk, A. J. P. Garner, B. Yadin, K. Modi, and F. A. Pollock. Resource theories of multi-time processes: A window into quantum non-Markovianity. Quantum, 5:435, 2021. ISSN 2521-327X. doi: 10.22331/q-2021-04-20-435.
[64] G. A. L. White, F. A. Pollock, L. C. L. Hollenberg, K. Modi, and C. D. Hill. Non-Markovian quantum process tomography. PRX Quantum, 3:020344, 2022. doi: 10.1103/PRXQuantum.3. 020344.
[65] A. Abbas, R. King, H.-Y. Huang, W. J. Huggins, R. Movassagh, D. Gilboa, and J. McClean. On quantum backpropagation, information reuse, and cheating measurement collapse. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 44792–44819. Curran Associates, Inc., 2023.
[66] C.-C. Chen, M. Watabe, K. Shiba, M. Sogabe, K. Sakamoto, and T. Sogabe. On the expressibility and overfitting of quantum circuit learning. ACM Transactions on Quantum Computing, 2(2):1–24, 2021. doi: 10.1145/3466797.
[67] Y. Du, Z. Tu, X. Yuan, and D. Tao. Efficient measure for the expressivity of variational quantum algorithms. Physical Review Letters, 128(8):080506, 2022. doi: https://doi.org/10. 1103/PhysRevLett.128.080506.
[68] M. C. Caro, H.-Y. Huang, M. Cerezo, K. Sharma, A. Sornborger, L. Cincio, and P. J. Coles. Generalization in quantum machine learning from few training data. Nature Communications, 13:4919, 2022. doi: 10.1038/s41467-022-32550-3.
[69] M. C. Caro, H.-Y. Huang, N. Ezzell, J. Gibbs, A. T. Sornborger, L. Cincio, P. J. Coles, and Z. Holmes. Out-of-distribution generalization for learning quantum dynamics. Nature Communications, 14:3751, 2023. doi: 10.1038/s41467-023-39381-w.
[70] K.-M. Chung and H.-H. Lin. Sample efficient algorithms for learning quantum channels in PAC model and the approximate state discrimination problem. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:22, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[71] M. C. Caro. Binary classification with classical instances and quantum labels. Quantum Machine Intelligence, 3:18, 2021. doi: 10.1007/s42484-021-00043-z.
[72] M. Fanizza, Yihui Quek, and M. Rosati. Learning quantum processes without input control. 2022. arXiv:2211.05005.
[73] S. T Flammia and Joel J Wallman. Efficient estimation of Pauli channels. ACM Transactions on Quantum Computing, 1(1):1–32, 2020. doi: 10.1145/3408039.
[74] S. T Flammia and R. O’Donnell. Pauli error estimation via population recovery. Quantum, 5: 549, 2021. doi: 10.22331/q-2021-09-23-549.
[75] O. Fawzi, A. Oufkir, and D. Stilck França. Lower bounds on learning Pauli channels. 2023. arXiv:2301.09192.
[76] R. Harper, S. T. Flammia, and J. J. Wallman. Efficient learning of quantum noise. Nature Physics, 16(12):1184–1188, 2020. doi: 10.1038/s41567-020-0992-8.
[77] C. Rouzé and D. S. França. Efficient learning of the structure and parameters of local Pauli noise channels. 2023. arXiv:2307.02959.
[78] S. Chen, S. Zhou, A. Seif, and L. Jiang. Quantum advantages for Pauli channel estimation. Physical Review A, 105(3):032435, 2022. doi: 10.1103/PhysRevA.105.032435.
[79] S. Chen, C. Oh, S. Zhou, H.-Y. Huang, and L. Jiang. Tight bounds on Pauli channel learning without entanglement. 2023. arXiv:2309.13461.
[80] S. Chen and Weiyuan Gong. Futility and utility of a few ancillas for Pauli channel learning. 2023. arXiv:2309.14326v1.
[81] S. Chen and Weiyuan Gong. Efficient Pauli channel estimation with logarithmic quantum memory. 2023. arXiv:2309.14326.
[82] A. Rakhlin, K. Sridharan, and A. Tewari. Online learning via sequential complexities. Journal of Machine Learning Research, 16(6):155–186, 2015.
[83] A. Rakhlin, K. Sridharan, and A. Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 161:111–153, 2015. doi: 10.1007/ s00440-013-0545-5.
[84] S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(6):121–164, 2012. doi: 10.4086/toc.2012.v008a006.
[85] V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. In Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30–June 3, 2010. Proceedings 29, pages 1–23. Springer, 2010. doi: 10.1007/978-3-642-13190-5_1.
[86] G. Gutoski. On a measure of distance for quantum strategies. Journal of Mathematical Physics, 53(3):032202, 2012. doi: 10.1063/1.3693621.
[87] H.-Y. Huang, Yunchao Liu, M. Broughton, I. Kim, Anurag Anshu, Zeph Landau, and Jarrod R McClean. Learning shallow quantum circuits. 2024. arXiv:2401.10095.
[88] J. Haah, R. Kothari, and E. Tang. Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 135–146. IEEE, 2022. doi: 10.1109/FOCS54457.2022.00020.
[89] Daniel Stilck França, Liubov A Markovich, VV Dobrovitski, Albert H Werner, and Johannes Borregaard. Efficient and robust estimation of many-qubit hamiltonians. Nature Communications, 15(1):311, 2024. doi: 10.1038/s41467-023-44012-5.
[90] Andi Gu, Lukasz Cincio, and Patrick J Coles. Practical hamiltonian learning with unitary dynamics and gibbs states. Nature Communications, 15(1):312, 2024. doi: 10.1038/s41467-023-44008-1.
[91] F. Wilde, A. Kshetrimayum, I. Roth, D. Hangleiter, R. Sweke, and J. Eisert. Scalably learning quantum many-body Hamiltonians from dynamical data. 2022. arXiv:2209.14328.
[92] W. Yu, J. Sun, Z. Han, and X. Yuan. Robust and efficient Hamiltonian learning. Quantum, 7: 1045, 2023. ISSN 2521-327X. doi: 10.22331/q-2023-06-29-1045.
[93] H.-Y. Huang, Yu Tong, Di Fang, and Yuan Su. Learning many-body Hamiltonians with Heisenberg-limited scaling. Physical Review Letters, 130(20):200403, 2023. doi: 10.1103/ PhysRevLett.130.200403.
[94] H. Li, Y. Tong, H. Ni, T. Gefen, and L. Ying. Heisenberg-limited Hamiltonian learning for interacting bosons. 2023. arXiv:2307.04690.
[95] T. Möbus, A. Bluhm, M. C. Caro, A. H. Werner, and C. Rouzé. Dissipation-enabled bosonic Hamiltonian learning via new information-propagation bounds. 2023. arXiv:2307.15026.
[96] J. Castaneda and N. Wiebe. Hamiltonian learning via shadow tomography of pseudo-Choi states. 2023. arXiv:2308.13020.
[97] A. Bakshi, A. Liu, A. Moitra, and E. Tang. Learning quantum Hamiltonians at any temperature in polynomial time. 2023. arXiv:2310.02243.
[98] J. Haah, R. Kothari, and E. Tang. Learning quantum Hamiltonians from high-temperature Gibbs states and real-time evolutions. Nature Physics, pages 1–5, 2024. doi: 10.1038/ s41567-023-02376-x.
[99] A. Bluhm, M. C. Caro, and A. Oufkir. Hamiltonian property testing. 2024. arXiv:2403.02968.
[100] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. Structure learning of Hamiltonians from real-time evolution. 2024. URL https://arxiv.org/abs/2405.00082. arXiv preprint arXiv:2405.00082.
[101] J. Watrous. The theory of quantum information. Cambridge University Press, 2018. doi: 10.1017/9781316848142.
[102] W. Dür, M. Hein, J. I. Cirac, and H.-J. Briegel. Standard forms of noisy quantum operations via depolarization. Physical Review A, 72:052326, 2005. doi: 10.1103/PhysRevA.72.052326.
[103] J. Burniston, M. Grabowecky, C. M. Scandolo, G. Chiribella, and G. Gour. Necessary and sufficient conditions on measurements of quantum channels. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 476(2236):20190832, 2020. doi: 10.1098/rspa.2019.0832.
[104] A. Y. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191, 1997. doi: 10.1070/RM1997v052n06ABEH002155.
[105] G. Gutoski. Quantum strategies and local operations. PhD thesis, University of Waterloo, 2010. https://arxiv.org/abs/1003.0038.
[106] G. Chiribella, G. M. D’Ariano, and P. Perinotti. Quantum circuit architecture. Physical Review Letters, 101:060401, 2008. doi: 10.1103/PhysRevLett.101.060401.
[107] A. Lowe. Learning Quantum States Without Entangled Measurements. Master’s thesis, University of Waterloo, 2021.
[108] Y. Freund and R. E. Schapire. Adaptive Game Playing Using Multiplicative Weights. Games and Economic Behavior, 29(1):79–103, 1999. ISSN 0899-8256.
[109] N. Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2):212–261, 1994. doi: 10.1006/inco.1994.1009.
[110] S. Arora and S. Kale. A Combinatorial, primal-dual approach to semidefinite programs. J. ACM, 63(2), 2016. ISSN 0004-5411. doi: 10.1145/2837020.
[111] S. Arora, E. Hazan, and S. Kale. Fast algorithms for approximate semidefinite programm. using the multiplicative weights update method. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 339–348, 2005.
[112] R. Jain, Z. Ji, S. Upadhyay, and J. Watrous. QIP = PSPACE. Journal of the ACM, 58(6), 2011. ISSN 0004-5411.
[113] Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6(34):995–1018, 2005.
[114] Y. Freund and R. E. Schapire. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. ISSN 0022-0000.
[115] D. Petz. Bregman divergence as relative operator entropy. Acta Mathematica Hungarica, 116: 127–131, 2007.
[116] F. G. S. L. Brandão, W. Chemissany, N. Hunter-Jones, R. Kueng, and J. Preskill. Models of quantum complexity growth. PRX Quantum, 2:030316, 2021. doi: 10.1103/PRXQuantum.2. 030316.
[117] J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, and N. Yunger Halpern. Linear growth of quantum circuit complexity. 2021. arXiv:2106.05305.
[118] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. doi: 10.1017/9781108231596.
[119] S. Floyd and M. Warmuth. Sample compression, learnability, and the Vapnik-Chervonenkis dimension. Machine learning, 21:269–304, 1995. doi: 10.1023/A:1022660318680.
[120] S. Hanneke, A. Kontorovich, and M. Sadigurschi. Sample compression for real-valued learners. In A. Garivier and S. Kale, editors, Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pages 466–488. PMLR, 2019.
[121] J. D. Halpern and A. Levy. The ordering theorem does not imply the axiom of choice. Notices of the American Mathematical Society, 11:56, 1964. doi: 10.1007/978-94-015-8988-8_4.
[122] J. D. Halpern and A. Levy. The Boolean prime ideal theorem does not imply the axiom of choice. Axiomatic Set Theory, Proc. Sympos. Pure Math. 13, Part I, 83-134 (1971)., 1971.
[123] C. González. Dense orderings, partitions and weak forms of choice. Fundamenta Mathematicae, 147(1):11–25, 1995.
[124] A. A. Fraenkel and Y. Bar-Hillel. Foundations of Set Theory. Elsevier, Atlantic Highlands, NJ, USA, 1973.
[125] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. doi: 10.1137/1116025.
[126] O. Borisovich Lupanov. Ob odnom métodé sintéza shém (on a method of circuit synthesis). Izvéstiá vysših učébnyh zavédénij, Radiofizika, 1:120–140, 1958.
[127] T. Toffoli. Reversible computing. In International colloquium on automata, languages, and programming, pages 632–644. Springer, 1980. doi: 10.1007/3-540-10003-2_104.
[128] J. J. Vartiainen, M. Möttönen, and M. M. Salomaa. Efficient decomposition of quantum gates. Physical Review Letters, 92(17):177902, 2004. doi: 10.1103/PhysRevLett.92.177902.
[129] M. Möttönen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa. Quantum circuits for general multiqubit gates. Physical Review Letters, 93(13):130502, 2004. doi: 10.1103/PhysRevLett.93. 130502.
[130] V. V. Shende, S. S Bullock, and I. L. Markov. Synthesis of quantum logic circuits. In Proceedings of the 2005 Asia and South Pacific Design Automation Conference, pages 272–275, 2005. doi: 10.1145/1120725.1120847.
[131] A. A. Mele and Y. Herasymenko. Efficient learning of quantum states prepared with few fermionic non-gaussian gates. 2024. arXiv:2402.18665.
[132] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM (JACM), 33(4):792–807, 1986.
[133] A. Banerjee, C. Peikert, and A. Rosen. Pseudorandom functions and lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 719–737. Springer, 2012. doi: 10.1007/978-3-642-29011-4_42.
[134] S. Arunachalam, A. B. Grilo, and A. Sundaram. Quantum hardness of learning shallow classical circuits. SIAM Journal on Computing, 50(3):972–1013, 2021. doi: 10.1137/20M1344202.
[135] J. Watrous. Semidefinite programs for completely bounded norms. Theory of Computing, 5: 217–238, 2009. doi: 10.4086/toc.2009.v005a011.
[136] R. R. Tucci. Quantum Bayesian nets. International Journal of Modern Physics B, 09(03): 295–337, 1995. doi: 10.1142/S0217979295000148.
[137] D. Beckman, Daniel Gottesman, M. A. Nielsen, and J. Preskill. Causal and localizable quantum operations. Physical Review A, 64:052309, 2001. doi: 10.1103/PhysRevA.64.052309.
[138] T. Eggeling, D. Schlingemann, and R. F. Werner. Semicausal operations are semilocalizable. Europhysics Letters, 57(6):782, 2002. doi: 10.1209/epl/i2002-00579-4.
[139] O. Oreshkov, F. Costa, and C. Brukner. Quantum correlations with no causal order. Nature Communications, 3:1092, 2012.
[140] F. Costa and S. Shrapnel. Quantum causal modelling. New Journal of Physics, 18(6):063032, 2016. doi: 10.1088/1367-2630/18/6/063032.
[141] J.-M. A. Allen, J. Barrett, D. C. Horsman, C. M. Lee, and R. W. Spekkens. Quantum common causes and quantum causal models. Physical Review X, 7:031021, 2017. doi: 10.1103/PhysRevX.7.031021.
[142] D. Kretschmann and R. F. Werner. Quantum channels with memory. Physical Review A, 72: 062323, 2005.
[143] Y. Aharonov, S. Popescu, J. Tollaksen, and L. Vaidman. Multiple-time states and multiple-time measurements in quantum mechanics. Physical Review A, 79:052110, 2009. doi: 10.1103/ PhysRevA.79.052110.
[144] I. S. Dhillon and J. A. Tropp. Matrix Nearness Problems with Bregman Divergences. SIAM Journal on Matrix Analysis and Applications, 29(4):1120–1146, 2008.
Although all of our results have been phrased for n-qubit systems and channels, they apply equally well to qudit systems and qudit channels. This essentially amounts to replacing all of the Pauli operators Heisenberg–Weyl operators, sometimes known as the qudit/generalized Pauli operators. These operators are defined as [101]
where the addition in the definition of X(x) is performed modulo d, with . These operators are unitary and orthogonal, i.e.,
for . Consequently, they form a basis for the vector space L(
) of linear operators acting on
qudit Bell states are then defined as
The qudit Bell state vectors form an orthonormal basis for
, and the qudit Bell states Φ
form a POVM, meaning that
The qudit/generalized Pauli channels are defined analogously to n-qubit Pauli channels as
where [0, 1] and
form
It follows from this (and using orthonormality of the Bell states) that the error rates p(z, x) can be obtained as
for all . In other words, we can recover the error rates by performing the qudit Bell basis measurement on the Choi state
) of the channel. Conversely, every positive semi-definite bipartite operator
L(
) of the form (A.5) corresponds to a Pauli channel with error rates gives by
For a quantum channel N : L(L(
, we define its (qudit) Pauli-twirled version as
where the superscript “W” in refers to the set
:
of qudit Pauli operators. In Proposition 59, we show that the twirled channel
is indeed a Pauli channel.
Figure 5: (Top) A multi-time quantum process with r = 4 time steps. The input systems are , the output systems are
, and the memory systems are
(Bottom) Every multi-time process is associated with the channel
, obtained by collapsing the causal ordering of the inputs and outputs.
In this section, we provide some background on multi-time quantum processes. Such objects are also known as “quantum strategies” [60] and “quantum combs” [57], and they also constitute specific examples of quantum causal networks [57, 136–141] and quantum channels with memory [142]. They also provide a model for discrete-time non-Markovian quantum stochastic processes [61, 62], and it is in this context that they are known as “multi-time quantum processes”—see also Refs. [63, 143].
B.1 Definitions and basic properties
A general multi-time process is depicted in Figure 5 (top) as the comb object in blue with r = 4 time steps. The input systems are , the output systems are
, and the memory systems are
. Every multi-time process is associated with a quantum channel
), defined by concatenating the maps
in the manner shown in Figure 5 (bottom). As shown in Refs. [57, 60], due to the causal constraints, the Choi representation of the channel
, which completely characterizes the multi-time process, is in one-to-one correspondence with a set of so-called comb operators, which have a very specific structure based on the causal ordering of the individual elements of the process.
Definition 51 (Comb operator for multi-time quantum process). Every multi-time quantum process with time steps, as depicted in Figure 5, is represented by a positive semi-definite comb operator
, defined to be the Choi representation of the quantum channel associated with the process (see Figure 5). For every comb operator
, there exist positive semi-definite operators
, such that the following constraints are satisfied:
A positive semi-definite operator ) is the comb operator of an r-step multi-time quantum process with input systems
and output systems
if and only if there exists a set
of positive semi-definite operators such that
and the constraints in (B.1)–(B.3) are satisfied. We let
) denote the convex set of all operators in L(
) representing r-step multi-time quantum processes with input systems
and output systems
To understand Definition 51, let us see how the constraints on the comb operators in (B.1)–(B.3) are manifested in the Choi representation of the channel depicted in Figure 5 (bottom). By definition, we have
which is precisely the constraint in (B.1), where in the last line we let
In a similar manner, we find that
Tr
Tr
which reproduces the constraints in (B.2) and (B.3).
We can also consider a multi-time process with a measurement in the final time step, sometimes called a “measuring strategy”.
Definition 52 (Comb operators for multi-time quantum process with measurement). Every multi-time quantum process with measurement, consisting of time steps and input systems
Figure 6: Concatenation of a multi-time process blue quantum comb, with a corresponding tester
, which is represented by the red quantum comb. The operations
can be arbitrary quantum channels, and they can also more generally be arbitrary Hermiticity-preserving maps.
and output systems
, is represented by a set
of positive semi-definite operators
L(
), such that
). A finite set
of positive semi-definite operators in L(
) defines an r-step multi-time quantum process with measurement, with input systems
and output systems
, if and only if
A measurement, or tester, for a multi-time process is another multi-time process that consists of an input state in the first time step and a measurement in the final time step, as shown by the red comb object in Figure 6 for
co-strategies”.
Definition 53 (Comb operators for multi-time quantum tester). Every multi-time quantum tester with time steps, consisting of input systems
and output systems
, is represented by a set
of positive semi-definite operators, with
), such that
) is the set of all multi-time processes in which the first input system is trivial; see (2.29). A finite set
of positive semi-definite operators in L(
an r-step multi-time quantum tester, with input systems
and output systems
if and only if there exists
) such that
B.2 Norms
Norms for multi-time quantum processes have been defined in Refs. [86, 106]. Here, we follow the presentation in Ref. [86].
Definition 54 (Strategy norm and its dual [86]). Let . For every Hermitian operator
), we define the strategy norm
and its dual
For every Hermiticity-preserving linear map : L(
L(
), in particular those corresponding to multi-time processes, its strategy r-norm is defined via the Choi representation as
The norms and
are (Hölder) dual to each other, and the proof of this can be found in Ref. [86]. These norms should be thought of as generalizations of the trace norm and its dual (the spectral/operator norm) for quantum states and the diamond norm and its dual for quantum channels. Indeed, with respect to Figure 6, in the case
and
, where we note that
for every Hermitian operator H. Similarly, in the case r = 1 and arbitrary dimension for the system , we have that
, i.e., the Hölder dual to the diamond norm, has been considered before in Ref. [105, Section 5.3]. This dual norm is the relevant norm when considering observables for quantum channels, analogous to the role that the spectral norm
has for observables for states. Using (B.14), it is straightforward to see that the diamond norm dual is given by the following primal-dual pair of semi-definite programs, where
L(
) is Hermitian:
We now show that this norm is multiplicative for tensor-product operators, which is a relevant property when considering channel observables without memory; see Section 2.1 for the relevant background information.
Lemma 55 (Diamond norm dual for tensor-product operators). Let L(
) and
L(
) be Hermitian operators. It holds that
Proof. This follows straightforwardly from semi-definite programming duality. Let be the operators achieving the trace norm
, as in (B.15), and let
L(
) be the operators achieving the spectral norm
, as in (B.17). Then,
+
and
are readily verified to be feasible points in the SDP (B.19), which means that
. For the reverse inequality, observe that
) achieves the trace norm
according to (B.16), is a feasible point in the SDP (B.20). Consequently, which this choice of Y , we obtain
This completes the proof.
Let be the comb operator of a multi-time process with
time steps, and let
be the comb operator of a multi-time process with
time steps, such that both processes have some compatible input and output Hilbert spaces. The multi-time process resulting from the composition of the two processes is represented by the comb operator
represents the link product [57].
Just as the diamond norm is submultiplicative with respect to composition of linear maps, so too is the strategy norm submultiplicative with respect to concatenation of comb operators according to the link product. We prove this in our next result.
Proposition 56 (Submultiplicativity of the strategy norm). Let be the representation of a multi-time process with
time steps, and let
be the representation of a multi-time process with
time steps. Suppose that the composition of these processes, represented by
, produces a multi-time process with r time steps. Then, it holds that
Proof. This result follows straightforwardly from semi-definite programming duality. In particular, we make use of (B.13), which we restate here for convenience as
Now, let () be the optimal feasible points corresponding to
respectively, meaning that
and
. We now show that (
) constitutes a feasible point in the SDP in (B.22) for
, implying the desired result.
By definition, we have
The right-most inequalities can be rewritten as 0 and
0. Using the fact that the link product of positive semi-definite operators is positive semi-definite (see Ref. [57, Theorem 2]), we obtain (
0. Expanding the left-hand side of this inequality, we have
Similarly, we have
Adding the inequalities in (B.30) and (B.33), we obtain
As is positive semi-definite and defines a multi-time process with r steps, we conclude that (
) is a feasible point in the SDP in (B.22) for
, which implies the desired result.
Corollary 57 (Subadditivity of the strategy norm under composition). Let be representations of multi-time processes with
time steps, and let
be representations of multi-time processes with
time steps. Suppose that the composition of
multi-time processes with r time steps. Then,
Proof. By the triangle inequality, and making use of Proposition 56, we have
as required. Here, the last step used Proposition 56 together with the fact that The latter can for example easily be seen from Equation (B.22).
In this section, we prove (2.18), and thereby prove that the error-rate vector of the Pauli-twirled version of an arbitrary quantum channel N : L(L(
, is given by p(z, x) =
)] for all
. For generality, we prove the result in terms of qudit Pauli channels (see Appendix A), but an analogous proof to the one we present holds when the qudit Pauli operators are replaced by the n-qubit Pauli operators.
Lemma 58. For every qudit quantum channel N : L(L(
, the Choi representation of its Pauli-twirled version
, as defined in (A.7), is given by
Proof. By definition of the Choi representation, we have
as required, where for the third equality we have used the “transpose trick” (which holds for every linear operator
Proposition 59. Let , and define
to be the pinching channel in the qudit Bell basis:
It holds that
Consequently, for every channel N : L(L(
), the Choi representation of its Pauli-twirled version
, defined in (A.7), is given by
)). Furthermore, the corresponding error-rate vector of the Pauli-twirled channel is given by
)] for all
Proof. We make repeated use of the following facts about the qudit Pauli operators [101]:
which hold for all choices of . Now, let us start by showing that
for all . To show this, we use the definition of Φ
in (A.3), the properties in (C.5)–(C.7), and the fact that the operators
form a basis for L(
Therefore, using (C.8), along with the properties in (C.5)–(C.7) once more, we obtain
which proves (C.3). Then, if ) is the Choi representation of a quantum channel N : L(
L(
), using Lemma 58 we see that
)]Φ
)]Γ
. By identifying with (A.5), we can see that the twirled channel is indeed a Pauli channel, and using (A.6), we see that the error-rate vector of the twirled channel is
. This completes the proof.
In this section, we provide an entropic analysis of the matrix multiplicative weights (MMW) algorithm (Algorithm 2 and its projected variant for Choi states (Algorithm 3). We note that an entropic analysis similar to the one we provide here can be found in Ref. [84, Theorem 2.4] for the multiplicative weights update (MWU) algorithm. On it highest level, the MMW algorithm assigns initial weights to experts iteratively updates these weights multiplicatively according to the feedback on how well the expert has performed. It is known as a method for highly efficiently solve convex optimization problems.
We start with a proof of Proposition 14. The bound we obtain applies also to the Hedge algorithm (Algorithm 5 below), which is a special case of the MMW algorithm (Algorithm 2) when the loss matrices of the MMW algorithm are all diagonal in the same basis, such that the diagonal elements of
constitute the loss vector
in the Hedge algorithm. The bound we obtain for the Hedge algorithm is in general tighter than the one obtained in Ref. [84, Theorem 2.3].
D.1 Proof of Proposition 14
We start by noticing that in the proof of [110, Theorem 3.1], the inequality
can be written as
Taking the logarithm on both sides leads to
Applying (D.3) recursively leads to
Now, let be an arbitrary density operator. Then, noting that the von Neumann entropy of
is given by
], we have that the relative entropy between
Noting further that
we obtain
where for the inequality on the last line we have used (D.3). This implies that
Then, because 0, we obtain
Finally, because , and because
), we can rearrange the inequality above to obtain the desired result.
Remark 60. Let us make the following observations about the result in (2.44).
• If we let be a rank-one density operator, then
over all such rank-one density operators to obtain
• It is worth noting that the MMW-based result for online learning of quantum states in Ref. [20, Theorem 4] (see, in particular, the proof) presents the regret bound (using the notation of this section, and
for every density operator . Note that the regret bound in (2.44) can in general be tighter than this bound, because of the entropy term
), which is always non-negative.
• We can minimize the right-hand side of (2.44) with respect to , in order to obtain the best possible upper bound on the total expected loss. In other words,
From the connection between the MWW and Hedge algorithms noted at the beginning of this section, we immediately obtain the following regret bound for the Hedge algorithm from Proposition 14.
Corollary 61 (Entropic regret bound for the Hedge algorithm). Let , and consider a sequence
of loss vectors of size
along with the updates
provided by the Hedge algorithm in Algorithm 5. Then, the following inequality holds:
where q is an arbitrary probability vector.
D.2 The projected MMW algorithm
We start by defining the projection map as
where is a density operator and the relative entropy is
) is defined in (2.51). We make use of the fact that the relative entropy is a Bregman divergence [113, 115, 144]. In particular, for
density operators, with
positive definite, we have that
where
for P positive semi-definite and Q positive definite. It follows that the projection map in (D.14) is a Bregman projection; consequently, we have the so-called Pythagorean inequality [144],
for density operators . This inequality essentially tells us that projection only get us closer to the set of CPTP maps, in the sense that
which follows directly from (D.18), due to the fact that 0 for all density operators
. We also require the Pinsker inequality [101]: for all density operators
Finally, we make the observation that the update step 4 in the MMW algorithm (Algorithm 2
and Algorithm 3) can be written as
where we recall the expression for . With this observation, we can equivalently formulate Algorithm 3 as the lazy version of Algorithm 6 below, which is a mirror descent algorithm [46, Section 5.3].
Proposition 62 (Regret bound for lazy mirror descent for Choi states). Let be an arbitrary Choi state. Let
be the number of rounds of interaction, and consider a sequence
of cost matrices along with the updates
provided by the lazy version of Algorithm 6. Then,
Proof. It turns out that the lazy version of Algorithm 6 is equivalent to the regularized follow-the-leader algorithm [46, Section 5.3.1]. In particular, using Ref. [46, Lemma 5.5], it follows that the projection step for the lazy version of Algorithm 6 is given by
where the function F is defined in (D.16). Indeed, the gradient of the objective function on the right-hand side is equal to
where is an arbitrary positive semi-definite operator. At the same time, let us observe that the gradient step of the lazy version of Algorithm 6 is given by
where the last equality holds because
Therefore,
which implies that
Combining (D.24) and (D.28), and using the fact that the function F is strictly convex, we can conclude that (D.23) holds. The desired regret bound then follows by Ref. [20, Theorem 3], which considers the regularized follow-the-leader algorithm for quantum states.
Proposition 63 (Regret bound for agile mirror descent for Choi states). Let be an arbitrary Choi state. Let
be the number of rounds of interaction, and consider a sequence
of cost matrices along with the updates
provided by the agile version of Algorithm 6. Then,
Proof. Similar to the proof of Proposition 14 (see (D.7), in particular), the idea of the proof is to bound ) for every time step
. To this end, we start by noting that from the gradient step of the agile version of Algorithm 6, it holds that
for all . Using this, and with straightforward manipulations, we obtain the following:
Tr[
where for the inequality we have used (D.19), and we also made use of the fact that
which means that ) + log(Tr[
]). Now, let us bound
). Consider that
where we have used the Hölder inequality in the final line. Let us now use the fact that (0
for all
. Letting
and
, and using the Pinsker inequality (D.20), we obtain
which implies that
for all . Altogether, we have
for all . Summing over all t, we obtain
where the second inequality is due to the fact that 0 for all density operators
and
. After substituting
, we obtain the desired result.
Remark 64 (Extending Proposition 63 to multi-time processes). The key elements of the proof of Proposition 62 are the fact that we project onto a convex set in (D.14), such that the inequality in (D.19) holds, and the Pinsker inequality in (D.20). Consequently, it is straightforward to generalize Algorithm 6, and thus Proposition 62, to the Choi states of multi-times processes. In particular, letting ) be the set of multi-time processes with
time steps, as given in Definition 51, we define the relative entropy projection onto this set as
for all L(
0, where
. Then, by replacing step 6 in Algorithm 6 with the projection in (D.38), we obtain a mirror descent algorithm for Choi states of multi-time quantum processes. Then, the analogue of Proposition 62 is as follows. If
arbitrary Choi state of a multi-time process with r steps,
L(
) are cost matrices satisfying
, with
, and
are the projected Choi state updates resulting from the algorithm, then
which is directly analogous to (D.29).