  We investigate the amount of noise required to turn a universal quantum gate
set into one that can be efficiently modelled classically. This question is
useful for providing upper bounds on fault tolerant thresholds, and for
understanding the nature of the quantum/classical computational transition. We
refine some previously known upper bounds using two different strategies. The
first one involves the introduction of bi-entangling operations, a class of
classically simulatable machines that can generate at most bipartite
entanglement. Using this class we show that it is possible to sharpen
previously obtained upper bounds in certain cases. As an example, we show that
under depolarizing noise on the controlled-not gate, the previously known upper
bound of 74% can be sharpened to around 67%. Another interesting consequence is
that measurement based schemes cannot work using only 2-qubit non-degenerate
projections. In the second strand of the work we utilize the Gottesman-Knill
theorem on the classically efficient simulation of Clifford group operations.
The bounds attained for the pi/8 gate using this approach can be as low as 15%
for general single gate noise, and 30% for dephasing noise.
