7 papers
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…
An Optimal Analysis of the Product Test
Jacob Beckey, Fernando Granha Jeronimo, Pei Wu
Product testing, i.e., deciding whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition, serves as a bridge between quantum property…
The power of unentanglement without destructive interference
Yupan Liu, Pei Wu
Stoquasticity, originating in sign-problem-free physical systems, gives rise to , introduced by Bravyi, Bessen, and Terhal (2006), a quantum-inspired intermediate class…
Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
Amin Shiraz Gilani, Daochen Wang, Pei Wu +1
The edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of th…
Coherence in Property Testing: Quantum-Classical Collapses and Separations
Fernando Granha Jeronimo, Nir Magrafta, Joseph Slote +1
Understanding the power and limitations of classical and quantum information and how they differ is a fundamental endeavor. In property testing of distributions, a tester is given…