4 citations · 17 across the 23 of their papers we have counts for
34 papers
The power of time reversal in Hamiltonian property testing
Richard R. Allen, Matthias C. Caro, Yanlin Chen +2
Quantum algorithms enable Heisenberg-limited scaling across many tasks in sensing and learning, achieving precision using total evolution time. How…
Quantum Encodings, Private Messages, and Communication Complexity
Tom Gur, Miryam Mi-Ying Huang, Er-Cheng Tang
We study the complexity of quantum decomposable randomized encodings (QDRE). We establish a bi-directional connection between the QDRE model and the communication complexity model…
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
Tom Gur, Longcheng Li
We show that one-way one-round quantum-LOCAL algorithms cannot -color directed cycles with high probability. This is the first lower bound in the high-probability quantum LOCAL…
Trotter error compensation with polylogarithmic precision and nested-commutator scaling without ancillas
Xinzhao Wang, Shuo Zhou, Ziruo Wang +5
Product formulas are among the most practical approaches to Hamiltonian simulation, requiring no ancillary qubits and exhibiting error bounds governed by nested commutators rather…
An algorithmic Polynomial Freiman-Ruzsa theorem
Davi Castro-Silva, Jop Briët, Srinivasan Arunachalam +2
We provide algorithmic versions of the Polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Ann. of Math., 2025). In particular, we give a polynomial-time algorithm…
Pseudo-deterministic Quantum Algorithms
Hugo Aaronson, Tom Gur, Jiawei Li
We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focu…