A team of researchers from Australia and the UK have developed a new theoretical framework 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. Importantly, they demonstrate that these computations can be performed with near-term, intermediate, quantum computers.