  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 the 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 MPO's bond
dimension. Notably, by simulating lossy boson sampling using MPO, we show 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.
