Quantum-assisted Rendezvous on Graphs: Explicit Algorithms and Quantum Computer Simulations
arXiv:2405.14951 · doi:10.1088/1367-2630/ad78f8
Abstract
We study quantum advantage in one-step rendezvous games on simple graphs analytically, numerically, and using noisy intermediate-scale quantum (NISQ) processors. Our protocols realise the recently discovered [arXiv:2207.14404] optimal bounds for small cycle graphs and cubic graphs. In the case of cycle graphs, we generalise the protocols to arbitrary graph size. The NISQ processor experiments realise the expected quantum advantage with high accuracy for rendezvous on the complete graph K3. In contrast, for the graph 2K4, formed by two disconnected 4-vertex complete graphs, the performance of the NISQ hardware is sub-classical, consistent with the deeper circuit and known qubit decoherence and gate error rates.
Submitted version. Description of changes: Added simulation results for the check-later variant of S=1 (Figs. 5,7,8); expanded discussion of asymmetric strategies (end of Sec. 4); additional acknowledgements; competing interests and data-availability statements
References in corpus (10)
- Quantum entanglement
- Bell nonlocality
- Synthesis of Quantum Logic Circuits
- The European Quantum Technologies Roadmap
- Research on Hidden Variable Theories: a review of recent progresses
- On the Theoretical Gap of Channel Hopping Sequences with Maximum Rendezvous Diversity in the Multichannel Rendezvous Problem
- No graph state is preparable in quantum networks with bipartite sources and no classical communication
- Entangled Rendezvous: A Possible Application of Bell Non-Locality For Mobile Agents on Networks
- Quantum Strategies for Rendezvous and Domination Tasks on Graphs with Mobile Agents
- Using Time to Break Symmetry: Universal Deterministic Anonymous Rendezvous