Quantum Advantage in Identifying the Parity of Permutations with Certainty
- 23 December 2025
- journal article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 135 (26) , 260603
Abstract
We establish a sharp quantum advantage in determining the parity (even-odd) of an unknown permutation applied to any number n≥3 of particles. Classically, this is impossible with fewer than n labels, being that the success is limited to random guessing. Quantum mechanics does it with certainty with as few as ⌈sqrt[n] ⌉ 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, 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.Keywords
All Related Versions
Funding Information
- Ministerio de Ciencia e Innovación (PID2022-139099NB-I00)
- Ministerio de Ciencia e Innovación (FPU23/02763)
- NextGenerationEU (PRTR-C17.I1)
- Generalitat de Catalunya
- Ministerio de Economía y Competitividad
- Agencia Estatal de Investigación (PID2022-141283NB-I00)
- Institució Catalana de Recerca i Estudis Avançats
- European Regional Development Fund
This publication has 36 references indexed in Scilit:
- Dynamical Decomposition of Bilinear Control Systems Subject to SymmetriesJournal of Dynamical and Control Systems, 2020
- Quantum supremacy using a programmable superconducting processorNature, 2019
- Computational speed-up with a single quditScientific Reports, 2015
- Demonstration of quantum permutation algorithm with a single photon ququartScientific Reports, 2015
- Determining the parity of a permutation using an experimental NMR qutritPhysics Letters A, 2014
- Hermitian Young operatorsJournal of Mathematical Physics, 2014
- Advances in quantum metrologyNature Photonics, 2011
- How entangled can two couples get?Physics Letters A, 2000
- The Magma Algebra System I: The User LanguageJournal of Symbolic Computation, 1997
- Linear Representations of Finite Groups1977