qSHIFT: An Adaptive Sampling Protocol for Higher-Order Quantum Simulation

Abstract

Early fault-tolerant quantum computers are expected to support reliable but depth-limited quantum circuits, while classical computational resources remain available. These conditions have motivated hybrid coherent algorithms which use quantum simulation as a central algorithmic primitive. This trend calls for quantum-simulation methods that operate with shallow circuits and admit systematic improvements in gate-complexity scaling. Here, we introduce qSHIFT, an adaptive sampling protocol for simulating a Hamiltonian $H={\sum }_{i=1}^L{h}_i{H}_i$. qSHIFT achieves gate complexity ${\mathcal{O}}_r\left((\lambda t{)}^{1+1/r}/{\epsilon }^{1/r}\right)$, where $r$ is an algorithmic parameter, $\lambda ={\sum }_i|h_i|$ and $\epsilon$ denotes the target precision. Relative to qDRIFT, increasing $r$ systematically improves the gate complexity for a given target precision without incurring extra quantum cost. Unlike Trotterization, the number of sampled gates is nominally independent of $L$. qSHIFT retains the elementary gate set of qDRIFT and, unlike qSWIFT, requires neither ancillary qubits nor controlled operations. The improved gate complexity scaling is obtained at the cost of a classical calculation involving $L^r$ coefficients at each adaptive sampling round.

arXiv comment9+18 pages, 3 figures