The theory of quantum computation has brought us rapid technological developments, together with remarkable improvements in how we understand quantum theory. I will describe the foundations of a programme to extend the quantum theory of computation beyond quantum theory itself, based on the recently proposed constructor theory. I will then explain a recent application of this new approach to the problem of witnessing non-classicality in gravity.