2 citations · 2 across the 7 of their papers we have counts for
12 papers
Exponential Quantum Advantage in Numbers-on-Forehead Communication
Haoyu Wang, Pei Wu, Guangxu Yang
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 re…
Efficient Randomized Communication Without Large Monochromatic Rectangles
Haoyu Wang, Pei Wu
In this paper, we construct a total Boolean function with randomized communication protocol, while any monochromatic rectangle has density at most $O(2^{-\m…
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…
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…
Quantum Merlin-Arthur with an internally separable proof
Roozbeh Bassirian, Bill Fefferman, Itai Leigh +2
We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP NEXP. This gives a new route to prove…
Dimension Independent Disentanglers from Unentanglement and Applications
Fernando G. Jeronimo, Pei Wu
Quantum entanglement is a key enabling ingredient in diverse applications. However, the presence of unwanted adversarial entanglement also poses challenges in many applications. In…
Pseudorandom and Pseudoentangled States from Subset States
Fernando Granha Jeronimo, Nir Magrafta, Pei Wu
Pseudorandom states (PRS) are an important primitive in quantum cryptography. In this paper, we show that subset states can be used to construct PRSs. A subset state with respect t…