Multi-level quantum signal processing with applications to ground state preparation using fast-forwarded Hamiltonian evolution

The preparation of the ground state of a Hamiltonian H with a large spectral radius has applications in many areas such as electronic structure theory and quantum field theory. Given an initial state with a constant overlap with the ground state, and assuming that the Hamiltonian H can be efficiently simulated with an ideal fast-forwarding protocol, we first demonstrate that employing a linear combination of unitaries (LCU) approach can prepare the ground state at a cost of O(log²(\|H\| Δ⁻¹)) queries to controlled Hamiltonian evolution. Here $\|H\|$ is the spectral radius of H and Δ the spectral gap. However, traditional Quantum Signal Processing (QSP)-based methods fail to capitalize on this efficient protocol, and its cost scales as O(\|H\| Δ⁻¹). To bridge this gap, we develop a multi-level QSP-based algorithm that exploits the fast-forwarding feature. This novel algorithm not only matches the efficiency of the LCU approach when an ideal fast-forwarding protocol is available, but also exceeds it with a reduced cost that scales as O(log(\|H\| Δ⁻¹)). Additionally, our multi-level QSP method requires only O(log(\|H\| Δ⁻¹)) coefficients for implementing single qubit rotations. This eliminates the need for constructing the PREPARE oracle in LCU, which prepares a state encoding O(\|H\| Δ⁻¹) coefficients regardless of whether the Hamiltonian can be fast-forwarded.