• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


PO is now at the Physics Department of Bielefeld University!

New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,054 questions , 2,207 unanswered
5,345 answers , 22,721 comments
1,470 users with positive rep
818 active unimported users
More ...

  Quantum version of the Galton Board

+ 5 like - 0 dislike

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

Galton Board

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
asked Nov 1, 2013 in Theoretical Physics by asmaier (25 points) [ no revision ]
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

1 Answer

+ 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,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 ScottAaronson (795 points) [ no revision ]
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

Your answer

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):
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:
Then 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).
Please complete the anti-spam verification

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights