From the 1 of 11 linked papers with an AI index.
6 papers · 1 filter
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…
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…
Symmetric quantum computation
Davi Castro-Silva, Tom Gur, Sergii Strelchuk
We introduce a systematic study of "symmetric quantum circuits", a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model i…
Quantum Communication Advantage in TFNP
Mika Göös, Tom Gur, Siddhartha Jain +1
We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-w…
Quantum Channel Testing in Average-Case Distance
Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian +2
We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel $\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}…