Abstract: Quantum walks have been shown to capture what is necessary for universal quantum computing, even though they are very simple models. This advantage makes it easier to understand its complexity under different perspectives. While it is currently unknown whether quantum computing is indeed superior than classical computing, it is an interesting question to ask whether some intermediate physical system can be proven to be classically hard to simulate.