# Quantum version of the Galton Board

+ 5 like - 0 dislike
1274 views

If classical particles fall through a Galton Board they pile up in the limit of large numbers like a normal distribution, see e.g. http://mathworld.wolfram.com/GaltonBoard.html What kind of distribution would one see, if the particles would obey the laws of quantum mechanics (as a thought experiment) ? Wouldn't interference effects lead to a different distribution than the normal distribution?

This post imported from StackExchange Physics at 2014-07-24 15:42 (UCT), posted by SE-user asmaier
retagged Jul 24, 2014
More on a Galton box: physics.stackexchange.com/search?q=is%3Aq+galton

This post imported from StackExchange Physics at 2014-07-24 15:42 (UCT), posted by SE-user Qmechanic

+ 6 like - 0 dislike

You might like this 110-page paper by me and Alex Arkhipov, which is all about a quantum bosonic analogue of Galton's board (we even use the same graphic you did -- see Section 1.1!). In particular, we gave strong evidence that such a board (with an arbitrary configuration of "pegs," and with multiple entry points for the "balls") is exponentially hard even to simulate using a classical computer. This suggests that such a quantum Galton's board (which is now called a "BosonSampler") could be used as a rudimentary, proof-of-principle quantum computer. And indeed, within the last year the first BosonSampling experiments were done in linear optics (see here), although so far only with 3 photons.

To make our argument for computational hardness work, we needed two crucial assumptions:

(1) The "balls" have to be indistinguishable particles. If they're distinguishable, then the distribution for any one individual ball could still exhibit interference fringes. But once you knew the probability distribution for one ball, the distribution for n balls would just be obtained by sampling from that distribution n times independently -- thereby producing "conventional, classical" Law of Large Numbers behavior. By contrast, identical quantum particles can famously become "correlated" even if they've never explicitly interacted, as seen for example in the Hong-Ou-Mandel dip.

(2) The "balls" have to be bosons. In that case, their transition amplitudes are given by nxn matrix permanents, the calculation of which is a famous hard problem in computer science. By contrast, if the balls are fermions, then their transition amplitudes are given by nxn determinants, which are easy to calculate classically.

Of course, there's also a "narrower" way to interpret your question, which might be closer to what you were actually asking about! Namely, rather than an "arbitrary" Galton-like board, we could consider the specific geometry from the figure: so let's say, a network of 50/50 interferometers arranged in a diamond pattern in the plane, with a single source of particles at the top. And we could then calculate (or, if we're lazier, numerically simulate...) the particular probability distribution over n-particle outcomes that that configuration leads to, under two different assumptions:

(1) That the particles are distinguishable. (In this case, of course, the problem reduces to working out the distribution for a single particle.)

(2) That the particles are indistinguishable bosons.

(Note that a third case, that the particles are indistinguishable fermions, never arises -- for by the Pauli exclusion principle, n identical fermions couldn't even "fit" simultaneously through the single source at the top.)

If I have some time later, I might work out the answers and post them here -- but in the meantime, anyone else should feel free to do so first.

Addendum: OK, so let's consider the case of a single quantum particle passing through a "diamond-shaped" network of 50/50 interferometers. In that case, the probability distribution after n steps will be determined, not by the nth row of Pascal's triangle (as in the classical case), but by the nth row of what we might call the "interferometric Pascal's triangle." The latter is defined as follows: let A(i,j) be the jth entry in row i. Then:

A(0,0)=1

A(0,j)=0 for all j≠0

For i+j positive and odd: A(i,j)=A(i-1,j)+A(i-1,j+1)

For i+j positive and even: A(i,j)=A(i-1,j-1)-A(i-1,j)

I'm almost certain that the result will asymptotically approximate the standard behavior for the "quantum random walk on the line": see here or here for good overviews. In particular, the distribution will not look anything like the Gaussian one: instead it should be nearly uniform, except with a bunch of oscillating peaks near the two edges, with the size of the peaks getting damped as you move closer to the center. (See the linked papers for example images.)

A slight caveat is that usual analyses of quantum random walks assume there's a "coin" (i.e., a spin-1/2 internal degree of freedom), whereas I've used a staggered arrangement of interferometers to remove the need for the coin. I don't think that affects the walk's qualitative behavior, but I don't have a proof.

This post imported from StackExchange Physics at 2014-07-24 15:42 (UCT), posted by SE-user Scott Aaronson
answered Nov 1, 2013 by (795 points)
Thank you! Your last reference also led me to this article in Wikipedia with a picture of the distribution: en.wikipedia.org/wiki/Quantum_walk . However, is it true that neither for the fermion nor for the boson case the resulting distribution can be expressed in closed form?

This post imported from StackExchange Physics at 2014-07-24 15:42 (UCT), posted by SE-user asmaier
Well, I think you can at least get a pretty good approximation in closed form, if you're willing to count special functions as "closed form."

This post imported from StackExchange Physics at 2014-07-24 15:42 (UCT), posted by SE-user Scott Aaronson

 Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead. To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL. Please consult the FAQ for as to how to format your post. This is the answer box; if you want to write a comment instead, please use the 'add comment' button. Live preview (may slow down editor)   Preview Your name to display (optional): Email me at this address if my answer is selected or commented on: Privacy: Your email address will only be used for sending these notifications. Anti-spam verification: If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:p$\hbar$ysics$\varnothing$verflowThen drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds). To avoid this verification in future, please log in or register.