Adaptive Online Learning of Quantum States

The motivation above suggests a learning problem that assumes the quantum state prepared at time step $t=1,2,\ldots,T$ is $\rho_{t}$. Due to imperfect calibration, $\rho_{t}$ at different time $t$ is different, and our goal is to learn $\rho_{t}$ in an online fashion. The problem of online learning of a changing concept has received significant attention in the machine learning literature, and we adapt several of these techniques to the quantum setting, which involves high-dimensional spaces over the complex numbers.

The first metric we consider is the "dynamic regret" introduced by zinkevich2003online [17], which measures the difference between the learner’s loss and that of a changing comparator. The dynamic regret bounds are usually characterized by how much the optimal comparator changes over time, known as the "path length."

Next, we consider a more sophisticated metric, the "adaptive regret," as introduced by hazan2009efficient [18]. This metric measures the maximum of the regret over all intervals, essentially taking into account a changing comparator. Many extensions and generalizations of the original technique have been presented in works such as daniely2015strongly [19, 20, 21]. Minimizing adaptive regret requires a combination of expert algorithms and continuous online learning methods, which we also adopt for the quantum setting.

In this paper, we systematically study adaptive online learning of quantum states. In quantum tomography, we might have prior knowledge about $\rho_{t}$, but in online learning, it can be adversarial. As such, we expect regret guarantees that extend beyond just comparing with the best fixed $\varphi\in C_{n}$. We study the following questions summarized in Table 1:

• •

  Dynamic regret: We consider minimizing regret under the assumption that the comparator $\varphi$ changes slowly:

  $\displaystyle\text{Regret}_{T,\mathcal{P}}^{\mathcal{A}}=\sum_{t=1}^{T}\ell_{t}\left(\operatorname{Tr}(E_{t}x_{t}^{\mathcal{A}})\right)-\min_{\varphi_{t}\in C_{n}}\sum_{t=1}^{T}\ell_{t}\left(\operatorname{Tr}(E_{t}\varphi_{t})\right),\text{ where }\mathcal{P}=\sum_{t=1}^{T-1}\|\varphi_{t}-\varphi_{t+1}\|_{\color[rgb]{0,0,0}1}.$

  (1)

  Here $\mathcal{P}$ is bounded and defined as the path length, the functions $\ell_{t}$ are $L$-Lipschitz for all $t\in[T]$, and $\|\cdot\|_{\color[rgb]{0,0,0}1}$ is the $\ell_{1}$ norm of the singular values of a matrix known as the nuclear norm. We propose an algorithm based on online mirror descent (OMD) that achieves an $\tilde{O}(\sqrt{nT\mathcal{P}})$ regret bound. Although the analysis shares the same spirit as the standard OMD proof, tackling optimization in the complex domain requires new tools from several areas. Specifically, we use Klein’s inequality from matrix analysis to study the dual update in OMD, and the Fannes–Audenaert inequality [22] from quantum information theory to obtain the dynamic regret bounds. Compared to aaronson2018online [5], our analysis is more general due to the introduction of these tools.

  As an application, under the assumption that $\varphi_{t}$ evolves according to a family of dynamical models, we can also prove $\tilde{O}(\sqrt{nT\mathcal{P}^{\prime}})$ dynamic regret bounds where $\mathcal{P}^{\prime}$ is a variant of path length defined in Eq. (6). This covers two natural scenarios: either the dynamics comes from a family of $M$ known models (which incurs a $\log M$ overhead), or we know that the dynamical model is an $O(1)$-local quantum channel, a natural assumption for current quantum computers fabricated by 2D chips [23, 24, 25] where a quantum gate can only influence a constant number of qubits.

• •

  Adaptive regret: We also consider minimizing the strongly adaptive regret [19] of an algorithm $\mathcal{A}$ at time $T$ for length $\tau$:

  $\displaystyle\text{SA-Regret}_{T}^{\mathcal{A}}(\tau)=\max_{I\subseteq[T],|I|=\tau}\bigg{(}\sum_{t\in I}\ell_{t}\left(\operatorname{Tr}(E_{t}x_{t}^{\mathcal{A}})\right)-\min_{\varphi\in C_{n}}\sum_{t\in I}\ell_{t}\left(\operatorname{Tr}(E_{t}\varphi)\right)\bigg{)}$

  (2)

  where $x_{t}^{\mathcal{A}}$ is the output of algorithm $\mathcal{A}$ at time $t$, and $\ell_{t}$ is a real loss function that is revealed to the learner, for example, $\ell_{t}(z)=|z-b_{t}|$ and $\ell_{t}(z)=(z-b_{t})^{2}$ for some $b_{t}\in[0,1]$.²²2Here we make no assumptions about how $\ell_{t}$ is revealed. In application, for example [1], they first obtain $b_{t}$ by repeated measurements and then compute $\ell_{t}$ classically. We show that combining algorithms from aaronson2018online [5], jun2017improved [20] gives an $O(\sqrt{n\tau\log(T)})$ bound for adaptive regret. We then derive an $O(\sqrt{knT\log(T)})$ regret bound when the comparator $\varphi$ is allowed to shift $k$ times.

• •

  Mistake bound: Given a sequence of two-outcome measurements $E_{1},E_{2},\ldots,E_{T}$ where each $E_{t}$ is followed afterward by a value $b_{t}$ such that $|\operatorname{Tr}(E_{t}\rho_{t})-b_{t}|\leq\epsilon/3$. Assuming the ground truth $\rho_{t}$ has $k$-shift or bounded path length $\mathcal{P}$, we build upon the regret bounds to derive upper bounds of the number of mistakes made by an algorithm whose output is a sequence of $x_{t}^{\mathcal{A}}\in[0,1]$, where $|x_{t}^{\mathcal{A}}-\operatorname{Tr}(E_{t}\rho_{t})|>\epsilon$ is considered a mistake. For dynamic regret and adaptive regret settings, we give mistake bounds in Corollary 1 and Corollary 4, respectively.

We also note that our results can be extended from two-outcome POVMs to $K$-outcome POVMs for $K\geq 2$, inspired by a recent work by gong2022learning [26]. A $K$-outcome measurements $\mathcal{M}$ can be described by $K$ $2^{n}\times 2^{n}$ Hermitian matrices $E_{1},\ldots,E_{K}$ such that $0\preceq E_{j}\preceq I,$ $\sum_{j=1}^{K}E_{j}=I$, and for any quantum state $\rho$, the measurement $\mathcal{M}$ outputs $j$ with probability $\mathrm{Tr}(E_{j}\rho)$. In our setting of online learning of quantum states, a sequence of measurements $\mathcal{M}_{t}$ is given and each $\mathcal{M}_{t}$ can be described by a set of Hermitian matrices $\{E_{t,1},E_{t,2},\ldots,E_{t,K}\}$. In Appendix C.1, we show that our algorithm has the same regret upper bound on it for any $K$ if we use the total variational norm as the loss function.

We also conduct numerical experiments for our algorithms about their dynamic and adaptive regret bounds on the $k$-shift and the path length settings. The results demonstrate that our algorithms improve upon non-adaptive algorithms when the quantum state is changing, confirming our theoretical results.

Let $\|\cdot\|_{\color[rgb]{0,0,0}1}$ denote the nuclear norm, i.e., the $\ell_{1}$ norm of the singular values of a matrix. Let $x\bullet y=\operatorname{Tr}(x^{\dagger}y)$ denote the inner trace product between $x$ and $y$. Denote $\lambda_{i}(X)$ to be the $i^{\text{th}}$ largest eigenvalue of a Hermitian matrix $X$. $X\succeq 0$ means that the matrix $X$ is positive semidefinite. For any positive integer $n$, denote $[n]:=\{0,1,\ldots,n-1\}$. Denote $\otimes$ to be the tensor product, i.e., for matrices $A=(A_{i_{1}j_{1}})_{i_{1}\in[m_{1}],j_{1}\in[n_{1}]}\in\mathbb{C}^{m_{1}}\times\mathbb{C}^{n_{1}}$ and $B=(B_{i_{2}j_{2}})_{i_{2}\in[m_{2}],j_{2}\in[n_{2}]}\in\mathbb{C}^{m_{2}}\times\mathbb{C}^{n_{2}}$, we have $A\otimes B=(A_{i_{1}j_{1}}\cdot B_{i_{2}j_{2}})_{i\in[m_{1}m_{2}],j\in[n_{1}n_{2}]}\in\mathbb{C}^{m_{1}m_{2}}\times\mathbb{C}^{n_{1}n_{2}}$ where $i=i_{1}m_{2}+i_{2}$, $j=j_{1}n_{2}+j_{2}$. Throughout the paper, $\tilde{O}$ omits poly-logarithmic terms.

We can obtain a mistake bound in this setting when we assume the ground truth $\rho_{t}$ has a bounded path length.

So far, we have not made assumptions on how the state evolves. However, in many cases, the quantum state only evolves under a family of dynamical models. A natural question is the following: If we know the family of possible dynamical models in advance, can we achieve a better dynamic regret?

First, we consider the case when there is a fixed family of dynamical models. The most general linear maps $\Phi\colon C_{n}\to C_{n}$ implementable on quantum computers are quantum channels satisfying:

• •

  Completely positive: For any $\rho\in C_{n}$ and $m$-dimensional identity matrix $I_{m}$, $\rho\otimes I_{m}\succeq 0$;

• •

  Trace preserving: $\operatorname{Tr}(\Phi(\rho))=\operatorname{Tr}(\rho)=1$ for any quantum state $\rho\in C_{n}$.

A common example is $\Phi(x)=e^{iHt}xe^{-iHt}$, where $H$ is a background Hamiltonian that evolves the quantum state following the Schrödinger equation.

We first consider the case with $M$ possible dynamical models $\{\Phi^{(1)},\ldots,\Phi^{(M)}\}$, each of which is a quantum channel. Following hall2013dynamical [34] and zhang2018adaptive [28], we restrict a variant of the path length of the comparator:

In general, the possible dynamical models can be a continuous set. Considering that current quantum computers [23, 24, 25] commonly use 2D chips where a quantum gate only influences a constant number of qubits, it is natural to consider $l$-local quantum channels where each channel only influences at most $l$ qubits (and perform identity on the other $n-l$ qubits), and the following result holds. The proofs of Corollary 2 and Corollary 3 are deferred to Appendix B.

As an application of Lemma 1, we derive a $k$-shift regret bound. In the $k$-shift setting, we assume that $\varphi$ can change at most $k$ times, and we derive the following theorem.

With Theorem 2 in hand, when we further assume that the ground truth $\rho_{t}$ also shifts at most $k$ times, we can derive the following mistake bound.

The proofs of the claims in this section are deferred to Appendix C.

One eminent strength of adaptive online learning of quantum states is its ability to capture the changing states. Previous algorithms such as regularized follow-the-leader (RFTL) perform well for predicting fixed quantum states [5], but they are not adaptive when the quantum state evolves. We compare the cumulative regret produced by RFTL and our algorithms in the $k$-shift setting and the path length setting. The results are illustrated as follows.

The advantage of our algorithms in the $k$-shift setting is presented in Figure 1. In Subfigure(a), we plot the long term changes of the cumulative regret. The two curves have similar trends but CBCE achieves smaller regret. In Subfigure(b)-(f), we choose a small time scale $T=20$ to display the details. It is clearly shown that the distances between two curves grow larger as $T$ increases, which means our algorithm maintains the advantage in the long run.

Figure 2 shows the advantage of our algorithms in the path length setting. In Subfigure(a) and (b), we plot the comparison between our Algorithm 1 (denoted by “DOMD”) and the non-adaptive algorithm RFTL with different learning rates. It can be seen that in a single run, our algorithm attains the minimum regret and is comparable to RFTL with the best learning rate. Indeed, given the similarity of RFTL and OMD, we expect RFTL with the optimal learning rate to do as well as DOMD in practice. However, since the optimal learning rate for OMD depends on the path length, it is unknown a priori, and non-adaptive methods require more tuning to achieve good performance. In Subfigure(c) and (d), we plot the comparison between our Algorithm 3 (denoted by “CBCE”) and the non-adaptive RFTL with different $\eta$. There is a significant gap between the regret of CBCE and RFTL with the best learning rate from the grid search, demonstrating the interesting phenomenon that empirically, CBCE with adaptive regret guarantees also does well in the path length setting.

We also conduct experiments to verify our adaptive regret bound $O(\sqrt{knT\log T})$ in the $k$-shift setting (Theorem 2). Results are shown in Figure 3.

In Subfigure(a), we plot the average regret $R_{\text{aver}}=\text{regret}_{T}/T$ as $T$ grows. Every data-point was executed by 100 random experiments and taking the maximum regret, since regret is an upper bound. Under different parameter choices $(k,n)$, $R_{\text{aver}}$ always converges to 0 when $T$ increases, implying a sublinear regret $R_{k\text{-shift}}$. More concretely, curves with larger $k$ has larger $R_{\text{aver}}$ and converges more slowly, consistent with the intuition that more shifts make the learning task more difficult.

In Subfigure(b), to verify the precise bound we plot the ratio $C=\text{regret}_{T}/\sqrt{knT\log T}$. We choose $n=2,k=10,T=200$, and repeat the experiments 50 times randomly. We then plot the maximum of the regret constant $C$ on every interval. As the figure shows, the ratio is limited by a constant $C\leq 0.07$. This strongly supports our upper bound $O(\sqrt{knT\log T})$ on $\text{regret}_{T}$ with every fixed $n$.

In addition, we conduct experiments in terms of average regret $R_{\text{aver}}$ and ratio term $C_{\text{path}}=R_{\text{path}}/\sqrt{T(n+\log T)\mathcal{P}}$ to testify our dynamic regret bound $O(L\sqrt{T(n+\log T)\mathcal{P}})$ in the path length setting (Theorem 1). Results are shown in Figure 4.

In Subfigure(a), we plot the change of average regret $R_{\text{aver}}=\text{regret}_{T}/T$. We observe that as $T$ grows, $R_{\text{aver}}$ converges to 0 with different pairs of $(n,\mathcal{P})$, indicating that $R_{\text{path}}$ is sublinear with respect to $T$. In addition, the blue curve representing the average regret of a 2-qubit quantum state appears higher than the orange curve representing the average regret of a 1-qubit quantum state, consistent with the fact that our regret bound depends polynomially on the number of qubits.

In Subfigure(b), we choose different scales of $T$ to demonstrate how the ratio $C$ evolves in the long term. For every fixed $T$, we execute 100 random experiments and take the maximum ratio term $C$. Although there are noticeable fluctuations, it can be seen that the curve is non-increasing and only fluctuates within a fixed interval of 0 to 0.065, which shows that $C$ has a constant upper bound $C^{\prime}=0.065$. In conclusion, $R_{\text{path}}/\sqrt{T(n+\log T)\mathcal{P}}$ is within the range of a small positive constant.