William Kirby, Bibek Pokharel, Javier Robledo Moreno, Kevin C. Smith, Sergey Bravyi, Abhinav Deshpande, Constantinos Evangelinos, Bryce Fuller, James R. Garrison, Ben Jaderberg, Caleb Johnson, Petar Jurcevic, Su-un Lee, Simon Martiel, Mario Motta, Seetharami Seelam, Oles Shtanko, Kevin J. Sung, Minh Tran, Vinay Tripathi, Kazuhiro Seki, Kazuya Shinjo, Han Xu, Lukas Broers, Tomonori Shirakawa, Seiji Yunoki, Kunal Sharma, Antonio Mezzacapo

We experimentally demonstrate that a hybrid quantum-classical algorithm can outperform purely classical, off-the-shelf selected configuration interaction methods. First, we construct a class of local Hamiltonian problems with sparse ground states, and show that representative classical heuristics fail to find the ground state of a specific 49-qubit instance. Next, we show that the sample-based Krylov quantum diagonalization algorithm, run on an IBM Heron R3 processor, succeeds at the same task. This algorithm uses quantum samples from a grid of time-evolved quantum states, and offers provable convergence guarantees for sparse ground state problems with guiding states. While the problem is also solvable classically using two iterative solvers that we designed specifically to target our Hamiltonian construction, this work resolves the previously open question of whether a sample-based quantum diagonalization algorithm can outperform standard selected configuration interaction heuristics.