Majorization, Entropy and Computational Complexity of Linear Optics
Seungbeom Chin, Joonsuk Huh · arXiv (Cornell University) · 2017
One of the most important problems in linear optics quantum computing is to find the origin of its computational complexity. This work shows that the majorization of photon distributions is one of the crucial factors that affect the complexity of multimode passive linear optics, which explains one aspect of the boson sampling hardness. As a preliminary to the main discussion, a majorization-dependent quantity that can measure the quantum complexity of identical particle distributions is introduced, which we name \emph{the Boltzmann entropy of elementary quantum complexity $S_B^q$.} It decreases as the majorization of the photon distribution vector increases (Schur concavity). Using the properties of majorization and $S_B^q$, we analyze two quantities that are important criteria for the photon scattering process, $\cT$ (the runtime of a generalized classical algorithm for calculating the permanent) and $\cE$ (the additive error bound for an approximated permanent estimator). First, for all the known algorithms for computing the permanents of matrices with repeated rows and columns, the runtime $\cT$ becomes shorter as the input and output distribution vectors are more majorized. Second, the error bound $\cE$ decreases as the majorization difference of input and output states increases. In addition, $S_B^q$ turns out to be an underlying quantity of $\cT$ and $\cE$, which implies that $S_B^q$ is an essential resource for the computational complexity of linear optics. We expect that our current results would provide a clue to find the genuine resource of quantum supremacy and its operational mechanism in linear optics.