From the 1 of 11 linked papers with an AI index.
11 papers
Trotter error compensation with polylogarithmic precision and nested-commutator scaling without ancillas
Xinzhao Wang, Shuo Zhou, Ziruo Wang +5
The paper introduces a high‑order nested‑commutator compensation (HNCC) algorithm that reduces the circuit size needed for Hamiltonian simulation to polylogarithmic dependence on p…
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…
High-precision and low-depth quantum algorithm design for eigenstate problems
Jinzhao Sun, Pei Zeng, Tom Gur +1
Estimating the eigenstate properties of quantum systems is a long-standing, challenging problem for both classical and quantum computing. Existing universal quantum algorithms typi…
3-Query RLDCs are Strictly Stronger than 3-Query LDCs
Tom Gur, Dor Minzer, Guy Weissenberg +1
We construct -query relaxed locally decodable codes (RLDCs) with constant alphabet size and length for -bit messages. Combined with the lower bound of $\tild…
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
Guy Goldberg, Tom Gur, Sidhant Saraogi
We show a nearly optimal lower bound on the length of linear relaxed locally decodable codes (RLDCs). Specifically, we prove that any -query linear RLDC $C\colon \{0,1\}^k \to \…