A Quantum Unique Games Conjecture
<|reference_start|>A Quantum Unique Games Conjecture: After the NP-hardness of computational problems such as 3SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum extensions of some of these problems are known to be hard-indeed undecidable-their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.<|reference_end|>
@article{mousavi2024a,
    title={A Quantum Unique Games Conjecture},
    author={Hamoon Mousavi, Taro Spirig},
    journal={arXiv preprint arXiv:2409.20028},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.20028},
    primaryClass={quant-ph cs.CC}
}