It is my understanding that probabilistic classical computing can be simulated efficiently (using same order of steps) as quantum computing. However, is anything known about the existence of problems where classical deterministic computation can be performed more efficiently (say many fewer steps and at least similar memory resources)? I am not necessarily interested in "practical" problems, nor am I asking about "realistic" quantum computers. My question is more about theory.
Thank you.
