pith. sign in

arxiv: 2405.09626 · v2 · submitted 2024-05-15 · 🪐 quant-ph

Permutation tests for quantum state identity

Harry Buhrman , Dmitry Grinko , Philip Verduyn Lunel , Jordi Weggemans This is my paper

Pith reviewed 2026-05-24 01:07 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum state identitypermutation testswap testsemidefinite programmingquantum property testingrepresentation theoryoptimal measurement
0
0 comments X

The pith

An exactly solvable SDP yields the optimal test for deciding if quantum states are identical or pairwise orthogonal under any known distribution.

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

The quantum state identity problem asks whether n unknown states are all the same or all distinct, given the promise that they are either identical or pairwise orthogonal. The authors formulate the task as a semidefinite program whose optimal value is the minimal error probability for a given input distribution. They solve the primal and dual programs in closed form and prove the values coincide, removing the one-sided error restriction that previously limited optimality results. This supplies the exact best measurement for arbitrary distributions and also yields analytic expressions for a family of simpler G-tests based on subgroups of the symmetric group.

Core claim

Casting the quantum state identity problem as a semidefinite program produces exact solutions to both the primal and dual programs whose values coincide, thereby giving the optimal measurement for any known distribution over the identical versus orthogonal cases without requiring one-sided error.

What carries the argument

The semidefinite program whose primal and dual values coincide to give the optimal error probability for the quantum state identity decision task.

If this is right

  • The permutation test is optimal only in the one-sided error regime; the SDP supplies the true optimum once two-sided error is allowed.
  • Any subgroup G of the symmetric group yields an explicit, analytically evaluable test whose performance lies between the trivial and optimal values.
  • The full permutation test can be approximated by a classical permutation of the states followed by n-1 swap tests.
  • For distributions concentrated on particular promise cases, the SDP recovers simpler known tests such as the circle test as special instances.

Where Pith is reading between the lines

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

  • The same SDP technique could be applied to other quantum property-testing problems where the input distribution is known but the error regime is two-sided.
  • When the distribution is uniform over the promise, the optimal value should match the known permutation-test performance, providing an immediate consistency check.
  • Implementation cost can be traded against optimality by choosing smaller subgroups G, suggesting a practical hierarchy of tests for near-term devices.

Load-bearing premise

The input distribution over the identical and orthogonal cases must be known in advance so that the SDP can be solved for that specific distribution.

What would settle it

For a concrete n and distribution, run the SDP to obtain a numerical error bound and check whether an explicit measurement (such as a different subgroup test) achieves a strictly lower error rate on the same promise.

Figures

Figures reproduced from arXiv: 2405.09626 by Dmitry Grinko, Harry Buhrman, Jordi Weggemans, Philip Verduyn Lunel.

Figure 1
Figure 1. Figure 1 [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Visualisation of the Iterated Swap Tree (IST) protocol for n = 8. 5. Approximation of the Permutation test by the Iterated Swap Tree 5.1. The Iterated Swap Tree protocol. We propose a new simple protocol to compute the QSI gp µ problem based only on applying the Swap test in a tree-like way on all the inputs. One motivation is that this protocol will always be correct on equal inputs and hence has perfect … view at source ↗
read the original abstract

The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether $n$ unknown quantum states are equal or unequal, given the promise that all states are either pairwise orthogonal or identical. Under the one-sided error requirement, it is known that the permutation test is optimal for this task, and for two input states this coincides with the well-known Swap test. Until now, the optimal measurement in the general two-sided error regime was unknown. Under more specific promises, the problem can be solved approximately or even optimally with simpler tests, such as the circle test. This work attempts to capture the underlying structure of the quantum state identity problem. Using tools from semidefinite programming and representation theory, we (i) give an optimal test for any input distribution without the one-sided error requirement by writing the problem as an SDP, giving the exact solutions to the primal and dual programs and showing that the two values coincide; (ii) propose a general $G$-test which uses an arbitrary subgroup $G$ of $\text{S}_n$, giving an analytic expression of the performance of the specific test, and (iii) give an approximation of the permutation test using only a classical permutation and $n-1$ Swap tests.

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

0 major / 3 minor

Summary. The paper addresses the two-sided quantum state identity problem (deciding if n states are identical or pairwise orthogonal) by formulating it as an SDP over measurements. It uses representation theory of S_n to obtain closed-form solutions to the primal and dual programs, proving they coincide exactly for any known input distribution over the two cases. It further defines a general G-test for subgroups G of S_n with an analytic performance expression and gives a practical approximation to the permutation test using one classical permutation and n-1 Swap tests.

Significance. If the claimed exact primal-dual coincidence holds, the work supplies the first optimal test for the general two-sided regime, extending the known optimality of the permutation test under one-sided error. The symmetry reduction via representation theory is the natural and standard approach for this hypothesis-testing task and yields parameter-free closed forms; the G-test family and Swap-test approximation add practical value for quantum state discrimination.

minor comments (3)
  1. [§3] §3 (SDP formulation): the promise that the input distribution is known in advance is used to fix the objective; clarify whether the optimal measurement can be computed efficiently when the distribution is only approximately known.
  2. [G-test section] The analytic expression for the G-test (around Eq. (12)) is given in terms of characters of G; an explicit numerical example for a small non-trivial G (e.g., cyclic subgroup) would help readers verify the formula.
  3. [Figure 1] Figure 1 (performance curves): the legend and axis labels are clear, but adding the one-sided permutation-test curve as a reference would make the two-sided improvement visually immediate.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript, including the recognition of the exact primal-dual coincidence for the two-sided quantum state identity problem and the practical value of the G-test family and Swap-test approximation. We appreciate the recommendation for minor revision and will incorporate improvements to clarity and presentation in the revised version.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper formulates the two-sided quantum state identity problem as an SDP over measurements on n copies, then applies the representation theory of S_n to obtain explicit primal and dual solutions whose values are shown to match for arbitrary known input distributions. This chain relies on standard SDP strong duality and the natural symmetry reduction for the symmetric hypothesis-testing task; no step reduces by construction to a fitted parameter, a self-citation chain, or a prior ansatz from the same authors. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, invented entities, or additional axioms beyond the problem promise are visible.

axioms (1)
  • domain assumption States are promised to be either all identical or pairwise orthogonal
    This promise defines the decision problem and is required for the SDP to be well-posed.

pith-pipeline@v0.9.0 · 5758 in / 1096 out tokens · 19702 ms · 2026-05-24T01:07:21.458257+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages · 2 internal anchors

  1. [1]

    Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms

    [Bar+97] Adriano Barenco, Andre Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello. “Stabilization of quantum computations by symmetriza- tion”. In:SIAM Journal on Computing26.5 (1997), pp. 1541–1557.doi:http : //doi.org/10.1137/S0097539796302452(cit. on pp. 2, 6). [BCH06] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow. “Effic...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/s0097539796302452(cit 1997

  2. [2]

    The Weingarten Calculus

    Springer. 2007, pp. 598– 609.doi:http://doi.org/10.1007/978-3-540-70918-3_51(cit. on p. 20). [CMN22] Benoˆ ıt Collins, Sho Matsumoto, and Jonathan Novak. “The Weingarten Calculus”. In:Notices of the American Mathematical Society69.05 (May 2022), p. 1.doi: 10.1090/noti2474.url:http://dx.doi.org/10.1090/noti2474(cit. on p. 5). [C´S06] Benoˆ ıt Collins and P...

    work page doi:10.1007/978-3-540-70918-3_51(cit 2007

  3. [3]

    The church of the symmetric subspace

    arXiv:quant- ph/0512255.url:http://hdl.handle.net/1721.1/34973(cit. on p. 5). [Har13] Aram W Harrow. “The church of the symmetric subspace”. In:arXiv preprint arXiv:1308.6595(2013).doi:https : / / doi . org / 10 . 48550 / arXiv . 1308 . 6595 (cit. on p. 8). [IW18] Mee Seong Im and Angela Wu. “Generalized iterated wreath products of cyclic groups and roote...

    work page arXiv 2013

  4. [4]

    Quantum Certificate Verification: Single versus Multiple Quantum Certificates

    Springer. 2018, pp. 15–28.doi:http://doi.org/10.1007/978-3-319-98684-5_2(cit. on pp. 4, 14). [KMY01] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. “Quantum cer- tificate verification: Single versus multiple quantum certificates”. In:arXiv preprint quant-ph/0110006(2001).doi:https : / / doi . org / 10 . 48550 / arXiv . quant - ph/0110006(cit....

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-3-319-98684-5_2(cit 2018

  5. [5]

    On general minimax theorems

    url:https://books.google.com/books?id=Y6vTBwAAQBAJ&pg=PA180(cit. on p. 8). [Sio58] Maurice Sion. “On general minimax theorems.” In:Pacific Journal of Mathematics 8.1 (1958), pp. 171–176 (cit. on p. 8). [ST21] Vikesh Siddhu and Sridhar Tayur. “Five starter pieces: quantum information science via semi-definite programs”. In:Tutorials in Operations Research:...

    work page 1958

  6. [6]

    In: Proc

    Chap. 3, pp. 59–92.doi:10 . 1287 / educ . 2022.0243. arXiv:2112.08276(cit. on p. 6). [Swa18] Joshua P Swanson. “On the existence of tableaux with given modular major index”. In:Algebraic Combinatorics1.1 (2018), pp. 3–21.doi:http://doi.org/10.5802/ alco.4(cit. on p. 14). [Wat18] John Watrous.The Theory of Quantum Information. Cambridge University Press, 2...

    work page doi:10.1007/978- 2022