  It is often said that the transition from quantum to classical worlds is
caused by decoherence originated from an interaction between a system of
interest and its surrounding environment. Here we establish a computational
quantum-classical boundary from the viewpoint of classical simulatability of a
quantum system under decoherence. Specifically, we consider commuting quantum
circuits being subject to decoherence. Or equivalently, we can regard them as
measurement-based quantum computation on decohered weighted graph states. To
show intractability of classical simulation above the boundary, we utilize the
postselection argument introduced by M. J. Bremner, R. Jozsa, and D. J.
Shepherd [Proceedings of the Royal Society A: Mathematical, Physical and
Engineering Science 465, 1413 (2009).] and crucially strengthen its statement
by taking noise effect into account. Classical simulatability below the
boundary is also shown constructively by using both separable criteria in a
projected-entangled-pair-state picture and the Gottesman-Knill theorem for
mixed state Clifford circuits. We found that when each qubit is subject to a
single-qubit complete-positive-trace-preserving noise, the computational
quantum-classical boundary is sharply given by the noise rate required for the
distillability of a magic state. The obtained quantum-classical boundary of
noisy quantum dynamics reveals a complexity landscape of controlled quantum
systems. This paves a way to an experimentally feasible verification of quantum
mechanics in a high complexity limit beyond classically simulatable region.
