  This work shows that the majorization of photon distributions is related to
the runtime of classically simulating multimode passive linear optics, which
explains one aspect of the boson sampling hardness. A Shur-concave quantity
which we name the \emph{Boltzmann entropy of elementary quantum complexity}
($S_B^q$) is introduced to present some quantitative analysis of the relation
between the majorization and the classical runtime for simulating linear
optics. We compare $S_B^q$ with two quantities that are important criteria for
understanding the computational cost of the photon scattering process,
$\mathcal{T}$ (the runtime for the classical simulation of linear optics) and
$\mathcal{E}$ (the additive error bound for an approximated amplitude
estimator). First, for all the known algorithms for computing the permanents of
matrices with repeated rows and columns, the runtime $\mathcal{T}$ becomes
shorter as the input and output distribution vectors are more majorized.
Second, the error bound $\mathcal{E}$ decreases as the majorization difference
of input and output states increases. We expect that our current results would
help in understanding the feature of linear optical networks from the
perspective of quantum computation.
