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
Q&A (4870)
