Title: Tradeoffs on the volume of fault-tolerant circuits Show Chinese title

Title: 容错电路的体积权衡

Abstract: Dating back to the seminal work of von Neumann [von Neumann, Automata Studies, 1956], it is known that error correcting codes can overcome faulty circuit components to enable robust computation. Choosing an appropriate code is non-trivial as it must balance several requirements. Increasing the rate of the code reduces the relative number of redundant bits used in the fault-tolerant circuit, while increasing the distance of the code ensures robustness against faults. If the rate and distance were the only concerns, we could use asymptotically optimal codes as is done in communication settings. However, choosing a code for computation is challenging due to an additional requirement: The code needs to facilitate accessibility of encoded information to enable computation on encoded data. This seems to conflict with having large rate and distance. We prove that this is indeed the case, namely that a code family cannot simultaneously have constant rate, growing distance and short-depth gadgets to perform encoded CNOT gates. As a consequence, achieving good rate and distance may necessarily entail accepting very deep circuits, an undesirable trade-off in certain architectures and applications. Show Chinese abstract

Abstract: 自冯·诺依曼的开创性工作[冯·诺依曼，自动机研究，1956]以来，人们已经知道纠错码可以克服有故障的电路元件，以实现鲁棒计算。选择适当的码并不容易，因为它必须平衡多个要求。提高码的速率会减少在容错电路中使用的冗余比特的相对数量，而增加码的距离则能确保对故障的鲁棒性。如果速率和距离是唯一需要考虑的因素，我们可以像在通信设置中那样使用渐近最优的码。然而，由于一个额外的要求，选择用于计算的码具有挑战性：该码需要促进编码信息的可访问性，以实现在编码数据上的计算。这似乎与具有较大的速率和距离相冲突。我们证明确实如此，即码族不能同时具有常数速率、增长的距离和短深度的部件来执行编码的CNOT门。因此，获得良好的速率和距离可能必然要接受非常深的电路，在某些架构和应用中这是一种不希望的权衡。