Quantum Advantage in Identifying the Parity of Permutations with Certainty
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917210716372992 |
|---|---|
| author | Diebra, Arnau Llorens, Santiago González-Lociga, David Rico, Albert Calsamiglia, John Hillery, Mark Bagan, Emili |
| author_facet | Diebra, Arnau Llorens, Santiago González-Lociga, David Rico, Albert Calsamiglia, John Hillery, Mark Bagan, Emili |
| contents | We establish a sharp quantum advantage in determining the parity (even/odd) of an unknown permutation applied to any number $n \ge 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 $\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$, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_04310 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum Advantage in Identifying the Parity of Permutations with Certainty Diebra, Arnau Llorens, Santiago González-Lociga, David Rico, Albert Calsamiglia, John Hillery, Mark Bagan, Emili Quantum Physics We establish a sharp quantum advantage in determining the parity (even/odd) of an unknown permutation applied to any number $n \ge 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 $\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$, 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. |
| title | Quantum Advantage in Identifying the Parity of Permutations with Certainty |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2508.04310 |