A new theoretical framework has been developed to identify computations that occupy the ‘quantum frontier’ – the boundary at which problems become impossible for today’s computers and can only be solved by a quantum computer. The team demonstrates that these computations can be performed with near-term, intermediate, quantum computers.