12 papers
Time-Dependent Hamiltonian Simulation with Optimal Query Complexity
Boyang Chen, Minbo Gao, Xinzhao Wang +1
We give a query-optimal algorithm for simulating a general -qubit time-dependent Hamiltonian on , assuming that is Lipschitz continuous and . In…
Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding
Tongyang Li, Fengning Ou, Xinzhao Wang +3
The paper analyzes the T‑gate cost of sparse quantum read‑only memory (QROM) and derives asymptotically optimal bounds, applying the results to sparse state preparation and block e…
Quantum-classical crossover in fault-tolerant quantum dynamics simulation
Jinzhao Sun, Bozhen Zhou, Jue Xu +28
While quantum computers promise to solve classically intractable problems, identifying the point at which fault-tolerant quantum computation outperforms the best classical algorith…
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…
Quantum Multi-Level Estimation of Functionals of Discrete Distributions
Kean Chen, Minbo Gao, Tongyang Li +2
We propose a quantum multi-level estimation framework for a functional of a discrete distribution . We partition the values into logarith…
DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
Zhengfeng Ji, Tongyang Li, Changpeng Shao +2
We study the computational complexity of estimating the normalized trace for a log-local Hamiltonian acting on qubits. This problem arises naturally in the…