Near term quantum devices: complexity, verification and applications – NISQ-TCS

In the past decade, we have seen constant progress in the development of quantum technologies, which are outstanding outcomes in engineering and experimental physics despite not allowing us to perform universal fault-tolerant quantum computation. Given their limited size and the fact that they are not fault-tolerant, they have been called noisy intermediate-scale quantum (NISQ) devices, and they play a fundamental role in exposing the computational advantage of quantum devices in practice.

From a theoretical perspective, NISQ devices reinforce the importance of several questions: Which non-universal models of quantum computation enable quantum speedups? Up to which point can their implementation be classically simulated? Can we find practical applications for them?...

Our goal in this project is to study NISQ devices from the formal perspective of theoretical computer science, bridging the gap between the exciting experiments for quantum superiority and our understanding of them.