  Deterministic quantum computation with one quantum bit (DQC1), or the one
clean qubit model, [E. Knill and R. Laflamme, Phys. Rev. Lett. {\bf81}, 5672
(1998)] is a model of quantum computing where the input is the tensor product
of a single pure qubit and many completely-mixed states, and only the single
qubit is measured at the end of the computation. In spite of its naive
appearance, the DQC1 model can efficiently solve some problems for which no
classical efficient algorithms are known, and therefore it has been conjectured
that the DQC1 model is more powerful than classical computing (under the
assumption of $\mbox{BPP}\subsetneq\mbox{BQP}$). Here we show that the output
probability distribution of the DQC1 model cannot be classically efficiently
approximated (exactly within a polynomial bit length or in the fully polynomial
randomized approximation scheme (FPRAS) with at most a constant error) unless
$\mbox{BQP}\subseteq\mbox{BPP}$.
