Solving the quantum simulation problem via signal analysis

The computation of scattering amplitudes soon becomes an intractable problem for a classical computer as the size of the quantum system and the evolution time grows. Nevertheless, this problem is in the class BQP, where a quantum computer can offer an efficient solution in time polynomial in both the system size and evolution time. The currently available quantum devices (NISQ) have enough qubits to represent challenging instances of this problem. However, because of errors, they can not run the simulations for long times. Our research frames the quantum simulation problem as a signal analysis one to combine NISQ devices' power and classical computation. The goal is to devise an algorithm that can forecast the expectation values at longer times with bounded error, given the outcome of short-time simulations. Using a Matrix Pencil approach, we conduct numerical experiments that suggest that the predictions can be accurate under certain conditions. At the same time, we are aware of adversarial problem instances that can make the prediction hard.