Classical Adversarial Fault-Tolerance and PCPs

We show how to compile an arbitrary classical circuit into a fault-tolerant circuit, which performs the desired computation even when an almost-linear number of bits are adversarially chosen and corrupted in each timestep. Using a variant of this fault-tolerance scheme that only detects (rather than corrects) corruptions, we give a new construction of probabilistically checkable proofs (PCPs) for NP with polylogarithmic query complexity. This PCP construction from fault-tolerance presents a promising candidate for quantization by the work of Anshu, Breuckmann, and Nguyen (STOC'24), who provided a roadmap for constructing quantum PCPs via fault-tolerance.

Source: arXiv:2608.16860v1 - http://arxiv.org/abs/2608.16860v1 PDF: https://arxiv.org/pdf/2608.16860v1 Original Link: http://arxiv.org/abs/2608.16860v1