Joint Seminar on Quantum Information and Technologies

A surprising and non-intuitive feature of the universe is that there appear to be exactly two possible types of computer (up to polynomial equivalence) - classical and quantum computers. While quantum computers are widely expected to be faster than classical computers at certain tasks, for now classical computers are dramatically more reliable, more powerful and more available than their quantum counterparts. This motivates us to use classical computers to simulate quantum computers. In addition to being of obvious practical use, classical simulations of quantum computations have interesting theoretical implications. Intuitively those computations which may be efficiently simulated by a classical computer are somehow "less quantum" while those which are prohibitively expensive to simulate classically are "more quantum". I will discuss some ways of quantifying non-classicality in the form of "magic" resources, as well as some classical simulation algorithms whose run-times are determined by the amount of magic in the quantum computation being simulated.