New pre-print: “Sample-Based Quantum Diagonalization with Amplitude Amplification”
Recently, sample-based quantum diagonalization (SQD) has emerged as one of the most promising approaches to solve the electronic structure problem on current quantum computers. This method classically diagonalizes a Hamiltonian in a subspace that is spanned by samples obtained from a quantum computer. However, SQD suffers by construction from a fundamental sampling problem, as some basis states that are required for a targeted accuracy may only be sampled extremely rarely. To alleviate this limitation, we introduce the new SQD-AA algorithm that combines SQD with amplitude amplification (AA). SQD-AA uses AA to sequentially reduce probabilities of already measured bitstrings, thus making the observation of new ones more likely.
In this new preprint by Nina Stockinger, Ludwig Nützel, and Michael J. Hartmann, we show that the total runtime of SQD-AA is orders of magnitude lower than vanilla SQD, and we consider SQD-AA in an early fault-tolerant scenario. We show that there is a significant regime where SQD-AA is more efficient than phase estimation methods. Therefore, it is likely that SQD methods remain viable even beyond the NISQ era on the way to fault-tolerance.