Efficient Simulation of the Deutsch-Jozsa Algorithm

Abstract: We provide a framework wherein one can simulate the Deutsch-Jozsa quantum algorithm on a regular computer within polynomial time, and with linear memory consumption. Under certain reasonable assumptions the simulation solves the problem with a bounded error of probability with only one function evaluation, which is comparable with the efficiency of the quantum algorithm. The provided framework lies within a slight extension of the toy model purposed by Robert W. Spekkens Phys. Rev. A 75 (2007), and consists of transformations that are reminiscent of transformations in quantum mechanics.