Quantum Advantage in Identifying the Parity of Permutations with Certainty
A. Diebra 1 , S. Llorens 1 , D. González-Lociga 1 , A. Rico 1 , J. Calsamiglia 1 , M. Hillery 2 , and E. Bagan 1 · 2025
Read Quantum Advantage in Identifying the Parity of Permutations with Certainty by A. Diebra 1 , S. Llorens 1 , D. González-Lociga 1 , A. Rico 1 , J. Calsamiglia 1 , M. Hillery 2 , and E. Bagan 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-04310.txt.
Introduction
A seven-author team proves a clean case where quantum mechanics beats every classical method with certainty. The task is to tell whether an unknown permutation of n objects is even or odd. Classically, anything short of checking all n labels leaves success no better than a coin flip. The authors show that entangled particles settle the question perfectly.
Each particle needs only about the square root of n distinguishable states, far fewer than the classical demand. Below that threshold, quantum methods also collapse to guessing, so the boundary is sharp. For small cases the authors write down the exact states that work. They also measure how much entanglement those states must carry: close to the maximum possible, and in some cases fully maximal. Because the task needs no oracle or contrived setup, they offer it as a simple, rigorous showcase of genuine quantum advantage.
Catalog record
| CREATOR | A. Diebra 1 , S. Llorens 1 , D. González-Lociga 1 , A. Rico 1 , J. Calsamiglia 1 , M. Hillery 2 , and E. Bagan 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 147 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-04310
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Advantage in Identifying the Parity of Permutations with Certainty A. Diebra 1 , S. Llorens 1 , D. González-Lociga 1 , A. Rico 1 , J. Calsamiglia 1 , M. Hillery 2 , and E. Bagan 1 Abstract We establish a sharp quantum advantage in determining the parity (even/odd) of an unknown permutation applied to any number n ≥ 3 n\geq 3 of particles. Classically, this is impossible with fewer than n n labels, being the success limited to random guessing. Quantum mechanics does it with certainty with as few as ⌈ n ⌉ \lceil\sqrt{n}\,\rceil distinguishable states per particle, thanks to entanglement. Below this threshold, not even quantum mechanics helps: both classical and quantum success are limited to random guessing. For small n n , we provide explicit expressions for states that ensure perfect parity identification. We also assess the minimum entanglement these states need to carry, finding it to be close to maximal, and even maximal in some cases. The task requires no oracles or contrived setups and provides a simple, rigorous example of genuine quantum advantage. pacs 03.67.-a, 03.65.Ta,42.50.-p Introduction . One of the defining goals of quantum information science is to identify tasks that quantum systems can perform better than classical ones, a phenomenon broadly known as quantum advantage. Over the past two decades, many such examples have emerged: exponential speedups relative to the best known classical algorithms, as in Shor’s factoring Shor1997 ; reductions in communication complexity Buhrman2010 , e.g., Random Access Codes (RACs) PhysRevLett.114.170502 and quantum fingerprinting buhrman2001quantum ; improvements in learning efficiency huang2022quantum ; or exponential query savings in oracle-based problems, such as Simon’s Simon1997 and the Bernstein–Vazirani doi:10.1137/S0097539796300921 ; naseri2022entanglement algorithms—both special cases of the abelian hidden subgroup problem. The recent experimental achievement of quantum supremacy Arute2019 ; Preskill2012 can be viewed as an extreme case of quantum advantage, where a quantum device performs a computational task beyond the reach of classical supercomputers. While a significant portion of the literature has focused on quantum algorithms and computational tasks, quantum advantage also arises in a variety of physically motivated settings, from quantum communication and metrology to nonlocal correlations. These instances highlight how quantum resources such as coherence Streltsov2017 , contextuality amaral2019resource ; gupta2023quantum , and entanglement plenio2014introduction can yield capabilities fundamentally unattainable by classical systems. For example, entanglement-enhanced metrology enables Heisenberg-limited precision Giovannetti2011 , and quantum communication protocols such as teleportation Bennett1993 and dense coding Bennett1992 enable tasks that are fundamentally impossible using classical resources alone. In this work, we propose a problem that is elementary to state, physically natural, and yet exhibits a sharp separation between classical and quantum capabilities. It requires no complex communication setup, no oracle for function evaluation, and no computational promises—just a set of n particles, subject to a hidden permutation, and the simple binary question: is it even or odd? Swapping is arguably the most primitive and universal transformation one can perform on a set of objects. It applies regardless of their nature; it is simply a rearrangement. Classically, if each particle carries a distinct label—e.g., n different colors—one can perfectly reconstruct the permutation and read off its parity. But with even one fewer label, perfect parity identification becomes impossible: every permutation has an opposite-parity counterpart producing the same label arrangement, and the best one can do is guess, with success probability P_{\rm s}=1/2 . Quantum systems, however, allow us to do fundamentally better. By preparing the n particles in a suitable initial entangled state |\psi_{e}\rangle of qudits (each of local dimension d ), we show that Theorem I . Perfect parity identification ( P_{\rm s}=1 ) is achievable if d\geq d_{\rm min}:=\left\lceil\sqrt{n}\,\right\rceil. (1) Below this threshold, assuming all permutations are equally likely, parity remains indistinguishable and random guessing is the best one can do ( P_{\rm s}=1/2 ). Thus, from a quantum system in which each of the n constituents carries quadratically fewer distinguishable states than classically required, one can nonetheless extract the parity of the hidden permutation with certainty, thanks to entanglement—for local dimension below d_{\rm min} , not even quantum resources help. If Eq. ( 1 ) holds, a parity-detecting state |\psi_{e}\rangle exists, and the subspaces spanned by the action of the even and odd permutations on |\psi_{e}\rangle are mutually orthogonal, allowing parity identification by a projective measurement. Theorem I makes our protocol a clear-cut example of genuine quantum advantage: the task is naturally defined, with a rigorously provable classical limitation, and, as will be shown, its quantum solution relies on fundamental structural properties of multipartite entangled states under permutation symmetry. We emphasize that our result, summarized in Theorem I , is non-asymptotic : it holds exactly for every n , not just in the large- n limit. This contrasts with other permutation-based protocols, such as those introduced in korff2004quantum and extended in PhysRevA.71.012326 , where certainty is achieved only asymptotically. In korff2004quantum , asymptotic zero-error identification of the applied permutation (not just its parity) is achievable iff d\geq n/\mathrm{e} , where \mathrm{e} is Euler’s constant, while PhysRevA.71.012326 shows that the same asymptotic performance can be attained with d\sim\sqrt{n} using ancillary systems. Our protocol also bears some resemblance with the algorithm introduced in gedik2015computational and experimentally demonstrated in wang2015demonstration ; dai2018demonstration . Although it involves a single quantum register (a single qudit), with the permutation applied to its internal basis states via a quantum oracle, the state used for perfect parity identification in the qutrit case can be mapped to the three-qubit version of our general n -qudit state |\psi_{e}\rangle supp_mat : |\psi_{e}\rangle=|011\rangle+\zeta_{3}|101\rangle+\zeta_{3}^{2}|110\rangle. (2) (Throughout this letter, states are given unnormalized) Here \zeta_{N}:={\rm e}^{2\pi i/N} is the N -th root of unity, and we adopt the standard notation |i_{1}i_{2}\dots\rangle=|i_{1}\rangle\otimes|i_{2}\rangle\otimes\cdots , with i_{p}\in\{0,1,\dots,d-1\} for p=1,2,\dots,n . One can easily verify that \sigma_{\rm odd}|\psi_{e}\rangle is orthogonal to \sigma_{\rm even}|\psi_{e}\rangle\propto|\psi_{e}\rangle for any odd, respectively even, permutation. In the ququart case ( d=4 ), however, the authors consider only a restricted subset of permutations, and the notion of parity in that context is not clearly defined. Since their scheme involves a single qudit, no entanglement is present, and the observed quantum advantage is attributed instead to contextuality. This letter is organized as follows. We begin with three explicit examples to gradually introduce notation and highlight features that generalize to arbitrary n . We then prove Theorem I , using group and representation theory. Finally, we assess the multipartite entanglement required by our protocol and close with a brief summary and outlook. Example: four qubits. The case of four particles already reveals the essential ingredients that enable perfect parity identification. For concreteness, consider a system of four spin- \tfrac{1}{2} particles, on which some agent (Alice) acts by reshuffling their positions without disturbing their spin degrees of freedom. The Hilbert space of the system, (\mathbb{C}^{2})^{\otimes 4} , can be decomposed (via, e.g., the standard Clebsch–Gordan coefficients) into a direct sum of \mathrm{SU}(2) -invariant subspaces \mathscr{H}_{j} labeled by the total spin j hamermesh2012group : (\mathbb{C}^{2})^{\otimes 4}\cong\left(\mathscr{K}_{2}\otimes\mathscr{H}_{2}\right)\oplus\left(\mathscr{K}_{1}\otimes\mathscr{H}_{1}\right)\oplus\left(\mathscr{K}_{0}\otimes\mathscr{H}_{0}\right), (3) where the \mathscr{K}_{j} factors account for the multiplicity of each spin sector: \mathscr{K}_{2}\cong\mathbb{C} , \mathscr{K}_{1}\cong\mathbb{C}^{3} , and \mathscr{K}_{0}\cong\mathbb{C}^{2} (corresponding to 1, 3, and 2 copies , respectively). The group \mathrm{SU}(2) acts only on the spin factors \mathscr{H}_{j} and trivially on the multiplicity spaces \mathscr{K}_{j}