In the current NISQ (Noisy Intermediate Scale Quantum) era, quantum processors are noise-limited, dictating the need for fault-tolerant circuits. As techniques for fault-tolerant quantum computation keep improving, it is natural to ask: what is the fundamental lower bound on redundancy? Relatively fewer works have addressed the question of minimum redundancy requirement. However, as better and better codes are found, the interest in understanding the fundamental limit on space overhead is growing.

In this talk we focus on obtaining a lower bound on the redundancy required for ϵ-accurate implementation of a large class of operations that includes unitary operators. For the practically relevant case of sub-exponential depth and sub-linear gate size, our bound on redundancy is tighter than the known lower bounds. We obtain this bound by connecting fault-tolerant computation with a set of finite blocklength quantum communication problems whose accuracy requirements satisfy a joint constraint. This lower bound holds for a large class of noise models and also translates to an upper bound on the noise threshold above which fault-tolerant computation is impossible. Our bound directly extends to the case where noise at the outputs of a gate are non-i.i.d. but noise across gates are i.i.d.