Unconditional quantum advantage from a two-round CHSH problem in one dimension
Abstract
We introduce a relation problem constructed from the Clauser--Horne--Shimony--Holt (CHSH) game, which we call the two-round one-dimensional CHSH problem. Its two-round structure ensures that the CHSH questions are supplied only after the relevant Pauli-frame data have been fixed, thereby ruling out a simple classical strategy that solves the corresponding problem perfectly when all inputs are supplied simultaneously. We construct a quantum circuit on 2N qubits that uses only adjacent two-qubit gates, has operational depth at most eight, and achieves the optimal quantum success probability of CHSH, which is strictly smaller than one. We prove that, for every fixed 0≤δ<(√2−1)/4, any randomized classical circuit with fixed wiring and bounded gate fan-in that achieves an average success probability of at least (2+√2)/4−δ requires depth Ω(log N) after the questions of the second round are supplied. This yields an unconditional separation even though the quantum circuit is restricted to a one-dimensional geometry, whereas the classical circuit has no geometric locality restriction. The result shows that perfect quantum success is not necessary for unconditional quantum advantage with shallow circuits.
Related
- Comment on J.Qin et al., Unconditional and Robust Quantum Metrological Advantage beyond N00N States, PRL 130, 070801 (2023) and J.A. H. Nielsen et.al., Deterministic Quantum Phase Estimation beyond N00N States. PRL 130, 123603 (2023)
- Unconditional quantum advantage with noisy planar architectures
- Constant-round quantum advantage in communication complexity for total functions
- Unconditional Quantum PAC Learning Advantage in the Large Error Regime
- Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
BibTeX
@misc{lee2026unconditional,
title = {{Unconditional quantum advantage from a two-round CHSH problem in one dimension}},
author = {Yonghae Lee and Jeonghyeon Shin and Soojoon Lee},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21237},
eprint = {2609.21237},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21237},
}
RIS
TY - UNPB
TI - Unconditional quantum advantage from a two-round CHSH problem in one dimension
AU - Yonghae Lee
AU - Jeonghyeon Shin
AU - Soojoon Lee
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.21237
UR - https://arxiv.org/abs/2609.21237
AB - We introduce a relation problem constructed from the Clauser--Horne--Shimony--Holt (CHSH) game, which we call the two-round one-dimensional CHSH problem. Its two-round structure ensures that the CHSH questions are supplied only after the relevant Pauli-frame data have been fixed, thereby ruling out a simple classical strategy that solves the corresponding problem perfectly when all inputs are supplied simultaneously. We construct a quantum circuit on 2N qubits that uses only adjacent two-qubit gates, has operational depth at most eight, and achieves the optimal quantum success probability of CHSH, which is strictly smaller than one. We prove that, for every fixed 0≤δ<(√2−1)/4, any randomized classical circuit with fixed wiring and bounded gate fan-in that achieves an average success probability of at least (2+√2)/4−δ requires depth Ω(log N) after the questions of the second round are supplied. This yields an unconditional separation even though the quantum circuit is restricted to a one-dimensional geometry, whereas the classical circuit has no geometric locality restriction. The result shows that perfect quantum success is not necessary for unconditional quantum advantage with shallow circuits.
ER -