Maximum-Likelihood Quantum State Tomography by Soft-Bayes
Authors: Chieng-Ming Lin
Yu-Ming Hsu
Yen-Huan Li
Venue: NeurIPS 2022 Submitted (2022)

Abstract: Quantum state tomography (QST), the task of estimating an unknown quantum state given measurement outcomes, is essential to building reliable quantum computing devices. Whereas computing the maximum-likelihood (ML) estimate corresponds to solving a finite-sum convex optimization problem, the objective function is not smooth nor Lipschitz, so most existing convex optimization methods lack sample complexity guarantees; moreover, both the sample size and dimension grow exponentially with the number of qubits in a QST experiment, so a desired algorithm should be highly scalable with respect to the dimension and sample size, just like stochastic gradient descent. In this paper, we propose a stochastic first-order algorithm that computes an $\varepsilon$-approximate ML estimate in $O( ( D \log D ) / \varepsilon ^ 2 )$ iterations with $O( D^3 )$ per-iteration time complexity, where $D$ denotes the dimension of the unknown quantum state and $\varepsilon$ denotes the optimization error. Our algorithm is an extension of Soft-Bayes to the quantum setup.

Maximum-Likelihen Quantum State Tomography by Soft-Bayes
Anonymous Author(s) Affiliation Address email
Abstract
Quantum state tomography (QST), the task of estimating an unknown quantum state given measurement outcomes, essential building reliable quantum computing devices. Whereas computing the maxinum-likelihodd (MI.) estimate corresponds solving finite-sum convex optimization problem, the objective function is not smooth nor Lipschitz, so most existing convex optimization methods lack sample complexity guarantees; moreover, both the sample size and dimension grow expo- nentially with the number of qubits in a QST experiment, so a desired algorithm should be highly scalable with respect to the dimension and sample size, just like stochastic gradient descent. In this paper, we propose a stochastic first-order algo- rithm that computes an E-approximate ML estimate in O((D log D) iterations with O (D*) per-iteration time complexity, where D denotes the dimension of the unknown quantum state and denotes the optimization error. Our algorithm is an extension of Soft-Bayes to the quantum setup.
3
10
11
12
Introduction
14
Quantum state tomography (QST), the task of estimating unknown quantum state given measurement outcomes, is essential to building reliable quantum computing devices [52]. The states of the quantum bits (qubits) prepared by experimental apparatus estimated, in order to check the correctness of the apparatus and, if needed, determine how to calibrate it. Moreover, quantum process tomography, the task of estimating
16
18
unknown quantum channel, can also be cast as a QST problem [7]. There are various approaches to QST, such as trace regression [49] 28
20
63 64]
and recently proposed deep learning-baat baaee methods S 53 Among existing approaches, the ML. approach has
meximum-likelihood likelihood (ML) estimation 33 34 12]
Bayesian estimation [1O
22
been widely adopted for its relatively low estimation error in practice and asymptotic statistical
24
guarantees in theory 34 (55)
Computing the ML estimator amounts to solving optimization problem. Whereas the optimization problem convex, standard convex optimization methods are not directly applicable. It is easily checked that the negative ligelikel function in ML QST is neither Lipschitz nor smooth, violating standard assumptions in optimization literature [39] 24). Hence, for example, even whether vanilla gradient descent converges for QST is unclear. This is perhaps why RpR, a heuristic algorithm known to be empirically fast, was developed via an expectation maximization, instead Unfortunately, RpR does not always converge (60]. The negative log-likelihood function is indeed self-concordant, so Newton's method is readily applicable
26
28
30
of convex optimization, argument 43 44
32
33
455. Nevertheless, the dimension of quantum state grows exponentially with the number of qubits; the Hessian computations in Newton's 's method are computationally too expensive when the dimension is high. There a few first-order (i.e., gradient-based convex optimization algorithms
34
35
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

36
provably converging for ML QST, such as diluted RpR 60 27. and entropic mirror descent with line search 39 These are all
SCOPT [57 NoLips 19, the
37
Frank-Wooff Wolfe method 48 24 65
38
batch methods. As they require computing the full gradient in every iteration, their per-iteration time complexities are at least linear in the sample size. To estimate a quantum state, has been proved that the sample size must be exponential in the number of qubits [47 17].
39
40
41
Regarding the high dimension and sample size issues in ML QST, it is desirable to, like how we handle the same issues in modern machine learning applications, develop a stochastic first-order optimization method for ML QST. A stochastic first-order optimization method takes one or a few, instead of all, samples in each iteration and avoids computationally expensive Hessian computations. The stochastic quasi-Newton method for self-concordant minimization of Zhou et al. [66] seems to apply. Nevertheless, its step size selection rule involves Hessian computations; moreover, its analysis assumes a bounded Hessian, which does not hold in MI. QST. The stochastic mirror-prox and stochastic primal-dual hybrid gradient methods were considered for problems very similar to MI
42
43
44
45
48
47
48
49
QST 16 32]. However, their analyses assume either a bounded dual domain or Lipschitznes:; both are violated in ML QST.
51
In this paper, we propose a stochastic first-order algorithm for ML QST. We design the algorithm by an online learning argument. Consider an online convex optimization problem, where the loss function in each round corresponds to the negative log- likelihood function corresponding to one data point in ML QST. Interestingly, this online convex optimization problem is exactly the quantum analogue of online portfolio selection, a celebrated online learning problem 19 20]. Since the ML approach aims to minimize the empirical average of the negative log-likelihood, once we "quantumize" any existing first-order online portfolio selection algorithm that no-regret and apply an online-to-ban to-batch conversion [1 22]. the resulting algorithm becomes a stochastic first-order algorithm for ML QST.
52
53
54
55
56
57
58
59
We refer the reader to Section 2 for an introduction of relevant concepts.
60
The algorithm we choose to "quantumize" is Soft-Bayes [51]. There are two reasons. First, the per-round time complexity of Soft-Bayes is linear in the ambient dimension, arguably the lowest one can expect; second, Soft- Soft-Bayes has a curious connection with expectation maximization 43 44 (see Section 55.. We call the resulting algorithm Stochastic Q-Soft-Bayes, Stochastic Q-Soft-B Bayte processes one randomly chosen data point in each iteration. Suppose the quantum state to be estimated represented by a DD- density matrix. The per-iteration time complexity of Stochastic Q-Soft- Bayes is O(D3), ). independent of the sample size. The expected optimization error of Stochastic Q- Soft-Bayes converges to zero at O( (V/TT) log D) rate, where T denotes the number of iterations.
61
62
63
64
65
66
68
The main technical difficulty lies in figuring out an appropriate quantum extension of Soft- Soft-Bayes that coincides with Soft-Bayes when all matrices involved share the same eigenspace and allows for a regret analysis. This challenging because for any given "non-quantum" expression, one can immediately find many candidates for its quantum extension, but only a few or one of them inherit
89
70
71
72 the desired theoretical properties of their moonnquantum" counterpart; see, e.g., the discussion in 162] Chapter 11] for extending information theoretic quantities to the quantum case. Similar to the 73
74 quantum extension of exponentiated gradient update by Tsuda et al. [58], the quantum extension we
find reveals the complicated mathematical structure of Soft-Bayes hidden in the "non-quantum" setup,
78 Instead of empirically beating state of the arts, our aim is to give the first provably fast stochastic
77 first-order algorithm for ML QST. Section 3.3 shows that Stochastic Q-Soft- Bates is competitive existing batch algorithms. Section Isows that Stochastic-Sole 79 Bayes is empirically even faster than RpR in terms of the number of epochs. Unfortunately. Section
78 in time complexity in comparison
80 shows that in terms of the elapsed time, O-Soft-Baye may not be satisfactory to practitioners.
81 We discuss the possibility of developing faster stochastic first-order methods in Section 5
1.1
Related work
textbook approach to quantum state tomography is to approximate the problem as a trace regression 84 problem [46] and compute the corresponding ceastesquares estimate or directly minimize the expected
83
85 square loss, sometimes with regularization [49 28 25 64 [3) Since minimizing the square loss
86 arguably the most standard problem in optimization and machine learning, many existing algorithms
87 apply. Youssry et al. [64] proved the convergence of stochastic entropic mirror descent. Yang et al.
A similar algorithm is proposed and studied in 26). but the bounded Hessian assumption therein renders the algorithm inapplicable to ML QST.

---

86
showed that several standard online learning algorithmss are no-regret for the corresponding online trace regression problem. Notice that both papers do not consider the ML formulation.
63
89
90
Quantum state tomography schemes optimal or nearly optimal in sample complexity are known
47
91
30
38 29]. The optimal schemes require entangled measurements, challenging to implement 47
30
92
If only incoherent measurements (as in the ML QST scheme considered in this paper) are allowed,
93
the scheme by Kueng al. [8 is optimal [17: nevertheless, the scheme still challenging to
94
implement [38 p. 97]. The scheme proposed by Gută et al. [29] is nearly optimal, but the numerical
95
result in 29 Figure 1] shows that the ML approach achieves a smaller estimation error empirically.
96 A problem closely related to quantum state tomography is shadow tomography, in which one is not interested in recovering the quantum state but estimating the probability distributions of its measurement outcomes [.. Aaronson et al. showed that shadow tomography can be done in an online fashion, via follow the regularized leader with the von Neumann entropy 2 We emphasize that shadow tomography is fundamentally different from quantum state tomography. Indeed, Aaronson showed shadow tomography is strictly easier than state tomography, in the sense that the former requires much less samples than the latter (.. Another closely related problem is the quantum version of individual sequence prediction considered by Koolen et al. (37. The loss function studied in K7 is the trace-log loss, instead of the log-trace loss we consider, as discussed in Section 4 of their paper.
98
99
100
101
102
103
104
Our algorithm is developed via "quantumizing" an online portfolio selection algorithm. Online portfolio selection is a classic online learning problem. It is known that the optimal regret of online portfolio selection is O D) log TT,, where 1) denotes the ambient dimension and T denotes the number of rounds, and is achieved by Universal Portfolio Selection (UPS) 19 20). However, UPS
106
107
108
109
computationally too expensive to be practical [5 There are several algorithms that try to balance between the regret and computational complexity, but none of them is optimal in both aspects 42 [59].
110
Soft-Bayes strikes balance with a O(D) per-round time complexity and OVVTDlog D) regret.
111
112
Recently, Zimmert et al. [67] "quantumized" another online portfolio selection algorithm, called BISONS, to solve the game of online quantum state tomography described in Section 3.1 By an maline-to-batte conversion, their algorithm yields a stochastic algorithm for ML QST. The resulting algorithm achieves a better iteration complexity than Stochastic Q-Soft-Bayes; nevertheless, each iteration of it requires solving a self-concordant convex program by, e.g. Newton's 's method, resulting in high time complexity incomparable to that of Stochastic Q-Soft- In the words of Zimmert et al. 667. both their and our algorithms are on the state-of-the-arr efficiency-regrel frontier.
114
116
118
119
1.2
Notations
120
We write R. for the set of non- non-negaaive real numbers and R++ the set of strictly positive real numbers. Let E N. We write [J] for the set (1....,J] J)
Let M be a matrix. We write M for its Hermitian (conjugate transpose) and tr(M) for its trace. Let H be a Hermitian matrx; we write its spectral decomposition as H = Ea >aPa, where Xa are the eigenvalues and Pa are projections onto the associated eigenspaces. Let f be real-valued function whose domain contains { (Aa }. Then, f() is defined as the matrix E. Pa. Let A and B be two matrices. We write A 2 B if and only A - B is positive semi-detinite. Let E be an event and ş be random variable following probability distribution P. We write P(E) for the probability of the event and Ep [g] for the expectation of Ç. We sometimes omit the subscript P and write E [[] when there is no ambiguity.
121
122
123
124
125
127
128
2
Preliminaries
130
2.1
Maximum-Liikelihod Quantum State Tomography
131
In the mathematical formulation of quantum mechanics, a quantum state corresponds to density matrix, Hermitian positive semi-definite complex matrix of unit trace. Let the dimension of the
132
133
density matrix be D E N. If there are qubits, then D = 29. We denote by DD the set of density matrices in C DxD i.e.,
134
D = f= DxD -= H 0. 1
"W note that the work of Zimmert et al. 667 appears much later than the arXiv version of our work. This footnote is simply to address potential confusions of reviewers and may be removed in the camera-read version. We do not encourage the reviewers to check the arXiv version that violates the double-blind policy.
3

---

135
A measurement setup corresponds to positive operator-valned measure (POVM), set of Hermitian positive semi-definite complex matrices summing the identity. Let p and { [M,,... M, } с CDDD be POVM. The measurement outcome is random variable taking values in [J] such that
136
P (1 = j) - tr(M))),
Vj E [J]
138
The MI. estimation approach seeks the quantum state that maximizes the probability of observing the measured data. Let p² 'D be the density matrix to be estimated. In standard QST experiment, we construct N independent copies of p² and measure the copies independently with possibly different
139
140
POVMs. It is easily checked that the ML estimator is of the form
E argmax II tr(Anp);
PED
142
where each A, is an element of the POVM for the n-th measurement. We call [A.....,Ap the data-set. We equivalently write the ML estimator as
143
i E argmin [()),
(1)
PED
f(D)
Σ (- log (A..)))
(2)
144
Obviously, TT
a convex optimization problem. the matrix Aw not full-rank for some n' E [N]
(as in the cases with the Pauli measurement [40] and Pauli basis measurement (6)), then tr (r())))) can be arbitrarily close to zero on D and hence the k-th-order derivative of the objective function is unbounded for all & E N.
146
Let A be random matrix following the empirical distribution PNv on the data-set { (A....., An }.
148
If the matrices An are all different, then PN is simply the uniform distribution on the data-set write the objective function in ( as expectation
149
AA AN }. Then,
f()) p [- log logtr(((p)))) (r())
(3)
This observation connects MI QST with the problem of computing the log-optimal portfolio.
2.2
Log-optimal Portfolio
153
Interestingly, the optimization problem (I) is exactly a quantum extension of the problem of com- puting the log-optimal portfolio (aka the Kelly criterion), asymptotically optimal strategy for long-term investment (5] 13 36). Consider multi-round investment a market. Suppose there are D investment alternatives. For the 1-th round, we list the return rates of the investment alternatives in that round as a random vector a E R.D. Before each round starts, an investor needs to determine the portfolio for the round given the past return rates. Denote by P++1 the probability distribution of
155
157
158
159
a++1 conditional on the history (a).... at). The log-optimal portfolio w for the (t + 1)-th round given by the stochastic optimization problem:
160
wi+1 argming((w),
(4)
WEA
( = Ep,., [- log (0r+1, w)],
(5)
where denotes the probability simplex in RP,, the set of ensr non-negatee non-negative vectors whose entries to one. Then, the investor distributes the wealth to the investment alternatives following the ratios specified by w
181
163
164
We now discuss the correspondence between ML QST and log- log-optimal portfolio. The set D is indeed quantum extension of the probability simplex A, in the sense that a Hertimian matrix is density matrix if and only if its vector of eigenvalues lies in the probability simplex. The objective functions linear functions. Indeed, it easily checked
185
186
167
and (4) are both expectations of the logarithm that if the matrices involved in (1) share the same eigenbasis, then the non-commutativity issue in the quantum setup vanishes and (T) coincides with 4 Though the correspondence is obvious given the two problem formulations, seems that this correspondence has not been discussed in the literature.
189

---

2.3
Online Portfolio Selection
172
Online portfolio selection may be viewed as probability-Ffe version of log- optimall portfolio [9] Online portfolio selection is multi-round game between two players, say INVESTOR and MARKET. Suppose the game consists of T rounds. In the t-th round of the game, first, INVESTOR announces portfolio Wy E A; then, MARKET announces the return rates of all investment alternatives for the I-th round in a vector a, E I finally, INVESTOR suffers a loss of value log (a,, wt). The goal of IN- VESTOR is to achieve a low regrel against all possible strategies of MARKET. The regret is defined as
173
174
176
177
T
RT = sup Σ (- log (ae, wa))
min WEA
(- log (ay, w)),
where the supremum is over all possible strategies of MARKET to determine (a)) We say an algorithm for INVESTOR to determine the portfolios is no-regret if it achieves Rī = o(T).
179
If can sample from the conditional probability distribution Pr+1 specified in the previous sub- section, then we can transform a no-regret online portfolio selection algorithm to an algorithm that approximately computes the log-optimal portfolio. The following is immediate consequence of the online-to-batee botchh conversion [ 50).
181
183
Proposition 2.1. Suppose in the online portfolio selection game, the vectors at all independent and identically distributed (i..d.) random vectors sollowing the probability distribution P.+1 in the previoius sub-section. Let (We)EN be the sequence iterates generated by an algorithm for INVESTOR of regret Rr. Then, for any T N,
185
187
E
min <((WT)
p(()))
RT
WT
WT
WEA
T
Recall that up is the conditional expectation of the log-linear loss (
188
189
If INVESTOR adopts a no-regret algorithm, then the expected optimization error vanishes as T + co.
190
2.4
Soft-Bayes
There various existing algorithms for online portfolio selection. Among these algorithms, particularly interested in Soft-Bayes [51] The per-iteration time complexity of Soft- soft-Baees is linear in D, arguably the lowest one can expect. This desirable feature for ML QST, as the dimension of the density matrix grows exponentially with the number of qubits.
192
193
194
The iteration rule of Soft-Bayes is follows.
196
Initialize w1 (1/D. ./DD.....//))). E A (the uniform distribution).
For each E N, compute
Wr+1 = (1 n) + Oe We (az, we)
E N,
(6)
for some properly chosen learning rute 1 E [0, 1]. where denotes the entry-wise product.
199
Soft-Bayed has the following regret guarantee.
Theorem 2.2 (51). After T rounds in online portfolio selection, the regret of Soft-Bayer with
DT
1
v DT Vlog D
is at most 2/TD log D + log D.
3 Online Maximum-Likelihon Quantum State Tomography by Q-Soft-Bayes
Following the discussion Section I we first propose game of online quartum state tomogruphy as quantum extension of online portfolio selection. Then, we "quantumize" Soft-Bayes to derive 205 a no-regret algorithm for the game and analyse its regret. Finally, we adopt the online-to-bates
203
conversion and bound the expected optimization error of the resulting algorithm.
5

---

207
3.1
Game of Online Quantum State Tomography
208
We propose the following game of online quantum state tomography as a quantum extension of online portfolio selection. Online quantum state tomography is multi-round game between two players, say PHYSICIST and ENVIRONMENT. Suppose there are in total T rounds. In the t-th round, first, PHYSICIST announces a density matrix Pr D; then, ENVIRONMENT announces a Hermitian positive semi-definite matrix A, 2 0; finally, PHYSICIST suffers for loss of value log tr (Atpe).
209
210
212
The regret in this game is given by
T
Ry = sup Σ
log tr(Asp:)
min TED
(- log tr((A
where the supremum is over all possible strategies of PHYSICIST to generate the sequence (At)
The connection with online portfolio selection is obvious and similar that between MI. QST and the log-optimal portfolio: The vector of cigenvalues of density matrix lies in the probability simplex A: the Hermitian matrices A, and the positive semi-definiteness condition correspond the vectors
218
217
aj in online portfolio selection and their non-negativity condition, respectively; the losses in the two 218
219
games are both logarithms of linear functions; the regrets in the two games are defined exactly in the same manner. When all the matrices involved in the game of online quantum state tomography share
220
221
the same eigenbasis, we recover the game of online portfolio selection.
222
3.2
Q-Soft-Bayes and Stochastic Q-Soft-Bayes
223
We propose the following Q-Soft-Bayes algorithm as a quantum extension of Soft-Bayes.
224
Initialize P1 W1 D/D.
For each E N, compute
A
G, = [1- (r( (r(())))'
W411 exp (log (We) + log (Gr)),
(8)
W411
Pt+1
tr(W.+1)
226
for some properly chosen learning rate E [0,
227
Remark 3.1. Recently, we learned that Q-Soft-Bayes may be interpreted using the commutative matrix product by Warmuth and Kuzmin (61]. It is currently unclear to whether this interpretation provides any insight.
229
230
If we were able to cancel the exponential and logarithms SSoft-Bayes, then we recover Soft-Bayes; however, due to the non-commutativity issue, such cancellation is illegal in general. In comparison to Soft-Bayes, Q-Soft-Baye has an additional normalization step to ensure its outputs are of unit trace.
232
We prove the following in Section B.
Proposition 3.2. It holds that tr(W,) < for all t.
235
Numerical experiments show that the equality does not always hold, so the normalization step is necessary, Recall that Soft-Bayes does not need the normalization step (see Section 2.4).
237
In Appendix C, we prove the following regret bound for Q-Soft-Bayee showing that it inherits the regret bound of Soft- Boft-Bayes.
238
239
Theorem 3.3. The regret of D-Soof-Bayes with the learning rate 1) given in is at most
2 DD log D + log D.
Remark 3.4. One might wonder why D is not replaced by D2 in the quantum case. This is because our extension, the analogue of a D-dimensional vector in the quantum case is the D-dimensional vector of eigenvalues of a D-by-D Hermitian matrix, instead of the D-dimensional vector obtained by vectorizing vD-by-vD matrix. Similar coincidence of regret bounds can be observed in, for example, the matrix version of exponentiated gradient update [58] and the quantum individual sequence prediction algorithms of Koolen et al. (37]
242
243
245

---

247
The standard online-to-batee conversion argument can also be applied to solving ML QST by
248
Q- Q-Soft Soft-Bayes. Recall for ML QST. our aim solve the stochastic optimization problem
أ E argmin P [- log tr(A,
PED
where A is a random matrix following the empirical probability distribution PN on the data-set [A, ,...... AN } (see Section 2.1). We propose the following stochastic optimization algorithm, which we call Stochastic Q-Soft- Bayes, to solve ML QST.
249
250
251
252
Initialize D-Soft-Bayes with f1 I/D.
253
In the t-th iteration of Stochastic Q-Soft-Bayes, do the following.
254
1. Output the t-th output P: of Q-Soft-Bayes.
255
2. Sample a random matrix B, E {A....., AN } following the empirical probability distribution PN on the data-set, independent of the past.
256
3. Let ENVIRONMENT in the online QST game announce the matrix B
258
Similarly as for Proposition 2.1 the standard online-to-batch conversion argument provides the following convergence guarantee of Stochastic-Q-Soft Saaiii----Sof--Byeeee
280
Proposition 3.5. Let (Pt) be the sequence of iterates generated by Stochastic Soft-Bayes. Then, for any T E N, holds that
261
E f(PT) - min f(p) f()) PED S 2
D log T
log D T
+
282
where Pr (p. PTT and the expectation is with respect to the randomness in B, of Stochastic Soft-Bayes Recall f is the objective function in ML QST as defined in or (3) (the two
263
264
definitions are equivalent).
265
Therefore, Stochastic- Castastti---oft---e Q-Soft-Bayer outputs an approximate ML estimator of expected optimization
error smaller than in O((Dlgg )) iterations. Each iteration of Stochastic- Q-Soft-Baye
266
267
requires computing a matrix exponential and two matrix logarithms. The overall time complexity is
hence O(D log = One may adopt anytime online-to-batch [22], which seems to empirically
268
yield faster convergence. According to (22), the optimization error guarantee remains the same; the only difference is that V are evaluated at P, instead of pr when implementing Soft-Bayes, so the overall time complexity also remains the same.
270
272
One may be interested in the distance to the minimizer. It is easily checked that the function f is self-concordant. If V2 f is positive definite at the minimizer, a standard condition for well-posed estimators, then the function f locally strongly convex around the minimizer 45 Theorem 4. 1.6). Therefore, the distance to the minimizer, measured in terms of the Frobenius norm, is asymptotically of the order of the square root of the optimization error.
273
274
275
276
277
3.3
Theoretical Comparison with Existing Batch Algorithms
278
Let us compare the time complexities of Stochastic Q-Soft-Bayes and existing algorithms discussed in Section [ The iteration complexities of existing algorithms are mostly unknown vague in their dependence on the problem parameters. Diluted RpR and entropic mirror descent with line search do not have non-asymptotic analysis results (60] 27 39] SCOPT only has local linear rate guarantee (57): Adaptive Frank- Wolfe and Monotonous Frank-Wolfe have O iteration complexities with unclear dependence on the dimension and sample size, as their error bounds involve local smoothness parameters that are hard to evaluate [1, (4). A finer analysis of Adaptive Frank- Wolfe by Zhao and Freund [65] shows that its iteration complexity is O(E NN) and hence its time complexity is O (N2 D2 + Nr)), where the symbol denotes the time of computing the local norm defined by the Hessian, for which we do not know an efficient implementation. In comparison, the complexities of Stochastic Q-Soft-Bayes is very clear: O(E 2 D log D) iteration complexity and hence O( 2 log D) time complexity. The time complexity of Stochastic Q-Soft-Bayes becomes
279
280
281
282
283
284
285
287
288
289
competitive with Adaptive Frank if N > (1/1)))loo D, ignoring the time of computing the local norms. Recently, is proved that any QST scheme with non-coherent measurement, e.g., MI.
291
QST we consider in this paper, requires N = Q(D3 /82) to achieve estimation error smaller than d
7

---

5055
Sph
0014
0.
2053
75
300
125
150
375
200
23
90
15.0
1.25
1540
325
200
Numbbr Eprsthc
Nurbbbr of Spocths
Figure 1: in function value of Stochastic Q-Soft-Bayes (SQSB), RpR (RthoR), and Monotonous Frank- Wolfe (FW).
Approximate optimization errors
Figure 2: Fidelity values of the iterates and the W state achieved by Stochastic Q-Soft-Bayee (SQSB), RpR (RrhoR), and Monotonous Frank- Wolfe (FW).
in the trace distance [7 The algorithm by Zimmert et al. 67 has Õ(D*/E) iteration complexity and O(D5) per-iteration time complexity ignoring the dependence on other parameters, due to the 295 use of Newton's 's method to compute the iterates; the overall time complexity has a much higher
293
294
298
dependence on the dimension than Adaptive Frank-Wolfe and Stochastic Q-Soft-Bayes. We conclude that the time complexity of Stochastic Q-Soft-Baye Bayes is competitive compared to existing algorithms.
297
4 Numerical Results
As discussed above, Stochastic Soft-Bayes is competitive in theory. We now examine its empirical performance with anytime online-to-bated We compare its empirical speed with two batch methods, the RpR method 443 44 and Monotonous Frank-Wolfe [44, a synthetic data-set in Figure D and Figure 2 We have mentioned several batch methods applicable for ML QST in Section T. Among them, choose RpR for comparison it is representative in physics literature and empirically fast, though does nol always converge. We choose monotonous Frank- for comparison as it avoids computationally expensive Hessian computations in step size selection. Recall that Monotonous Frank-Wolfe converges at (11/t) rate as other Frank Wolfe methods for self- concordant minimization do 665 24 48
300
302
304
305
306
307
but its complexity guarantee lacks clear characterization of the dependence on the dimension and sample size.
308
The synthetic data-set is generated basically following the set-up in [3I. The number of qubits equals 6. The dimension D then equals 2 = 64. The unknown quantum state to be measured is the W state. We randomly generate N = 4" x 100 -49600 Pauli observables in, e.g., [25] 28 40), each of which corresponds to a POVM two rank-(D/2) elements. As there are in total 49 different Pauli observables (and hence POVMs), each observable is used about 100 times. Then, sample
310
312
313
314 the N measurement outcomes and formulate the MI. estimator following Section 2.1.
The performance measures consider are optimization errors (in objective function) and fidelity values. To estimate the optimization error, we run each algorithm for 200 epochs and use the smallest function value found by the algorithms
316
approximate optimal value. The approximate optimization error of an iterate defined as the difference between the objective function value at the iterate and the approximate optimal value. Fidelity is a notion commonly used by physicists to measure how close two quantum states are to each other. For any two density matrices p and
318
320
the fidelity is given by F(p, o) = (tr / /P) 2, which takes values in [0, 1]. The fidelity of two quantum states equals 1, if the two states are exactly the same. We plot the optimization errors and fidelity values versus the number of epochs. An epoch corresponds to one pass of the whole deta-set. One iteration of Stochastic Q-Soft-Baye corresponds to 1/N epoch. One iteration of RpR
322
324
325
and Monotonous Frank-Wolfe corresponds to epoch as both algorithms are batch.
326
Obviously, Stochastic Q-Soft-Bayes converges faster than RpR in both optimization error and fidelity.
Where as Monotonous Frank- Wolfe is the fastest in both figures, this can be explained by the fact that
8

---

328
Frank- Wolfe tends to generate upproximately low-rank iterates. The W state corresponds to rank- I density matrix, so the ML estimate should be approximately low-rank, matching the structure favoured by Trank-Wofft We conclude that the convergence speed of Stochastic Q- D-Soft-Bayer is competitive in theory (Section 3.3) and comparable to fast yet theoretically non-rigorous algorithms in practice.
329
331
332
A comparison in terms of the elapsed time is provided in Appendix A. The results show there is large room for improvement to compete with Rpl and Monotonous Frank- Wolfe in the elapsed time. The source codes are provided in the supplementary material.
333
334
5
Discussions
335
336
5.1
Can We Find Faster Stochastic First-Order Algorithms for ML QST?
337
Our approach to constructing a stochastic first-order algorithm for ML QST conceptually applies to any no-regret online portfolio selection algorithm. In this paper, we focus on
338
Other existing online portfolio selection algorithms have much higher per-iteration time complexities, in terms of the dependence on the ambient dimension and sample size. If we adopt any other existing online portfolio selection algorithm and "quantumize" it to obtain stochastic algorithm for MI. QST, then the resulting algorithm will scale poorly with the number of qubits. Developing an online portfolio selection algorithm that enjoys both low regret and low time complexity is still open
339
341
342
343
59
67
345
is still possible to develop another quantum extension of Soft-Bayes that enjoys lower per- iteration time complexity. The per-iteration time complexity issue may be mitigated if we consider other quantum extensions of Soft-Bayes. For example, if we naively replace (8) by We+1 W, + W,G.) /2, the resulting algorithm still coincides with Boft-Bayes when all matrices share
348
347
348
the same eigenbasis, whereas the per-iteration time complexity is reduced to O(D") for some < 2.373 @ Unfortunately, we cannot work out a non-asymptotic analysis for any other possible quantum extension of Soft- Baft-Baye we can think of.
349
350
351
352
The discussion above assumes that we adopt the online-to-batch argument as in this paper. Another way, which we think perhaps more plausible, to directly consider the stochastic optimization formulation and develop stochastic optimization algorithm for ML QST.
353
354
355
5.2
Connection with Expectation Maximization
356
Finally, let us discuss an interesting connection between D-Soft-Bayes and expectation maximization
357
(EM). The RpR algorithm, according to 43 was inspired by the expectation maximization (EM)
358
method for solving optimization problems of the form (4) Given a full-rank initial iterate P1 E D,
359
RpR iterates as
ReprRe tr(ReptRt)
PL+1
R₂ == -f(p), e N,
380 where f is defined in 2). In comparison, given an entry-wise positive vector wi E A, EM for iterates as
361
Wt+1 = w. (-V)(w))), N.
It is interesting to notice that even when all matrices involved share the same eigenbasis, RoR is
363
not equivalent to EM. Indeed, EM is proved to asymptotically converge to the optimum [18, 21). whereas RpR oscillates
carefully designed data-set (60). This suggests that RpR is perhaps not 365 a "natural"' quantum extension of EM. Later, there were variations of RpR that solve the convergence issue by line search [60 27 but these variations still do not recover EM.
367
Notice that the formulation of Soft- Soft-Bayes (6) is the convex combination of the previous iterate and the output of EM. Therefore, Soft-Bayes, after the thline-to-bathh conversion, can be interpreted as a relaxed stochastic EM method for computing the log-optimal portfolio. As Q-Soft-Bayee becomes
368
369
Soft-Bayes when all matrices involved share the same eigenbasis, we may claim that Stochastic Q-Soft-Bayes also a relaxed stochastic EM method, though its derivation does not have any obvious
371
relation with the standard derivation of EM 23

---

References
373
374
[1] Aaronson. Shadow tomography of quantum states, SIAM J. Comput., 49(5):STOC18-36- STOCI8-394 2020.
[2] S. Aaronson, X. Chen, E. Hazan, S. Kale, and A. Nayak. Online learning of quantum states, In Adv. Neural Information Processing Systems 31, 2018.
377
378
[3] Ahmed, C. S. Muñoz, F. Nori, and A. F. Kockum. Quantum state tomography with conditional generative adversarial networks, 2020. arXiv:2008.0333 0022400
[4] A. Alacaoglu. Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond. PhD thesis, École polytechnique fédérale de Lausanne, 2021.
382
[5] P. H. Algoet and T. M. Cover. Asymptotic optimality and asymptotic equipartition properties of log-optimum investment. Ann. Probab., 16(2):876-898, 1988.
383
[6] Alman and V. V. Williams. A refined laser method and faster matrix multiplication. In Proc.
385
2021 ACM-SIAM Symp. Discrete Algorithms (SODA), 2021.
386
[7] J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O'Brien, M. A. Nielsen, and A. G. White, Ancilla-assisted quantum process tomography. Phys. Rev. Lett., 90 (19), 2003,
387
388
389
[8] S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: A meta-algorithm and applications. Theory Comput., 8: 8:121-164, 2012.
390
99 H. H. Bauschke, J. Bolte, and M. Teboulle. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res., 42(2):330-348, 2017.
392
393
394
[10] R. Blume-Kohout. Hedged maximum likelihood quantum state estimation. Phys. Rev. Lett., 105, 2010.
385
396
[1]] R. Blume-Kohout. Optimal, reliable estimation of quantum states. New J. Phys., 12, 2010.
387
[12] E. Bolduc, G. C. Knee, E. M. Gauger, and Leach. Projected gradient descent algorithms for quantum state tomography. npj Quantum Inf., 3, 2017.
[13] L. Breiman. Investment policies for expanding business optimal in long-run sense. In W. T. Ziemba and R. G. Vickson, editors, Stochastic Optimization Models in Finance, pages 593-598. Academic Press, New York, NY, 1975.
400
[14] A. Carderera, M. Besançon, and S. Pokutta. Simple steps are all you need: Frank- and generalized eelf-concordant functions, 2021.
403
404 [15] N. Cesa- BesaccBianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learning algorithms. IEEE Trans. Inf. 5009):0500
2004.
[16] A. Chambolle, M. J. Ehrhardt, P. Richtárik, and C.-B. Schönlieb. Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications. SIAM J. Optim., 28(4): 2018.
407
[17] S. Chen, B. Huang, J. Li, A. Liu, and M. Selke. Tight bounds for state tomography with incoherent measurements. 2022. arXiv:2206.05265V..
410
411
[18] T. M. Cover. An algorithm for maximizing expected log investment return. IEEE Trans. Inf. Theory, (7:3002):3993733 1984.
[19] T. M. Cover. Universal portfolios. Math. Financ., 1(1):1-29) 1991.
[20] T. M. Cover and E. Ordentlich. Universal portfolios with side information. IEEE Trans. Inf. Theory, 42(2):348-363 1996.
415
416 [21] Csiszár and G. Tusnády. Information geometry and alternating minimization procedures. Stat. Decis., (Supplement 1):205-237, 1984.
10

---

418
[22] A. Cutkosky. Anytime coline-to-batche optimism and acceleration. In Proc. 36th Int. Conf. Machine Learning. 2019.
419
420
[23] A. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc., Ser. B, 39(1):1-38, 1977.
422
[24] P. Dvurechensky, P. Ostroukhov, K. Safin, S. Shtern, and M. Staudigl. Self-concordant analysis of Frank-Waa Wolfe algorithms. In Proc. 37th Int. Conf. Machine Learning, 2020.
423
[55] S. T. Flammia, D. Gross, Y.-K. Liu, and J. Eisert. Quantum tomography via compressed sensing: Error bounds, sample complexity and efficient estimators. New J. Phys., 14, 2012.
425
426
[26] W. Gao and D. Goldfarb. Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions. Optim. Methods Softw., 34(1):194-217, 2019.
427
[77]
D. S. Gonçalves, M. A. Gomes- RoggeeRu and C. Lavor. Global convergence of diluted iterations in maximum-likelihon quantum tomography. Quantum Inf. Comput., 14(1 1& 2):9666888, 2014.
429
430
[28] D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert. Quantum state tomography via compressed sensing. Phys. Rev. Lett., 105, 2010.
432
433
[29] M. Gujä, J. Kahn, R. Kueng, and J. A. Tropp. Fast state tomography with optimal error bounds. J. Phys. A: Math. Theor. 53, 2020.
[30] J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu. Samplc-optimal tomography of quantum states. IEEE Trans. Inf. Theory, (3(9))562855644
436
2017.
437
[31] H. Häffner, W. Hänsel, C. F. Roos, J. Benhelm, D. al-ckr M. Chwalla, T. Körber, U. D. Rapol, M. Riebe, P. O. Schmidt, C. Becher, O. Gühne, W. Dür, and R. Blatt. Scalable multiparticle entanglement of trapped ions. Nature, 438:643-646, 2005.
439
440
[32] N. He, Z. Harchaoui, Y. Wang, and L. Song. Point process estimation with mirror prox algorithms. Appl. Math. Optim., 2019.
[33] Z. Hradil. Quantum-state estimation. Phys. Rev. A, 55(3), 1997.
443
[34] Z. Hradil, J. Reháček, J. Fiurášck, and M. Ježck. Maximum-likelihodd methods in quantum
444
mechanics. In Quantum State Estimation, chapter 3, pages 59-112. Springer, Berlin, 2004.
445
[35] A. Kalai and S. Vempala. Efficient algorithms for universal portfolios. J. Mach. Learn. Res., 3: 423 333-440,220 2002.
448
447
[36]
Kelly, Jr. new interpretation of information rate. IRE Trans. Inf. Theory, 2(3):185-189, 1956.
448
449
[37] W. M. Koolen, W. Kotlowski, and M. K. Warmuth. Learning eigenvectors for free. In Adv.
450
Neural Information Processing Systems 24, 2011.
[38] R. Kueng, H. Rauhut, and U. Terstiege. Low rank matrix recovery from rank one measurements. Appl. Comput. Harmon. Anal., 42:88-116, 2017.
452
453
[39] Y.H.. Li and V. Cevher. Convergence of the exponentiated gradient method with Armijo line search. J. Optim. Theory Appl., (81(2):588 607, 2019.
[40] Y.-K. Liu. Universal low-rank matrix recovery from Pauli measurements. In Adv. Neural Information Processing Systems 24, 2011.
456
457
[41] Y.-K. Liu. Universal low-rank matrix recovery from Pauli measurements. 2011. 1tf.::113.2266111 [quant-ph].
[42] H. Luo, C.-Y. Wei, and K. Zheng. Efficient online portfolio with logarithmic regret. In Adv. Neural Information Processing Systems 31, 2018
460
461
[43] A. I. Lvovsky. Iterative maximun-likelihood reconstruction in quantum homodyne tomography.
J. Opt. B: Quantum Semiclass. Opt., 6, 2004.

---

463
[44] G. Molina-Terriza, A. Vaziri, J. Reháček, Z. Hradil, and A. Zeilinger. Triggered qutrits for quantum communication protocols. Phys. Rev. Lett., 92(16), 2004.
484
465
[45] Y. Nesterov. Introductory Lectures on Convex Optimization. Kluwer, Boston, 2004.
466
[46] M. A. Nielsen and Chuang. Quantum Computation and Quantum Information. Cambridge
Univ. Press, Cambridge, UK, 2010.
468
[47] R. O'Donnell and Wright. Efficient quantum tomography. Proc. 48th Annu. ACM Symp. Theory of Computing, pages 899-912, 2016.
470
[48] G. Odor, Y.-H. Li, A. Yurtsever, Y.-P. Hsich, M. El Halabi, Q. Tran-Dinh, and V. Cevher. Frank-Wolfe works for non-Lipschitz continuous gradient objectives: Scalable Poisson phase retrieval. In IEEE Int. Conf. Acoustics, Speech and Signal Processing, pages 6230-6234, 2016.
472
[49] T. Opatmý, D.-G. Welsch, and W. Vogel. Least-squares inversion for density- matriix reconstruc- tion. Phys. Rev. A, 56(3), 1997.
474
[50] F. Orabona. A modern introduction to online learning. 2019. arXiv:1912.1321344
476
[51] L. Orseau, T. Lattimore, and S. Legg. Soft-Bayes: Prod for mixtures of experts with log-loss.
In Proc. 28th Int. Conf. Algorithmic Learning Theory, pages 372 2017.
[52] M. Paris and J. Reháčck, editors. Quantum State Estimation. Springer, Berlin, 2004.
479
[53] Y. Quek, S. Fort, and H. K. Ng. Adaptive quantum state tomography with neural networks. npj Quantum Inf., 7, 2021.
481
[54] C. A. Riofrío, D. Gross, S. T. Flammia, T. Monz, D. Nigg, R. Blatt, and J. Eisert. Experimental quantum compressed sensing for seven-qubit system. Nature Commun., 2017.
482
489
[55] T. L. Scholten and R. Blume-Kohout. Behavior of maximum likelihood in quantum state tomography. New J. Phys., 20, 2018.
484
485
[56] A. Steffens, C. A. Riofrío, W. McCutcheon, I. Roth, B. A. Bell, A. McMillan, M. S. Tame,
486
J. G. Rarity, and J. Eisert. Experimentally exploring compressed sensing quantum tomography.
487
Quantum Sci. Tech., 2, 2017.
488
[57] Q. Tran-Dinh, A. Kyrillidis, and V. Cevher. Composite self-concordant minimization. J. Mach. Learn. Res., 16:371-416, 2015.
489
490
[58] K. Tsuda, G. Rätsch, and M. K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. J. Mach. Learn. Res., 1:995-1016 2005.
492
[59] van Erven, D. van der Hoeven, W. Kotlowski, and W. M. Koolen. Open problem: Fast and optimal online portfolio selection. In Proc. 33rd Conf. Learning Theory, 2020.
493
494
[60] J. Reháček, Z. Hradil, E. Knill, and A. I. Lvovsky. Diluted maximum-like likelihood algorithm for quantum tomography. Phys. Rev. A, 75, 2007.
495
496
[61] M. K. Warmuth and D. Kuzmin. Bayesian generalized probability calculus for density matrices. Mach. Learn., 78:63-101, 2010.
497
498
[62] M. Wilde. From classical to quantum Shannon theory. 2019. arXiv: 111.111...44. 1445v8.
499
[63] Yang, J. Jiang, J. Zhang, and X. Sun. Revisiting online quantum state learning. In Proc. AAAI Conf. Artificial Intelligence, 2020.
501
[64] A. Youssry, C. Ferrie, and M. Tomamichel. Efficient online quantum state estimation using a matrix-exponentiane gradient method. New J. Phys., 21(033006), 2019.
503
[65] R. Zhao and R. M. Freund. Analysis of the Frank-Wolfe method for logarithmically-
homogeneous barriers, with extension, 2020.
505
[66] C. Zhou, W. Gao, and D. Goldfarb. Stocahstic adaptive quasi-Newton methods for minimizing expected values. In Proc. 34th Int. Conf. Machine Learning, 2017.
507
[67] J. Zimmert, N. Agarwal, and S. Kale. Pushing the efficiency- Pareto frontier for online learning of portfolios and quantum states, 2022. 1rX1w:2202.02765v1
12

---

Checklist
509
510
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
512
513
(b) Did you describe the limitations of your work? [Yes] See Section 4
Whereas the proposed algorithm is fast in theory, its speed is unfortunately not satisfactory to
514
515
practitioners.
(c) Did you discuss any potential negative societal impacts of your work? [No] This is theory work.
517
518
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
520
2. If you are including theoretical results...
521
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Indeed, our algorithm applies to every data-set generated following Section 2.1
522
523
(b) Did you include complete proofs of all theoretical results? [Yes) See the appendix.
524
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The codes are attached.
626
528
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 4
529
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No] The comparison is obvious, so we do not feel necessary
531
to report error bars.
533
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section A. This information is not necessary for Section
534
535
4. If you using existing assets (e.g., code, data, models) or curating/releusing new assets...
537
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
539
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
540
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
542
543
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
546
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
547
548
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
551
13


Reviews:
[{"review_id": "fvwKH99hDE", "reviewer": "Reviewer_m4jW", "summary": "The paper proposes a quantum version of Soft-Bayes for the maximum likelihood QST task, since Soft-Bayes enjoys fast per-iteration time complexity. The proposed algorithm is a stochastic first order algorithm, and compared to [64], it has better per-iteration complexity on the order of O(D^3), but worse iteration complexity. The paper provides numerical results comparing the proposed algorithm, RrhoR, and Monotonous FW. ", "questions": "Is it possible to do ML QST when the number of q-bits is large? Why does this problem formulation make sense with exponential dependence on the number of q-bits?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper is clearly written, and the theoretical results are well-supported. The numerical results, though not ideal for the proposed algorithm, are interesting and appreciated. \n\nWeaknesses\n- The iteration complexity and per-iteration complexity both involve D, which is exponential in the number of q-bits. Though for the ML QST task this dependence may be inevitable, it would be helpful for the authors to explain why this problem formulation makes sense when the number of q-bits is large.\n- The idea of using an online portfolio selection algorithm for a QST task is also explored in [64], and the extension of Soft-Bayes to the quantum setting doesn’t seem to involve new techniques. \n- The numerical results are unfortunately not very convincing, as the method obtains higher error than some of the baseline algorithms.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JQd9sEk7pX", "reviewer": "Reviewer_oBoV", "summary": "In this paper the authors consider the problem of quantum state tomography (QST). Here there is an unknown n qubit quantum state rho (i.e., its a complex matrix of size 2^n x 2^n) and the goal is to learn rho given copies to the state. The sample complexity of QST has completely been pinned down to Theta(d^2) where d=2^n. Apart from the theoretical guarantees there are also some heuristic works that have looked at QST and one such method which is relevant to this work is that of maximum-likelyhood estimation. So computing the ML estimator  amounts to solving a convex optimization problem, however the main issue for using maximum likelehood estimator for QST is  negative log-likelihood function in ML QST is not Lipschitz and not smooth as well.  In contrast in this paper, the authors develop a stochastic first-order optimization technique for ML QST inspired by techniques from online learning. They moreover choose to quantumize  the soft-Bayes algorithm which is an iterative algorithm  whose round by round complexity is linear in the dimension of the state, i.e., d  and the rate of convergence of the procedures presented in this paper are similar to ones known from literature. Finally the authors provide some empirical plots implementing their learning procedures.\n\nI think the study of QST using MLE is nice, but i dont think this paper is fit for NeurIPS for a few reasons\na) The main contributions of this paper are in a very narrow subject and i dont think this narrow subject  might be of interest to classical ML (which is the primary audience of NeurIPS) and quantum computing (since the novelty of this paper is limited to improving certain heuristic-based approach for QST).\nb) In my opinion, the main contributions of this paper needs more motivation. For example, QST is a completely solved subject, in the sense the sample complexity has been pinned down. Then why should one look at solving QST using regression, MLE etc? Is there any solid motivation for considering these approaches? \n\nGiven the niche contributions which are limited in applicability, i think this paper isnt strong enough to be accepted for NeurIPS.", "questions": "Mentioned earlier.", "limitations": "Mentioned earlier.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Mentioned earlier.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Responsible Research Practice (e.g., IRB, documentation, research ethics)"]}, "extra_text": {}}, {"review_id": "1EITIT9HJLA", "reviewer": "Reviewer_o5XD", "summary": "The submission proposes Stochastic-Q-Soft-Bayes to accomplish the quantum state tomography task. To achieve an $\\epsilon$-regret, the required runtime complexity scales with $O(D^4logD/\\epsilon^2)$. Numerical simulations on a 4-qubit state demonstrate the effectiveness of the proposed method. ", "questions": "See the comments above. ", "limitations": "See the comments above. ", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe submission addresses an important topic in quantum computing, i.e., devising efficient algorithms to complete quantum state tomography. The paper is well organized and the central idea is well presented.\n\nWeaknesses:\n1. It has been proved that $n = \\Omega(d^2/\\epsilon^2)$ copies are necessary to achieve the estimation error $\\epsilon$ [IEEE Trans. Inf. Theory, 63(9):5628–5641, 2017.]. Nevertheless, the submission shows that the proposed algorithm can achieve an $\\epsilon$-error using $O(D^4logD/\\epsilon^2)$ copies. This contradiction originates from the definition of the `error'. Conventionally, the estimation error between the estimated state $\\hat{\\rho}$ and the target $\\rho$ is defined as $\\|\\rho-\\hat{\\rho}\\|_{tr}$, whereas the submission adopts the regret to describe the `error'. Consequently, the achieved results are incomparable with prior literature. The authors should clarify this issue. \n\n2. To address the applicability of Stochastic-Q-Soft-Bayes. Simulation results on large-qubit states are desirable. Current results fail to demonstrate the potential advantages of Stochastic-Q-Soft-Bayes.\n\n \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0C7gNxYZ0Q5", "reviewer": "Reviewer_3n1B", "summary": "This paper studies state tomography from the perspective of online learning. State tomography is an important problem in quantum computing. Its main objective is to arrive at an approximated description of an unknown quantum state by measuring several copies of that state. The main approach of this paper is based on soft Bayes ML estimation in which the objective is to minimize a log-loss defined between the true density operator and the estimated one. The paper then relates this problem to minimizing regret in online learning (portfolio selection) where soft Bayes is a promising approach. Then, the paper proposes a quantum analogous to soft Bayes. Using classically developed tools, the authors provide guaranteed results for their algorithms. Lastly, they provide numerical demonstrations.  ", "questions": "Why do we need to use online learning for state tomography?", "limitations": "The main limitations of the proposed approach are (a) scalability as the number of the iterations grows exponentially with the number of qubits, and (b) numerical experiments do not seem to show the advantage of the proposed algorithm. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper in my opinion is the quantum soft Bayes which leads to a quantum learning algorithm with provable guarantees. This is a nice idea with possible future applications. The analysis (especially Theorem 3.3) is interesting.\n\nThere are two major weaknesses of the paper:\n\n1)  The paper is not clear in the problem formulation.  It is unclear to some extent as to why we need to use the online approach for state tomography where we can have all the samples at once. \n\n2)  The proposed approach does not seem to be scalable as the number of iterations grows exponentially with the number of qubits. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject