Skip to content
Preprint

Unconditional quantum advantage from a two-round CHSH problem in one dimension

Sep 2026 · 0 citations · 24 references
Physics

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\leq\delta<(\sqrt{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+\sqrt{2})/4-\delta$ requires depth $\Omega(\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.

View source

Similar papers

Preprint Oct 2026

Optimal and Verifiable Quantum Advantages in Communication Complexity

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $\Omega(2^n)$ bits of communication. We...

Ryan Anselm, Michelle Ding, D. Gilboa et al. · 1 citation
Preprint Oct 2026

From Steane to A7: Quantum Codes from Invariant States

We construct a two-parameter family of single-error-correcting seven-ququart codes with transversal $\tilde{A_7}$ symmetry, realizing the finite component of a two-qubit super-golden gate set. These $((7,4,3))_4$ codes encode two logical qubits and support non-Clifford operations by applying the same gate to each physi...

Ian Teixeira · 0 citations
Sep 2026

Exponential Quantum Advantage in Number-on-Forehead Communication

We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Pro...

Hao-Yu Wang, Pei Wu, Guang-Xu Yang · 1 citation
Sep 2026

Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT

The upper and lower bounds establish a fine-grained complexity dichotomy for quantum satisfiability, by showing that, assuming (Q)SETH, quantum 5-SAT admits no non-trivial worst-case speedup and demonstrating that the dependence of the authors' algorithms on regularity is in some sense nearly optimal.

Atsuya Hasegawa, Jonas Kamminga, François Le Gall et al. · 0 citations
Preprint Sep 2026

All Unitaries Have Constant Depth Quantum Circuits

It is well-known that every $n$-qubit unitary can be implemented by a $2^{O(n)}$-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that al...

Barak Nehoran, Joseph Slote, Henry S. Yuen · 5 citations · ⚡1
Preprint Oct 2026

Collective Quantum State Preparation Is Nonadditive

Quantum state preparation is a basic primitive of quantum computation and control, but its resource cost is usually analyzed for one target state or under an independent-copy construction. Here we study the many-copy problem under weighted Pauli control, where a Pauli-product rotation $e^{i\phi P}$ is charged by its ro...

Lin Zhu, Ranyiliu Chen, Xin Wang et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.