How can we test a quantum computer? An exploration of some of the theoretical puzzles of this field and how we can investigate them with experimental physics. What is the relationship between quantum physics, computer science and complexity theory? In this talk, Dr Jelmer Renema will introduce a conceptual problem that sits at the intersection between these fields, namely: how can we show that a quantum computer can outperform an ordinary computer?