What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?

Question

My intuition is that the fastest classical algorithm for simulating some kind of noiseless quantum sampling process should scale roughly with the dimension of the Hilbert space: you would need to process each amplitude at least once in order to calculate a generic matrix element.

For random (noiseless) circuit sampling, this is indeed true: the fastest classical simulation algorithm, the Schrodinger algorithm, scales as $m|\mathcal{H}|$, where $m$ is the number of gates and $|\mathcal{H}| = 2^n$ (where $n$ is the number of qubits) is the dimension of the Hilbert space.

But for exact boson sampling, these two quantities seems strangely unrelated to each other, and either can be much larger than the other. The Wikipedia article on boson sampling says that for $n$ identical photons distributed across $m$ modes, the dimension of the Hilbert space is $\binom{n+m-1}{n} = \binom{n+m-1}{m-1}$, but the fastest known classical algorithm has runtime $O(n\, 2^n + m n^2)$. (Note that unfortunately, the Wikipedia article switches its definitions of $M$ and $N$ between different sections.)

1. In the regime where $m \approx n \gg 1$, which is the case in the most advanced boson sampling experiments, we get that the Hilbert space dimension is $~4^n/\sqrt{n}$ and the runtime is $O(n\, 2^n)$, so the runtime only scales as the square root of the Hilbert space dimension.
2. In the regime where $n \gg m$, the Hilbert space dimension is $(n/m)^m$ (times subleading corrections) but the runtime is still $O(n\, 2^n)$, so for a fixed number of modes $m$ the runtime is exponentially longer than the Hilbert space dimension (which only scales polynomially in the number of photons).
3. In the regime where $m$ is exponentially larger than $n$, the Hilbert space dimension is $(m/n)^n$ (times subleading corrections), and if hold $n$ fixed then the runtime is $O(m)$, so the runtime scales as the $n$th root of the Hilbert space dimension.

This all seems very weird to me. Why does the runtime only scale as a root of the Hilbert space size in certain regimes, but is exponentially longer than the Hilbert space size in other regimes? This seems both more complicated and less intuitive than in the case of random circuit simulations, where the two quantities are directly proportional as I'd intuitively expect.

Answer 1

"What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?"

You are correct that for $n$ output photons and $m$ modes, the size of the Hilbert space is:

$$ n + m -1 \choose n \tag{1} $$

and that the best currently known classical algorithm for exactly simulating the boson sampling has asymptotic time cost:

$$\tag{2} \mathcal{O}\left(n 2^m + mn^2 \right). $$

Every other conclusion you drew is a mathematical consequence of Eqs. 1 and 2.

Are these runtime results for various regimes of $m$ and $n$, remarkable? Certainly. The original paper in which the algorithm was first introduced with runtime given by Eq. 2, noted this early in the paper:

"A particularly attractive property of the running time we give is that the exponentially growing term depends only on $n$, the size of the multisets we wish to sample, and not $m$ which is potentially much larger."

Is there a catch? Yes. The authors mentioned the following about the "naive" algorithm, which costs much more:

"The space usage of such a naive approach can be reduced to the storage needed for the required sample size"

whereas for the algorithm with lower time cost, there's an additional space cost of $\mathcal{O}(m)$. This is a classic case where if you do have enough RAM to store the required data, you can experience enormous speed-ups in the runtime, and this speed-up can even be exponential: try to write an algorithm that finds the number of times that a string of length $s$ appears in a file and you will see that the cost will be $\mathcal{O}(a^s)$ for an alphabet with $a$ letters, and exponentially smaller if you store information about the length-2 substrings to help you find the length-3 substrings, and so on for larger $s$).