Key points are not available for this paper at this time.
Estimating the eigenstate properties of quantum many-body systems is a long-standing, challenging problem for both classical and quantum computing. For the task of eigenstate preparation, quantum signal processing (QSP) has established near-optimal query complexity O (^-1 (^-1) ) by querying the block encoding of the Hamiltonian H where is the energy gap and is the target precision. However, QSP is challenging for both near-term noisy quantum computers and early fault-tolerant quantum computers (FTQC), which are limited by the number of logical qubits and circuit depth. To date, early FTQC algorithms have focused on querying the perfect time evolution e^-iHt. It remains uncertain whether early FTQC algorithms can maintain good asymptotic scaling at the gate level. Moreover, when considering qubit connectivity, the circuit depth of existing FTQC algorithms may scale suboptimally with system size. Here, we present a full-stack design of a random sampling algorithm for estimating the eigenenergy and the observable expectations on the eigenstates, which can achieve high precision and good system size scaling. The gate complexity has a logarithmic dependence on precision O (^1+o (1) (1/) ) for generic Hamiltonians, which cannot achieved by methods using Trottersiation to realise e^-iHt like in QETU. For n-qubit lattice Hamiltonians, our method achieves near-optimal system size dependence with the gate complexity O (n^1+o (1) ). When restricting the qubit connectivity to a linear nearest-neighbour architecture, The method shows advantages in circuit depth, with O (n^o (1) ) for lattice models and O (n^2+o (1) ) for electronic structure problems. We compare the resource requirements (CNOT gates, T gates and qubit numbers) by phase estimation, QSP, and QETU, in lattice and molecular problems.
Sun et al. (Thu,) studied this question.