5 papers
PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax
William Gay, Fernando Granha Jeronimo, Lenny Liu +3
Pure-state consistency problems naturally lead to quantum proof systems in which a single pure witness must satisfy many acceptance constraints. The corresponding class $\mathsf{Pu…
An Argmax Principle for Sum-of-Squares Relaxations on the Sphere
Fernando Jeronimo Granha, Pei Wu, Haochen Xu
We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of…
Optimal Quantum de Finetti Theorems via Argmax Rounding
Fernando Granha Jeronimo, Pei Wu, Haochen Xu
We prove optimal finite quantum de Finetti upper bounds. Given a bosonic state , there is a probability measure on the unit sphere such t…
Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity
Honghao Fu, Minglong Qin, Haochen Xu +1
Motivated by the limitations of near-term quantum devices, we study nonlocal games in the high-noise regime, where the two players may share arbitrarily many copies of a noisy enta…
The Computational Advantage of MIP* Vanishes in the Presence of Noise
Yangjing Dong, Honghao Fu, Anand Natarajan +3
Quantum multiprover interactive proof systems with entanglement MIP* are much more powerful than its classical counterpart MIP (Babai et al. '91, Ji et al. '20): while MIP = NEXP,…