Realistic lower bounds for the factorization time of large numbers on a quantum computer

We investigate the time T a quantum computer requires to factorize a given number dependent on the number of bits L required to represent this number. We stress the fact that in most cases one has to take into account that the execution time of a single quantum gate is related to the decoherence time of the quantum bits (qubits) that are involved in the computation. Although exhibited here only for special systems, this interdependence of decoherence and computation time seems to be a restriction in many current models for quantum computers and leads to the result that the computation time T scales much stronger with L than previously expected. 1996 The American Physical Society.