# How big is the Hilbert space of a boson sampling experiment?

Boson sampling experiments are typically characterized by two key parameters: the number of photons $$M$$ and the number of modes $$N$$.

A recent experimental demonstration (arXiv:2106.15534) with $$M = 113$$ and $$N = 144$$ says that the Hilbert space dimension is $$10^{43}$$. This is approximately $$2^N$$, so I assume that's where they got that number (although I could well be wrong). But the Wikipedia page on boson sampling says that

simple counting arguments show that the size of the Hilbert space corresponding to a system of $$M$$ indistinguishable photons distributed among $$N$$ modes is given by the binomial coefficient $$\binom{M+N-1}{M}$$.

For $$M = 113,\ N = 144$$ this expression gives $$10^{75}$$, not $$10^{43}$$. Why is the paper reporting such a smaller Hilbert space than the Wikipedia article's counting argument would imply?

• I'm not too familiar with it so I'm not sure, but note that they are talking about Gaussian boson sampling, which doesn't work in exactly the same way as the standard one, afaik. This might explain the stated difference
– glS
Dec 31, 2021 at 10:30
• arxiv.org/abs/2110.06964 (The Complexity of Bipartite Gaussian Boson Sampling) might be relevant Jan 4, 2022 at 23:14

It was frustrating to read that Wikipedia page. Rather than explaining every single problem with it, I'll only mention the top three problems in the single paragraph that you quoted (if there's this many problems with one paragraph, you can imagine how many can be listed across the rest of the article spanning several dozen paragraphs):

• You already noticed that the article switches $$N$$ and $$M$$.
• They then talk about $$W$$ without ever defining it explicitly.
• They don't cite references, and therefore even if it is indeed a "simple" counting argument that leads to their Hilbert space formula, anyone who does not know much about quantum photonics (specifically, how to determine the size of the Hilbert space in this situation) will simply have to take that formula for granted.

However, at least the formula they gave for the Hilbert space does happen to be correct, even if they didn't explain why and didn't cite a reference (I thought citations were a requirement in order to put things in Wikipedia?). This paper published as an "Editor's Suggestion" in Physical Review Letters fortunately does give the formula for the Hilbert space (all you have to do is search for the string "Hilbert space"), and it's the same as in Wikipedia. So even if you still know zero about quantum optics, at least you're no longer worried that there's no published citation that backs up the claim.

If the Hilbert space were to be $$2^N$$, then the complexity would be precisely the same no matter the size of $$M$$, so the Hilbert space does need to depend on both $$N$$ and $$M$$.

Furthermore, you can see in the above-mentioned paper published in PRL, that the abstract mentions a Hilbert space of $$10^{14}$$ which is (now that their $$n$$ is our $$M$$ and vice versa):

• not $$2^N = 2^{60} \approx 1.15 \times 10^{18}$$, and
• not $${M+N-1 \choose M} = {79 \choose 20} \approx 2.65 \times 10^{18}.$$

Instead, the $$10^{14}$$ that they state, comes from $${M^\prime+N-1 \choose M^\prime} \approx 3.697 \times 10^{14}$$ where $$M^\prime=14$$ instead of 20, because there's only 14 outputs, despite their being 20 input photons.

This is sometimes called the "output Hilbert space" which can be smaller than the Hilbert space of the actual physical wavefunction.

• If you need me to, I can explain more tomorrow at around this time. It's 1:15am here in Waterloo, and my wife is waiting, but the last two sentences should help, and since you put two bounties on two similar questions at the same time, I thought this might be urgent for you so I wrote up what I could, in the amount of time that I had available. Jan 8, 2022 at 6:17
• Okay, but in the article that I linked to in my question, they say that the output click number is 113, not the number of input photons. So where are they getting $10^{43}$ from? Jan 8, 2022 at 16:57
• The Hilbert space size in my answer, specifically the one using $M^\prime$ instead of $M$ is a correct answer to "How big is the Hilbert space of a boson sampling experiment?". As for the specific Hilbert space described in the paper, it might be the Hilbert space of the $N\times N$ unitary operator in the same Wikipedia paragraph to which we both referred. Perhaps a question with title "Which Hilbert space is being reported to be 10^43 in the 2021 boson sampling paper of Zhong et al." would attract users who are willing to open the paper. My interest in b-sampling diminished over the years. Jan 9, 2022 at 1:19
• Doesn’t “the Hilbert space of the $N \times N$ unitary operator” have dimension $N$, not $2^N$? Jan 9, 2022 at 2:51
• Good point, I thought a $2^N \times 2^N$ could come from there, but really I think the question: "Which Hilbert space is being reported to be 10^43 in the 2021 boson sampling paper of Zhong et al." ought to be asked, because this more general question of "what the is the Hilbert space" has an answer which is just $N + M -1 \choose M$. Also, you seem to be quite interested in boson sampling, but I don't think it can be used to do any valuable calculation, not even the permanents of a matrix. Jan 9, 2022 at 3:04