REVIEW 2 major objections 5 minor 27 references
Certified answers for ordered quantum discrimination problems
T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Ordered chains of linearly independent pure quantum states admit certified-answer discrimination as a compact semidefinite program, and a lower bound on success probability follows from the minimum-error solution alone.
desk verdict The SDP formulation for certified-answer discrimination is a genuine contribution, but the advertised general lower bound does not survive contact with the positivity constraints it is derived from. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument rests on three pieces. First, the Gram-matrix transformation: with $R=\sum_i|\Psi_i\rangle\langle i|$, the POVM constraints become $\Phi_\Delta[Z]\le G$, so all physics of the ordered hypotheses is encoded in the Gram matrix $G$ and in the linear map $\Phi_\Delta=\Phi_2\circ\Phi_{1,\Delta}$, which embeds the block-diagonal variable $Z$ into an $n\times n$ matrix; this shrinks the SDP from $n^2$ variables to $[n(2\Delta+1)-\Delta(\Delta+3)]$. Second, the lower-bound construction: starting from the minimum-error solution $Z^{\mathrm{ME}}$, the paper chooses the diagonal entries of a feasible ansatz by saturating the $2\times 2$ principal-minor inequality between a diagonal entry and the entry $\Delta+1$ steps away, which yields the formula (11). Third, for the quantum change point, the quantitative bound (21) follows from an exponential-decay estimate for the elements of $S=\sqrt{G}$, obtained by bounding the Fourier coefficients of $(1-2c\cos\theta+c^2)^{-1/2}$ through a contour-integral argument; this decay is what converts the abstract bound (11) into the explicit exponential approach to the minimum-error value.
What would settle it
Take the quantum change point with $n=4$ and overlap $c=0.9$, compute $Z^{\mathrm{ME}}$ from the square-root measurement, set $\Delta=1$, and test whether the diagonal entries from Eq. (9) admit any positive-semidefinite completion satisfying $\Phi_{1,\Delta}[Z]\le Z^{\mathrm{ME}}$; if no completion exists, or if the value $\tilde{P}_s$ from (11) exceeds the optimum of the SDP (5), the bound is refuted.
Extended reading notes
Core claim
In the paper's own terms, the central discovery is that the optimal $\Delta$-scheme for $n$ linearly independent ordered pure states is given by the semidefinite program (5): maximize $\frac{1}{n}\mathrm{Tr}[ZA]$ subject to $\Phi_\Delta[Z]\le G$, $Z\ge 0$, where $G=R^\dagger R$ is the Gram matrix built from $R=\sum_i |\Psi_i\rangle\langle i|$, and $\Phi_\Delta$ is a linear map that encodes which answers at distance greater than $\Delta$ are forbidden. The Gram matrix carries all discrimination properties of the hypotheses, and the SDP variable has only $O(n\Delta)$ free entries instead of $n^2$. The second claim is the lower bound (11), which expresses the certified success probability as the minimum-error value $P_s^{\mathrm{ME}}$ minus a sum of correction terms $H_i(\Delta)$ that depend only on the minimum-error solution $Z^{\mathrm{ME}}$; the corrections are obtained by saturating $2\times 2$ principal-minor inequalities in the relaxed constraint $\Phi_{1,\Delta}[Z]\le Z^{\mathrm{ME}}$. For the quantum change point with overlap $c$, exponential decay of the square-root matrix $S=\sqrt{G}$ turns this into $\tilde{P}_s\ge (1-2c\,e^{\Delta\log c}+c^2e^{2\Delta\log c})\,P_s^{\mathrm{ME}}$, and for quantum state anomaly detection it gives a linear interpolation between the unambiguous and minimum-error success probabilities once $\Delta\ge\lfloor n/2\rfloor$.
Load-bearing premise
The lower-bound proof assumes that a matrix whose diagonal entries are chosen to saturate the relaxed $2\times 2$ positivity inequalities can always be completed into a positive-semidefinite block matrix that still satisfies the measurement constraint, but the paper gives no such completion and the $2\times 2$ condition is only necessary, not sufficient.
Editorial extensions
If this is right
- CAD supplies a tunable interpolation between unambiguous discrimination ($\Delta=0$) and minimum-error discrimination ($\Delta=n-1$); for the quantum change point the minimum-error regime is already reached at $\Delta\approx 8$, so the most relevant operating range uses a small SDP.
- The bound (11) means that solving the minimum-error problem once gives, for free, a certificate of how much success probability is lost when answers must stay within distance $\Delta$ of the truth; no new optimization is needed.
- For the quantum change point, the certified success probability approaches the minimum-error value at least as fast as $(1-2c\,e^{\Delta\log c}+c^2e^{2\Delta\log c})$; numerically, allowing one error unit raises success from $0.27$ to $0.50$ for $n=25$, $c=0.6$, while $90\%$ of answers remain within one position.
- For quantum state anomaly detection, every $\Delta<\lfloor n/2\rfloor$ is provably equivalent to unambiguous discrimination, and the lower bound interpolates linearly between the unambiguous and minimum-error values above that threshold, matching the symmetry of the problem.
- Because the SDP dimension is $O(n\Delta)$ rather than $n^2$, certified discrimination remains numerically tractable precisely in the regime where certification is meaningful.
Reading between the lines
- Not drawn in the paper: the saturation ansatz that underlies the bound could be tested numerically on random ordered Gram matrices; finding a case with no positive-semidefinite completion, or a value of $\tilde{P}_s$ above the true SDP optimum, would pinpoint exactly when the bound breaks.
- If the bound holds generally, the natural reading is that the price of certification is controlled by the tail of the minimum-error outcome distribution: ordered problems whose ME measurement already concentrates its errors within distance $\Delta$ pay almost nothing for certified answers, which is precisely what the QCP numerics show.
- The same SDP machinery transfers directly to non-symmetric tolerances (different allowed distances forward and backward), with the bound acquiring separate $H_i(\Delta_+,\Delta_-)$ terms; this is a concrete, testable generalization the paper only sketches.
- For linearly dependent or noisy ordered states the Gram-matrix route fails, but the CAD constraints can be written directly on the POVM elements; whether an analogous minimum-error-only bound survives there is open.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces 'certified answer discrimination' for ordered sets of linearly independent pure states, in which a POVM must never return an answer more than Delta sites away from the true hypothesis. It gives a block-structured SDP, Eq. (5), and claims a general lower bound on the Delta-scheme success probability that depends only on the minimum-error solution, Eq. (11). The framework is then specialized to the quantum change point and quantum state anomaly detection problems, with numerical comparisons and an analytic bound for the change point, Eq. (21).
Significance. If the lower-bound theorem were valid, the paper would provide a useful interpolation between unambiguous and minimum-error discrimination for ordered hypotheses, and the QCP example would quantify how much success probability is lost by enforcing certified answers. The SDP reformulation in Section II is a coherent and potentially useful contribution, and the numerical demonstrations in Section IV illustrate the behavior of the exact SDP. However, the central analytical result of Section III is not established: the proposed ansatz is infeasible in exactly the rank-one case used in the applications. The advertised general bound and its QCP specialization are therefore unsupported.
major comments (2)
- [Section III, Eqs. (8)-(11)] The proposed lower-bound ansatz is not a feasible point of SDP (6). Feasibility of Z requires Z_ME - Z_Delta >= 0, so every 2-by-2 principal minor must be positive semidefinite. For a rank-one block Z_ME_i = |s_i><s_i|, write a = [Z_ME_i]_{i,i}, b = [Z_ME_i]_{i+Delta+1,i+Delta+1}, x = [Z_ME_i]_{i,i+Delta+1}, and z = [Z_Delta_i]_{i,i}. The (i, i+Delta+1) principal minor of Z_ME - Z_Delta is [[a-z, x], [conj(x), b]], because the off-diagonal entry of Z_Delta_i in that minor vanishes: row i+Delta+1 lies outside the Delta-band. Positivity of this minor requires (a-z)b >= |x|^2. Since |x|^2 = ab for the dyad block, this forces z <= 0, and with z >= 0 it forces z = 0. Thus any nonzero central diagonal element, including the value prescribed by Eq. (9), violates the very positivity condition from which Eq. (8) was derived. Eq. (8) is only a necessary consequence of Eq. (7) obtained through AM-GM; saturating it does not guarantee the determinant condition (7), and no off-diagonal completion can repair the violation because the violation occurs in a principal minor whose only Z_Delta entry is the diagonal element z. Consequently Eq. (11), and its QCP specialization Eq. (21), are unsupported.
- [Section IV, Eqs. (13) and (21)] Even if the lower-bound theorem were valid for the exact ME solution, the QCP application replaces Z_ME by the square-root measurement of Ref. [13] without proving a one-sided bound. The text says that the ME solution 'can be very well approximated' by the square-root measurement, but a certified lower bound requires a controlled direction of approximation, for example Z_ME - Z_SRM >= 0 or a norm estimate with a definite sign. Without such a statement, Eq. (21) is at best an estimate for the square-root measurement rather than a certified lower bound on P_s^Delta.
minor comments (5)
- [Section II] The phrase 'linear independent estates' should read 'linearly independent states'.
- [Introduction] The sentence 'we can have have a one-site error' contains a duplicated word.
- [Appendix A, Eqs. (18) and (A1)] The bound is written as |mu_hat(r,c)| <= M0(c) e^{k log c}; the index r on the left and k in the exponent should be the same symbol.
- [Section IV, QSAD] The claim that for Delta < floor(n/2) the protocol is equivalent to unambiguous discrimination is asserted rather than proved; a derivation of this symmetry reduction should be supplied, since Eq. (30) relies on it.
- [Appendix A] The contour argument should specify the branch cuts of the square root in mu(z,c) and justify taking the limit epsilon -> 0 inside the integral; the proof as written is too terse on these points.
Circularity Check
No circularity: the CAD SDP is an exact reformulation and the lower bound is a derived inequality, not an input renamed as a prediction.
full rationale
The paper's central derivation is self-contained. The SDP (5) is obtained from the original CAD problem (1) by the invertible change of variables F_r = R^\dagger E_r R with R = \sum_i |\Psi_i\rangle\langle i|; this is a reformulation, not an input disguised as a result. The lower bound (11) is derived by constructing a feasible ansatz for the relaxed SDP (6) and saturating inequality (8), which is obtained from the positivity condition (7) via AM-GM. Whether the ansatz is actually feasible is a mathematical correctness question, not a circularity: even if the bound were invalid, it would not be equivalent to its inputs by construction. The QCP application uses the square-root-measurement approximation from Ref. [13], whose authors overlap with the present paper; however, that cited result concerns the minimum-error solution of the quantum change point problem, not the certified-answer success probability, and it is used transparently as an external approximation rather than to force the CAD conclusion. The QSAD analysis is derived directly from the circulant Gram matrix. No fitted parameter is relabeled as a prediction, no uniqueness theorem is imported from the authors' prior work, and no known result is merely renamed. The only notable caveat is the unproven feasibility of the diagonal ansatz in Section III, which is a rigor gap rather than circular reasoning.
Assumptions & free parameters
assumptions (3)
- domain assumption The source states are linearly independent pure states with equal prior probabilities.
- domain assumption The square-root measurement is a sufficiently accurate stand-in for the optimal minimum-error solution in the quantum change point problem.
- ad hoc to paper Saturating the relaxed 2x2 inequality (8) with unspecified off-diagonal elements yields a feasible solution of SDP (6).
Cite this review
Pith. "Pith review of Certified answers for ordered quantum discrimination problems." pith.science (2026). https://pith.science/paper/ATHOCRR7
@misc{pith2026190804093,
author = {Pith},
title = {Pith review of: Certified answers for ordered quantum discrimination problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/ATHOCRR7}},
note = {Machine review of arXiv:1908.04093}
}
read the original abstract
We investigate the quantum state discrimination task for sets of linear independent pure states with an intrinsic ordering. This structured discrimination problems allow for a novel scheme that provides a certified level of error, that is, answers that never deviate from the true value more than a specified distance and hence a control of the desired quality of the results. We obtain an efficient semidefinite program and also find a general lower bound valid for any error distance that only requires the knowledge of optimal minimum error scheme. We apply our results to the quantum change point and quantum state anomaly detection cases.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[13]
G. Sent´ ıs, E. Bagan, J. Calsamiglia, G. Chiribella, and R. Mu˜ noz-Tapia, Quantum change point, Phys. Rev. Lett. 117, 150502 (2016)
work page 2016
-
[1]
C. W. Helstrom, Quantum detection and estimation the- ory (Academic press, 1976)
work page 1976
-
[2]
A. Chefles, Unambiguous discrimination between linearly independent quantum states, Physics Letters A 239, 339 (1998)
work page 1998
-
[3]
T. Rudolph, R. W. Spekkens, and P. S. Turner, Unam- biguous discrimination of mixed states, Physical Review A 68, 010301 (2003)
work page 2003
- [4]
- [5]
- [6]
-
[7]
M. Ban, K. Kurokawa, R. Momose, and O. Hirota, Opti- mum measurements for discrimination among symmetric quantum states and parameter estimation, International Journal of Theoretical Physics 36, 1269 (1997)
work page 1997
Show all 27 references
-
[8]
S. M. Barnett, Minimum-error discrimination between multiply symmetric states, Phys. Rev. A 64, 030303 (2001)
2001
-
[9]
Krovi, S
H. Krovi, S. Guha, Z. Dutton, and M. P. da Silva, Op- timal measurements for symmetric quantum states with applications to optical communication, Phys. Rev. A 92, 062333 (2015)
2015
-
[10]
S. M. Barnett and S. Croke, Quantum state discrimina- tion, Adv. Opt. Photon. 1, 238 (2009)
2009
-
[11]
Chefles, Quantum state discrimina- tion, Contemporary Physics 41, 401 (2000), https://doi.org/10.1080/00107510010002599
A. Chefles, Quantum state discrimina- tion, Contemporary Physics 41, 401 (2000), https://doi.org/10.1080/00107510010002599
2000 doi
-
[12]
Bae and L.-C
J. Bae and L.-C. Kwek, Quantum state discrimination and its applications, Journal of Physics A: Mathematical and Theoretical 48, 083001 (2015)
2015
-
[14]
Sent´ ıs, J
G. Sent´ ıs, J. Calsamiglia, and R. Mu˜ noz-Tapia, Exact identification of a quantum change point, Phys. Rev. Lett. 119, 140506 (2017)
2017
-
[15]
Sent´ ıs, E
G. Sent´ ıs, E. Mart´ ınez-Vargas, and R. Mu˜ noz-Tapia, On- line strategies for exactly identifying a quantum change point, Phys. Rev. A 98, 052305 (2018)
2018
-
[16]
Skotiniotis, R
M. Skotiniotis, R. Hotz, J. Calsamiglia, and R. Mu˜ noz- Tapia, Identification of malfunctioning quantum devices, arXiv:1808.02729 (2018)
2018 arXiv
-
[17]
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition , 10th ed. (Cambridge University Press, New York, NY, USA, 2011)
2011
-
[18]
Vandenberghe and S
L. Vandenberghe and S. Boyd, Semidefinite program- ming, SIAM Review 38, 49 (1996)
1996
-
[19]
Y. C. Eldar, A semidefinite programming approach to optimal unambiguous discrimination of quantum states, IEEE Transactions on Information Theory 49, 446 (2003)
2003
-
[20]
Watrous, The Theory of Quantum Information (Cam- bridge University Press, 2018)
J. Watrous, The Theory of Quantum Information (Cam- bridge University Press, 2018)
2018
-
[21]
Bhatia, Matrix Analysis , Graduate Texts in Mathe- matics (Springer New York, 1996)
R. Bhatia, Matrix Analysis , Graduate Texts in Mathe- matics (Springer New York, 1996)
1996
-
[22]
R. A. Horn and C. R. Johnson, Matrix Analysis , 2nd ed. (Cambridge University Press, New York, NY, USA, 2012)
2012
-
[23]
Hausladen and W
P. Hausladen and W. K. Wootters, A ‘pretty good’ mea- surement for distinguishing quantum states, Journal of Modern Optics 41, 2385 (1994)
1994
-
[24]
Hausladen, R
P. Hausladen, R. Jozsa, B. Schumacher, M. Westmore- land, and W. K. Wootters, Classical information capacity of a quantum channel, Phys. Rev. A 54, 1869 (1996)
1996
-
[25]
Dalla Pozza and G
N. Dalla Pozza and G. Pierobon, Optimality of square- root measurements in quantum state discrimination, Phys. Rev. A 91, 042334 (2015)
2015
-
[26]
R. M. Gray, Toeplitz and circulant matrices: A review, Foundations and Trends in Communications and Infor- mation Theory 2, 155 (2006)
2006
-
[27]
Katznelson, An Introduction To Harmonic Analysis , Cambridge Mathematical Library (Cambridge University Press, 2004)
Y. Katznelson, An Introduction To Harmonic Analysis , Cambridge Mathematical Library (Cambridge University Press, 2004)
2004
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.