Pith. sign in

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 →

arxiv 1908.04093 v2 pith:ATHOCRR7 submitted 2019-08-12 quant-ph

classification quant-ph PACS 03.67.-a
keywords quantumstatediscriminationcertifiedanswerssemidefiniteprogrammingunambiguousminimumerrorchangepointanomalydetectionGrammatrix
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces certified-answer discrimination (CAD) for multi-hypothesis quantum detection in which the candidate states are linearly independent pure states with a natural chain ordering. The task is to maximize the probability of identifying the true state under the hard constraint that no answer may differ from the true position by more than a chosen distance $\Delta$; this sits between unambiguous discrimination ($\Delta=0$) and minimum-error discrimination ($\Delta=n-1$). The paper's central claim is that this optimization is a compact semidefinite program whose data is only the Gram matrix of the states, together with a general lower bound on the certified success probability that can be read off from the solution of the unconstrained minimum-error problem alone. The payoff is a quantitative certificate: for any allowed error distance, one knows how much success probability is sacrificed for answer quality without running a new optimization. Specialized to the quantum change point, the bound predicts an exponential return to the minimum-error value as $\Delta$ grows, and numerically a single allowed unit of error more than doubles the success probability.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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)
  1. [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.
  2. [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)
  1. [Section II] The phrase 'linear independent estates' should read 'linearly independent states'.
  2. [Introduction] The sentence 'we can have have a one-site error' contains a duplicated word.
  3. [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.
  4. [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.
  5. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new physical entities. Its mathematical framework rests on the Gram matrix and the minimum-error solution; the main hidden assumption is the feasibility of the saturating ansatz, which is not established.

assumptions (3)
  • domain assumption The source states are linearly independent pure states with equal prior probabilities.
    Used to define the R matrix and the Gram matrix transformation in Section II; stated as an assumption in the paper.
  • domain assumption The square-root measurement is a sufficiently accurate stand-in for the optimal minimum-error solution in the quantum change point problem.
    Invoked in Section IV from Ref. [13]; needed for the decay estimates and final bound (21), but optimality or accuracy is not proven here.
  • ad hoc to paper Saturating the relaxed 2x2 inequality (8) with unspecified off-diagonal elements yields a feasible solution of SDP (6).
    This is the flawed step: the inequality is necessary only after relaxing the sharp determinant condition, and no PSD completion is constructed. In rank-one blocks, the (i,j) minor with j outside the band forces the central diagonal to zero.

how reviews work

0 comments
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 reproduced from arXiv: 1908.04093 by the authors.

Figure 1
Figure 1. Structure of the source states. The position of the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. Structure of the matrix variable Z for ∆ = 1. The blue boxes correspond to the free matrix elements and the blank ones are fixed to be zero. The highlighted boxes are the elements that appear in the objective function (1/n) Tr[ZA] of Eq. (5). Φ1[Z] = . . . . . . . . . + + + . . [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. The correspondent map takes the non-zero parts of [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figures from the paper (5 more)
Figure 5
Figure 5. Figure 5: We depict a specific block r of Z ME − Z ∆. The light blue block corresponds to Z ME r and the darker one to Z ∆ r . The small black boxes show the elements of the minor of interest to obtain the bound (9). having previously solved the ME scheme, i.e. we have at our di…
Figure 6
Figure 6. Figure 6: A machine produces a signal state and suddenly it [PITH_FULL_IMAGE:figures/full_fig_p005_6.png]
Figure 7
Figure 7. Figure 7: Probability of success versus the allowed error dis [PITH_FULL_IMAGE:figures/full_fig_p005_7.png]
Figure 8
Figure 8. Figure 8: Outcome probability profile of the minimum error [PITH_FULL_IMAGE:figures/full_fig_p005_8.png]
Figure 9
Figure 9. Figure 9: Probability of success against the error distance ∆ [PITH_FULL_IMAGE:figures/full_fig_p007_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 23 canonical work pages

  1. [13]

    Sent´ ıs, E

    G. Sent´ ıs, E. Bagan, J. Calsamiglia, G. Chiribella, and R. Mu˜ noz-Tapia, Quantum change point, Phys. Rev. Lett. 117, 150502 (2016)

  2. [1]

    C. W. Helstrom, Quantum detection and estimation the- ory (Academic press, 1976)

  3. [2]

    Chefles, Unambiguous discrimination between linearly independent quantum states, Physics Letters A 239, 339 (1998)

    A. Chefles, Unambiguous discrimination between linearly independent quantum states, Physics Letters A 239, 339 (1998)

  4. [3]

    Rudolph, R

    T. Rudolph, R. W. Spekkens, and P. S. Turner, Unam- biguous discrimination of mixed states, Physical Review A 68, 010301 (2003)

  5. [4]

    Croke, E

    S. Croke, E. Andersson, S. M. Barnett, C. R. Gilson, and J. Jeffers, Maximum confidence quantum measurements, Phys. Rev. Lett. 96, 070401 (2006)

  6. [5]

    Bagan, R

    E. Bagan, R. Mu˜ noz-Tapia, G. A. Olivares-Renter´ ıa, and J. A. Bergou, Optimal discrimination of quantum states with a fixed rate of inconclusive outcomes, Phys. Rev. A 86, 040303 (2012)

  7. [6]

    Singal, E

    T. Singal, E. Kim, and S. Ghosh, Structure of mini- mum error discrimination for linearly independent states, Phys. Rev. A 99, 052334 (2019)

  8. [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)

Show all 27 references
  1. [8]

    S. M. Barnett, Minimum-error discrimination between multiply symmetric states, Phys. Rev. A 64, 030303 (2001)

  2. [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)

  3. [10]

    S. M. Barnett and S. Croke, Quantum state discrimina- tion, Adv. Opt. Photon. 1, 238 (2009)

  4. [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

  5. [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)

  6. [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)

  7. [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)

  8. [16]

    Skotiniotis, R

    M. Skotiniotis, R. Hotz, J. Calsamiglia, and R. Mu˜ noz- Tapia, Identification of malfunctioning quantum devices, arXiv:1808.02729 (2018)

  9. [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)

  10. [18]

    Vandenberghe and S

    L. Vandenberghe and S. Boyd, Semidefinite program- ming, SIAM Review 38, 49 (1996)

  11. [19]

    Y. C. Eldar, A semidefinite programming approach to optimal unambiguous discrimination of quantum states, IEEE Transactions on Information Theory 49, 446 (2003)

  12. [20]

    Watrous, The Theory of Quantum Information (Cam- bridge University Press, 2018)

    J. Watrous, The Theory of Quantum Information (Cam- bridge University Press, 2018)

  13. [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)

  14. [22]

    R. A. Horn and C. R. Johnson, Matrix Analysis , 2nd ed. (Cambridge University Press, New York, NY, USA, 2012)

  15. [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)

  16. [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)

  17. [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)

  18. [26]

    R. M. Gray, Toeplitz and circulant matrices: A review, Foundations and Trends in Communications and Infor- mation Theory 2, 155 (2006)

  19. [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)

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.