  Characterizing the computational advantage from noisy intermediate-scale
quantum (NISQ) devices is an important task from theoretical and practical
perspectives. Here, we numerically investigate the computational power of NISQ
devices focusing on boson sampling, one of the well-known promising problems
which can exhibit quantum supremacy. We study hardness of lossy boson sampling
using matrix product operator (MPO) simulation to address the effect of
photon-loss on classical simulability using MPO entanglement entropy (EE),
which characterizes a running time of an MPO algorithm. An advantage of MPO
simulation over other classical algorithms proposed to date is that its
simulation accuracy can be efficiently controlled by increasing an MPO's bond
dimension. Notably, we show by simulating lossy boson sampling using an MPO
that as an input photon number grows, its computational cost, or MPO EE,
behaves differently depending on a loss-scaling, exhibiting a different feature
from that of lossless boson sampling. Especially when an output photon number
scales faster than the square root of an input photon number, our study shows
an exponential scaling of time complexity for MPO simulation. On the contrary,
when an output photon number scales slower than the square root of an input
photon number, MPO EE may decrease, indicating that an exponential time
complexity might not be necessary.
