Universal Statistical Simulator
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
The Quantum Fourier Transform is a famous example in quantum computing for being the first demonstration of a useful algorithm in which a quantum computer is exponentially faster than a classical computer. However when giving an explanation of the speed up, understanding computational complexity of a classical calculation has to be taken on faith. Moreover, the explanation also comes with the caveat that the current classical calculations might be improved. In this paper we present a quantum computer code for a Galton Board Simulator that is exponentially faster than a classical calculation using an example that can be intuitively understood without requiring an understanding of computational complexity. We demonstrate a straight forward implementation on a quantum computer, using only three types of quantum gate, which calculates 2 trajectories using O(n) resources. The circuit presented here also benefits from having a lower depth than previous Quantum Galton Boards, and in addition, we show that it can be extended to a universal statistical simulator which is achieved by removing pegs and altering the left-right ratio for each peg.