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.
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: