pith. sign in

arxiv: 2312.04023 · v2 · submitted 2023-12-07 · 🪐 quant-ph

A hybrid quantum-classical algorithm for Bayes-optimal quantum state discrimination using the source code

Ankith Mohan , Jamie Sikora , Sarvagya Upadhyay This is my paper

Pith reviewed 2026-05-24 04:55 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum state discriminationBayes optimal discriminationsemidefinite programGram matrixquantum preprocessingchangepoint detectionerror classification
0
0 comments X

The pith

Bayes-optimal quantum state discrimination SDP reduces to Gram matrix form when given source circuits.

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

When states are available only through their preparing quantum circuits, the optimal discrimination problem can be recast using the Gram matrix of the states rather than their full density operators. This shrinks the semidefinite program's variable size from dL to NL. A quantum preprocessing step then builds the smaller program directly from the circuits. The method makes optimal solutions feasible for changepoint detection and error classification on large qubit systems.

Core claim

The semidefinite program for Bayes-optimal discrimination can be reformulated in terms of the Gram matrix of these states, reducing the SDP variable dimensions from dL to NL. A quantum pre-processing procedure efficiently constructs the reduced semidefinite program from the source code, enabling operation directly on quantum data.

What carries the argument

Gram matrix reformulation of the discrimination SDP combined with quantum pre-processing to extract it from source circuits.

If this is right

  • Optimal identifications for quantum changepoint problems can be found under multiple reward structures.
  • Multiple-changepoint settings that were previously inaccessible become solvable.
  • Quantum error classification scales to systems of hundreds of qubits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This reduction could apply to other quantum tasks involving discrimination of circuit-prepared states.
  • Hybrid algorithms might benefit from using the Gram matrix approach in quantum sensing or communication protocols.
  • Further work could explore whether the preprocessing overhead remains low for even larger systems.

Load-bearing premise

The quantum pre-processing procedure constructs the reduced SDP exactly and efficiently from the source circuits without approximation or prohibitive overhead.

What would settle it

For a small known instance, running the preprocessing and comparing the optimal value of the reduced SDP against the known full SDP optimum would show mismatch if the construction is inexact.

Figures

Figures reproduced from arXiv: 2312.04023 by Ankith Mohan, Jamie Sikora, Sarvagya Upadhyay.

Figure 1
Figure 1. Figure 1: A quantum source is sending a stream of |ψ⟩ states but two mutations occurred in this example. The task is to design an optimal detector to guess when the mutations occurred. For part of this paper, we assume that both the promised state as well as the mutated ones are known to Bob. (We also discuss the case when they are unknown but we have a source of them to perform some precomputations.) Observe that t… view at source ↗
Figure 2
Figure 2. Figure 2: plots the optimal reward value for a single change point example. 3 10 20 30 40 50 60 70 80 Length of sequence, N 0.70 0.75 0.80 0.85 0.90 0.95 1.00 Reward function value = 0 = 1 = 2 = 3 = 4 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: We consider here the closer-the-better reward scheme with [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Here we consider the sequences where the state [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: We examine the sequences with three change points, each of [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Circuits to learn the inner product between two (perhaps unknown) states [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The state |0⟩ promised by Alice and the possible mutated states |+⟩, |1⟩ and − |−⟩ that Bob suspects of receiving. At most one change point. Here, we look at the case when Bob suspects Alice’s device of either having no mutations or ones that generate |+⟩. So Bob needs to determine exactly where this change point occurred. This is accomplished by discriminating between the states described by Eq. (47) and … view at source ↗
Figure 8
Figure 8. Figure 8: Here we consider the sequences where the state [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Here we look at the case where the state [PITH_FULL_IMAGE:figures/full_fig_p020_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: We look at sequences with three change points, each being sequences of [PITH_FULL_IMAGE:figures/full_fig_p021_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Consider the sequences when Alice promises Bob [PITH_FULL_IMAGE:figures/full_fig_p030_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Here we consider the scenario where the state [PITH_FULL_IMAGE:figures/full_fig_p030_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: The final case is where there are three stages of mutations: (1) from [PITH_FULL_IMAGE:figures/full_fig_p031_13.png] view at source ↗
read the original abstract

Quantum state discrimination is a fundamental primitive in quantum information processing, underpinning tasks in quantum communication, sensing, and learning. We consider the general Bayes framework, as introduced by Helstrom, for state discrimination when, instead of a classical description of the candidate states, one has access to their \emph{source code}: the quantum circuit that prepares them. We show that the semidefinite program (SDP) for the discrimination problem can be reformulated in terms of the Gram matrix of these states, reducing the SDP variable dimensions from $dL$ to $NL$, where $d$ is the Hilbert space dimension, $N$ is the number of candidate states, and $L$ is the number of possible guesses. Importantly, we further introduce a quantum pre-processing procedure which efficiently constructs the reduced semidefinite program from the source code, enabling our method to operate directly on quantum data. We consider two applications. First, we characterize the optimal identifications for quantum changepoint problems under several reward structures, including multiple-changepoint settings that were previously computationally inaccessible. Second, we consider a quantum error classification problem and show how our reduction makes it tractable for systems of hundreds of qubits.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that the Bayes-optimal quantum state discrimination SDP can be algebraically reformulated in terms of the Gram matrix of the candidate states (reducing SDP variable dimension from dL to NL), and that a quantum pre-processing procedure can construct this reduced SDP exactly and efficiently directly from the source circuits that prepare the states. Two applications are presented: optimal identification in multi-changepoint problems (previously inaccessible) and error classification on systems of hundreds of qubits.

Significance. If the pre-processing step is both exact and efficient at the claimed scales, the work would enable optimal discrimination on quantum data without classical state descriptions and would make previously intractable changepoint and large-scale error-classification instances computationally feasible. The dimension reduction itself follows from standard linear-algebra facts about pure-state Gram matrices and is not novel, but the end-to-end hybrid procedure would be a useful practical contribution if the efficiency claim holds.

major comments (2)
  1. [Abstract] Abstract and introduction: the claim that the introduced quantum pre-processing procedure 'efficiently constructs the reduced semidefinite program from the source code' and enables tractability for 'hundreds-of-qubit error classification' is load-bearing for both applications, yet the provided text contains no derivation, resource analysis, or error bound showing that the procedure yields the exact Gram matrix without statistical approximation or prohibitive overhead.
  2. [Applications] Applications (changepoint and error-classification sections): for N candidate states the Gram-matrix construction requires all N² overlaps; when these must be obtained via swap-test or Hadamard-test estimation on circuits of depth scaling with hundreds of qubits, the sample complexity and total runtime are not shown to remain polynomial or even practical, undermining the tractability claim for the error-classification example.
minor comments (2)
  1. Notation: the manuscript should explicitly state whether the source circuits are assumed to be known classically (so that overlaps can be computed exactly) or only executable on a quantum device (forcing statistical estimation).
  2. [Abstract] The abstract states the dimension reduction but does not cite the standard reference for the Gram-matrix SDP formulation of Helstrom discrimination; adding this reference would improve context.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for identifying the need for greater detail on the quantum pre-processing procedure and its scaling. We address the two major comments below, providing the requested clarifications on exact construction and resource bounds. We will revise the manuscript to incorporate an explicit derivation and complexity analysis.

read point-by-point responses

  1. Referee: [Abstract] Abstract and introduction: the claim that the introduced quantum pre-processing procedure 'efficiently constructs the reduced semidefinite program from the source code' and enables tractability for 'hundreds-of-qubit error classification' is load-bearing for both applications, yet the provided text contains no derivation, resource analysis, or error bound showing that the procedure yields the exact Gram matrix without statistical approximation or prohibitive overhead.

    Authors: We agree the manuscript would benefit from an explicit derivation. The quantum pre-processing uses the source circuits directly: for each pair of states, a controlled-SWAP test (or equivalent Hadamard-test circuit) is applied with the two source circuits as oracles, measuring an ancillary qubit to obtain the exact overlap <psi_i|psi_j> in the ideal case. This yields the precise N x N Gram matrix without reconstructing d-dimensional states. We will add a dedicated subsection deriving the circuit (depth linear in source depth, O(N^2) parallel tests) and confirming exactness. For the error-classification example the source circuits are local with depth independent of total qubit number, so preprocessing overhead remains polynomial. Resource analysis and error bounds (additive SDP perturbation O(epsilon)) will be included. revision: yes

  2. Referee: [Applications] Applications (changepoint and error-classification sections): for N candidate states the Gram-matrix construction requires all N² overlaps; when these must be obtained via swap-test or Hadamard-test estimation on circuits of depth scaling with hundreds of qubits, the sample complexity and total runtime are not shown to remain polynomial or even practical, undermining the tractability claim for the error-classification example.

    Authors: N denotes the number of candidate states (changepoint locations or error classes) and remains small and independent of Hilbert-space dimension d. In the error-classification application N is a fixed constant while qubit number reaches hundreds; each source circuit is local, so controlled-SWAP depth is O(1) per pair. Sample complexity per overlap is O(1/epsilon^2) shots for additive error epsilon; setting epsilon = 1/poly(N) suffices for SDP accuracy and keeps total samples polynomial in N. We will add an explicit sample-complexity paragraph showing overall runtime polynomial in the parameters of the presented instances. The concern would apply if N scaled with system size, but that regime is outside the applications considered. revision: partial

Circularity Check

0 steps flagged

No circularity; reformulation uses standard Gram-matrix property independent of paper's results

full rationale

The paper's core reduction of the Helstrom SDP to a Gram-matrix form (dimensions dL to NL) follows directly from the algebraic fact that optimal discrimination depends only on the set of pairwise inner products among the candidate states; this is a standard, externally verifiable property of quantum state discrimination and does not rely on any self-citation, fitted parameter, or ansatz introduced by the authors. The quantum pre-processing procedure is presented as a novel construction that produces this Gram matrix from circuit descriptions, without any equation or claim reducing by construction to the paper's own inputs or prior self-citations. No load-bearing uniqueness theorems, self-definitional steps, or renaming of known results appear in the derivation chain. The method is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on the standard mathematical fact that the Gram matrix determines the relevant statistics for state discrimination and on the existence of an efficient quantum circuit that extracts those overlaps from the source circuits.

axioms (2)
  • standard math The Gram matrix of the candidate states encodes all inner-product information required to solve the Bayes-optimal discrimination SDP.
    Invoked when the abstract states that the SDP can be reformulated in terms of the Gram matrix.
  • domain assumption A quantum preprocessing circuit exists that efficiently computes the Gram matrix entries directly from the source circuits preparing the states.
    Stated in the abstract as the key enabling step that allows operation on quantum data.

pith-pipeline@v0.9.0 · 5745 in / 1401 out tokens · 21283 ms · 2026-05-24T04:55:56.132934+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The most discriminable quantum states in the multicopy regime

    quant-ph 2026-04 unverdicted novelty 7.0

    k-designs achieve maximal discriminability for pure states in multi-copy minimum-error discrimination; mixed states outperform for larger ensembles, with quantum offering quadratic advantage over classical.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · cited by 1 Pith paper

  1. [1]

    Minimum-error discrimination between three mirror-symmetric states

    Erika Andersson, Stephen M Barnett, Claire R Gilson, and Kieran Hunter. Minimum-error discrimination between three mirror-symmetric states. Physical Review A , 65(5):052308, 2002

    work page 2002

  2. [2]

    A survey of methods for time series change point detection

    Samaneh Aminikhanghahi and Diane J Cook. A survey of methods for time series change point detection. Knowledge and information systems , 51(2):339--367, 2017

    work page 2017

  3. [3]

    A polynomial quantum algorithm for approximating the J ones polynomial, 2006

    Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the J ones polynomial, 2006

    work page 2006

  4. [4]

    A new protocol and lower bounds for quantum coin flipping

    Andris Ambainis. A new protocol and lower bounds for quantum coin flipping. In Proceedings of the thirty-third annual ACM symposium on Theory of computing , pages 134--142, 2001

    work page 2001

  5. [5]

    Quantum bit escrow

    Dorit Aharonov, Amnon Ta-Shma, Umesh V Vazirani, and Andrew C Yao. Quantum bit escrow. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 705--714, 2000

    work page 2000

  6. [6]

    Structure of minimum-error quantum state discrimination

    Joonwoo Bae. Structure of minimum-error quantum state discrimination. New Journal of Physics , 15(7):073037, 2013

    work page 2013

  7. [7]

    Minimum-error discrimination between multiply symmetric states

    Stephen M Barnett. Minimum-error discrimination between multiply symmetric states. Physical Review A , 64(3):030303, 2001

    work page 2001

  8. [8]

    Quantum state discrimination

    Stephen M Barnett and Sarah Croke. Quantum state discrimination. Advances in Optics and Photonics , 1(2):238--278, 2009

    work page 2009

  9. [9]

    Quantum fingerprinting

    Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting. Physical Review Letters , 87(16):167902, 2001

    work page 2001

  10. [10]

    Quantum state discrimination and selected applications

    J \'a nos A Bergou. Quantum state discrimination and selected applications. In Journal of Physics: Conference Series , volume 84, page 012001. IOP Publishing, 2007

    work page 2007

  11. [11]

    Discrimination of quantum states

    J \'a nos A Bergou. Discrimination of quantum states. Journal of Modern Optics , 57(3):160--180, 2010

    work page 2010

  12. [12]

    Iterative quantum-assisted eigensolver

    Kishor Bharti and Tobias Haug. Iterative quantum-assisted eigensolver. Physical Review A , 104(5):L050401, 2021

    work page 2021

  13. [13]

    D iscrimination of quantum states

    J \'a nos A Bergou, Ulrike Herzog, and Mark Hillery. D iscrimination of quantum states. Quantum State Estimation , pages 417--465, 2004

    work page 2004

  14. [14]

    Conclusive exclusion of quantum states

    Somshubhro Bandyopadhyay, Rahul Jain, Jonathan Oppenheim, and Christopher Perry. Conclusive exclusion of quantum states. Physical Review A , 89(2):022336, 2014

    work page 2014

  15. [15]

    Covariant quantum measurements that maximize the likelihood

    Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti, and Massimiliano F Sacchi. Covariant quantum measurements that maximize the likelihood. Physical Review A , 70(6):062105, 2004

    work page 2004

  16. [16]

    Maximum likelihood estimation for a group of physical transformations

    Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti, and Massimiliano F Sacchi. Maximum likelihood estimation for a group of physical transformations. International Journal of Quantum Information , 4(03):453--472, 2006

    work page 2006

  17. [17]

    Unambiguous discrimination between linearly independent quantum states

    Anthony Chefles. Unambiguous discrimination between linearly independent quantum states. Physics Letters A , 239(6):339--347, 1998

    work page 1998

  18. [18]

    Quantum state discrimination

    Anthony Chefles. Quantum state discrimination. Contemporary Physics , 41(6):401--424, 2000

    work page 2000

  19. [19]

    CVX : Matlab software for disciplined convex programming, version 2.0

    CVX Research, Inc. CVX : Matlab software for disciplined convex programming, version 2.0. http://cvxr.com/cvx, August 2012

    work page 2012

  20. [20]

    Mixed-quantum-state detection with inconclusive results

    Yonina C Eldar. Mixed-quantum-state detection with inconclusive results. Physical Review A , 67(4):042309, 2003

    work page 2003

  21. [21]

    Optimal detection of symmetric mixed quantum states

    Yonina C Eldar, Alexandre Megretski, and George C Verghese. Optimal detection of symmetric mixed quantum states. IEEE Transactions on Information Theory , 50(6):1198--1207, 2004

    work page 2004

  22. [22]

    Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    Andr \'a s Gily \'e n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 193--204, 2019

    work page 2019

  23. [23]

    Near-term quantum algorithms for linear systems of equations,

    Hsin-Yuan Huang, Kishor Bharti, and Patrick Rebentrost. Near-term quantum algorithms for linear systems of equations. arXiv preprint arXiv:1909.07344 , 2019

    work page arXiv 1909

  24. [24]

    Quantum detection and estimation theory

    Carl W Helstrom. Quantum detection and estimation theory. Journal of Statistical Physics , 1:231--252, 1969

    work page 1969

  25. [25]

    Quantum measurements for hidden subgroup problems with optimal sample complexity

    M Hayashi, A Kawachi, and H Kobayashi. Quantum measurements for hidden subgroup problems with optimal sample complexity. Quantum Information and Computation , 8(3&4):345--358, 2008

    work page 2008

  26. [26]

    Tight bounds for antidistinguishability and circulant sets of pure quantum states

    Nathaniel Johnston, Vincent Russo, and Jamie Sikora. Tight bounds for antidistinguishability and circulant sets of pure quantum states. arXiv preprint arXiv:2311.17047 , 2023

    work page arXiv 2023

  27. [27]

    Optimal distinction between two non-orthogonal quantum states

    Gregg Jaeger and Abner Shimony. Optimal distinction between two non-orthogonal quantum states. Physics Letters A , 197(2):83--87, 1995

    work page 1995

  28. [28]

    Advanced unambiguous state discrimination attack and countermeasure strategy in a practical B 92 QKD system

    Heasin Ko, Byung-Seok Choi, Joong-Seon Choe, and Chun Ju Youn. Advanced unambiguous state discrimination attack and countermeasure strategy in a practical B 92 QKD system. Quantum Information Processing , 17:1--14, 2018

    work page 2018

  29. [29]

    Methodology for replacing indirect measurements with direct measurements

    Kosuke Mitarai and Keisuke Fujii. Methodology for replacing indirect measurements with direct measurements. Physical Review Research , 1(1):013006, 2019

    work page 2019

  30. [30]

    On the optimal error exponents for classical and quantum antidistinguishability

    Hemant K Mishra, Michael Nussbaum, and Mark M Wilde. On the optimal error exponents for classical and quantum antidistinguishability. arXiv preprint arXiv:2309.03723 , 2023

    work page arXiv 2023

  31. [31]

    Inner products of pure states and their antidistinguishability

    Vincent Russo and Jamie Sikora. Inner products of pure states and their antidistinguishability. Physical Review A , 107(3):L030202, 2023

    work page 2023

  32. [32]

    Unambiguous discrimination of mixed states

    Terry Rudolph, Robert W Spekkens, and Peter S Turner. Unambiguous discrimination of mixed states. Physical Review A , 68(1):010301, 2003

    work page 2003

  33. [33]

    Measuring ultrasmall time delays of light by joint weak measurements

    Gr \'e gory Str \"u bi and C Bruder. Measuring ultrasmall time delays of light by joint weak measurements. Physical Review Letters , 110(8):083605, 2013

    work page 2013

  34. [34]

    Quantum change point

    Gael Sent \' s, Emilio Bagan, John Calsamiglia, Giulio Chiribella, and Ramon Munoz-Tapia. Quantum change point. Physical Review Letters , 117(15):150502, 2016

    work page 2016

  35. [35]

    Exact identification of a quantum change point

    Gael Sent \' s, John Calsamiglia, and Ramon Munoz-Tapia. Exact identification of a quantum change point. Physical Review Letters , 119(14):140506, 2017

    work page 2017

  36. [36]

    Simple, near-optimal quantum protocols for die-rolling

    Jamie Sikora. Simple, near-optimal quantum protocols for die-rolling. Cryptography , 1(2):11, 2017

    work page 2017

  37. [37]

    Optimal bounded-error strategies for projective measurements in nonorthogonal-state discrimination

    Maximilian Puelma Touzel, Robert B A Adamson, and Aephraim M Steinberg. Optimal bounded-error strategies for projective measurements in nonorthogonal-state discrimination. Physical Review A , 76(6):062314, 2007

    work page 2007

  38. [38]

    Security of the B ennett 1992 quantum-key distribution protocol against individual attack over a realistic channel

    Kiyoshi Tamaki, Masato Koashi, and Nobuyuki Imoto. Security of the B ennett 1992 quantum-key distribution protocol against individual attack over a realistic channel. Physical Review A , 67(3):032310, 2003

    work page 1992

  39. [39]

    All quantum resources provide an advantage in exclusion tasks

    Roope Uola, Tom Bullock, Tristan Kraft, Juha-Pekka Pellonp \"a \"a , and Nicolas Brunner. All quantum resources provide an advantage in exclusion tasks. Physical Review Letters , 125(11):110402, 2020

    work page 2020