We develop a point of view on reduction of multiplicative proof nets based on quantum error-correcting codes. To each proof net we associate a code, in such a way that cut-elimination corresponds to error correction.
Proof-theoretic cryptography is an emerging paradigm that grounds cryptographic security in the metatheory of linear logic proof nets, specifically the cut-elimination theorem. To enable modular construction and analysis of complex protocols in this paradigm, a compositional security framework is essential. In this paper, we propose such a framework, inspired by the Universal Composability (UC) framework but tailored to the algebraic structure of Multiplicative Linear Logic (MLL). We define a proof-net protocol as an MLL proof net with designated input/output interfaces and a partial order on its cut nodes. Two composition operators are naturally given by the logic: tensor product (⊗) for parallel composition and cut-elimination connection (◦) for sequential composition. We define an ideal functionality as a cut-free proof net together with a specification of its input/output behavior. We adopt a simulation-based security definition where the environment is an arbitrary PPT interactive Turingmachine (not restricted to proof nets), while the protocol and the adversary are described as proof-net protocols. This allows us to inherit the full power of the UC environment while keeping the protocol analysis within the proof-net framework. We then prove two composition theorems: if two protocols securely realize their respective ideal functionalities, then both their tensor product and their cut-elimination connection securely realize the corresponding compositions of the ideal functionalities. Theproofs rely on the confluence and strong normalization of cut elimination in MLL, which simplifies the analysis compared to general UC proofs, while still handling arbitrary environments. Finally, we discuss the relationship between our framework and the UC framework, clarifying that our framework is a specialization that exploits the algebraic structure of proof nets but does not sacrifice environmental generality. We also discuss the limitations of the current framework (static corruption, synchronousbroadcast) and outline directions for future generalization.
Just as conventional functional programs may be understood as proofs in an intuitionistic logic, so quantum processes can also be viewed as proofs in a suitable logic. We describe such a logic, the logic of compact closed categories and biproducts, presented both as a sequent calculus and as a system of proof-nets. This logic captures much of the necessary structure needed to represent quantum processes under classical control, while remaining agnostic to the fine details. We demonstrate how to represent quantum processes as proof-nets, and show that the dynamic behaviour of a quantum process is captured by the cut-elimination procedure for the logic. We show that the cut elimination procedure is strongly normalising: that is, that every legal way of simplifying a proof-net leads to the same, unique, normal form. Finally, taking some initial set of operations as non-logical axioms, we show that that the resulting category of proof-nets is a representation of the free compact closed category with biproducts generated by those operations.
Quantum computation holds the promise of solving certain complex problems exponentially faster than classical computers. However, the high prevalent noise in current quantum devices impedes the accurate execution of even basic algorithms. This can be remedied by protecting quantum information with a quantum error-correcting code, where the logical information of an algorithmic qubit is spread across multiple physical qubits. Individual quantum errors are then located and corrected by the fault-tolerant measurement of multi-qubit stabilizer operators (parity checks). Unfortunately, error correction and fault tolerance both impose large demands on the qubit overhead: hundreds to thousands of physical qubits per logical qubit.
We reduce the spacetime cost of fault tolerance by redesigning key building blocks of an error-corrected quantum computer. First, we develop a combinatorial proof with flag fault tolerance that exponentially reduces the extra qubits needed to measure a stabilizer of any size, while tolerating one fault. We leverage these proofs to then design state preparation circuits for the Steane and Golay codes with 100% yield. Next, we improve error correction on a planar layout by showing that a distance-four code encoding six logical qubits protects information as well as the distance-five surface code, using one-tenth as many physical qubits. Finally, we optimize the time overhead of logical gates in surface code quantum computers by protecting measurement results with a classical code, cutting computation time by a factor of two to six. Our hardware-agnostic optimizations of fault tolerance overheads thus suggest new routes to advance the timeline of error-free quantum computing.
Just as conventional functional programs may be understood as proofs in an intuitionistic logic, so quantum processes can also be viewed as proofs in a suitable logic.We describe such a logic, the logic of compact closed categories and biproducts, presented both as a sequent calculus and as a system of proof-nets. This logic captures much of the necessary structure needed to represent quantum processes under classical control, while remaining agnostic to the fine details. We demonstrate how to represent quantum processes as proof-nets and show that the dynamic behavior of a quantum process is captured by the cut-elimination procedure for the logic. We show that the cut-elimination procedure is strongly normalizing: that is, that every legal way of simplifying a proof-net leads to the same, unique, normal form. Finally, taking some initial set of operations as nonlogical axioms, we show that that the resulting category of proof-nets is a representation of the free compact closed category with biproducts generated by those operations. 3.1 Introduction 3.1.1 Logic, Processes, and Categories Birkhoff and von Neumann initiated the logical study of quantum mechanics in their well-known 1936 paper. They constructed a logic by assigning a proposition letter to each observable property of a given quantum system and studied negations, conjunctions, and disjunctions of these properties. The resulting lattice is nondistributive, and so the heart of what is called “quantum logic” is the study of various kinds of nondistributive lattices.