RESILIENT QUANTUM COMPUTATION - ERROR MODELS AND THRESHOLDS

Recent research has demonstrated that quantum computers can solve cert ain types of problems substantially faster than the known classical al gorithms. These problems include factoring integers and certain physic s simulations. Practical quantum computation requires overcoming the p roblems of environmental noise and operational errors, problems which appear to be much more severe than in classical computation, due to th e inherent fragility of quantum superpositions involving many degrees of freedom. Here we show that arbitrarily accurate quantum computation s are possible provided that the error per operation is below a thresh old value. The result is obtained by combining quantum error-correctio n, fault-tolerant state recovery, fault-tolerant encoding of operation s and concatenation. It holds under physically realistic assumptions o n the errors.