John Preskill

The cost of quantum fault tolerance

A classical circuit can be accurately simulated with a fault-tolerant circuit constructed from noisy classical gates. Similarly, a quantum circuit can be accurately simulated with a fault-tolerant circuit constructed from noisy quantum gates. But what is the cost of the simulation? Classically, the fault-tolerant simulation of an ideal circuit with size L and depth D can be achieved by a noisy circuit of size O(L\log(L)) and depth O(D). I will show, using topological codes in four or more spatial dimensions, that the fault-tolerant simulation of an ideal quantum circuit with size L and depth D can be achieved by a noisy quantum circuit with size O(L\polylog(L)) and depth O(D\log\log(L)). This depth blow-up improves what had been established previously using concatenated quantum codes. This is joint work with Charlene Ahn.