Quantum Advantage in Identifying the Parity of Permutations with Certainty

Abstract

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.

6+16 pages. Comments are welcome!

References in corpus (27)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Advances in Quantum Metrology
• Quantum Coherence as a Resource
• Quantum fingerprinting
• Geometric measure of entanglement and applications to bipartite and multipartite quantum states
• Non-locality and Communication Complexity
• Quantum advantage in learning from experiments
• A complete family of separability criteria
• Experimental Observation of Four-Photon Entangled Dicke State with High Fidelity
• How entangled can two couples get?
• A Limit on the Speed of Quantum Computation in Determining Parity
• Operational Families of Entanglement Classes for Symmetric $N$-Qubit States
• Quantum Random Access Codes using Single $d$-level Systems
• Computational speed-up in a single qudit NMR quantum information processor
• Computational speed-up with a single qudit
• The power of symmetric extensions for entanglement detection
• Quantum contextuality provides communication complexity advantage
• Determining the parity of a permutation using an experimental NMR qutrit
• Generalized Geometric Measure of Entanglement for Multiparty Mixed States
• Entanglement and coherence in Bernstein-Vazirani algorithm
• Implementation of a Deutsch-like quantum algorithm utilizing entanglement at the two-qubit level, on an NMR quantum information processor
• Hermitian Young Operators
• Dynamical Decomposition of Bilinear Control Systems subject to Symmetries
• Demonstration of quantum permutation algorithm with a single photon ququart
• Extended Quantum Color Coding
• Quantifying entanglement from the geometric perspective
• Finding maximal quantum resources