🔢 mathematics

Quantalic lambda-calculus and additive disjunction

This paper extends quantalic linear lambda-calculus with additive disjunction to enable quantitative reasoning about case statements, establishing its soundness and approximate completeness under continuity conditions while demonstrating its applicability across categorical logic, probabilistic, and quantum computation models, notably using Banach spaces to analyze random walks.

Original authors: Renato Neves, Bruna Salgado

Published 2026-08-07

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Renato Neves, Bruna Salgado

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a robot that can make decisions, but you want to be able to measure exactly how "wrong" it might be if you give it slightly fuzzy instructions. In the world of computer science, there is a branch called logic that acts like the rulebook for how programs think. Usually, this rulebook is very strict: a program either works perfectly, or it crashes. But in the real world, things are rarely perfect. Sensors give noisy data, and we often have to guess. To handle this, scientists use a special kind of math called "quantitative logic," which treats computer programs like physical objects that can be measured by how far apart they are from each other, rather than just saying they are "equal" or "not equal."

This paper dives into a specific corner of this logic, focusing on how computers handle "choices." Think of a choice like a fork in the road: "If it's raining, take an umbrella; otherwise, wear sunglasses." In the strict world of computer logic, this is called "additive disjunction." The authors are trying to figure out how to measure the difference between two programs that make these choices, especially when the conditions for making those choices are slightly different. They want to know: if I change the rule for taking an umbrella from "if it's raining" to "if it's drizzling," how much does the final behavior of the robot change?

The authors, Renato Neves and Bruna Salgado, have taken a powerful mathematical tool called "quantalic linear lambda-calculus" and added this "choice" feature to it. Think of their tool as a super-precise ruler for computer code. Before this paper, this ruler could measure how different two straight-line instructions were, but it struggled when the code had "if-then" branches. The team successfully extended the ruler to measure these branches. They proved that their new system is "sound," meaning the math works correctly and doesn't lead to contradictions. They also showed that if you use a specific type of smooth, continuous math (like the kind used in physics to describe flowing water), the ruler becomes "approximately complete." This means that while you might not get a perfect, single number for every possible difference, you can get as close to the truth as you want by using smaller and smaller measurement steps.

To show that their new ruler actually works, they built several "playgrounds" or models where they could test it. One playground was based on probability, using Banach spaces (a type of mathematical space used to handle infinite lists of numbers). In this model, they demonstrated how to track a "random walk"—a path taken by a particle that moves randomly, like a drunk person stumbling down a street. They showed that if you approximate the rules of the walk with slightly different numbers (like using a fraction instead of an irrational number), their system can calculate exactly how the path of the walk changes. Another playground was built for quantum computing, the futuristic technology that uses the laws of physics to process information. They adapted their system to handle the strange "yes and no at the same time" nature of quantum choices.

The main takeaway is that the authors have created a flexible, mathematical framework that allows scientists to reason about computer programs not just as black-and-white right-or-wrong entities, but as things that can be slightly off, slightly different, or slightly noisy. They proved that this framework is solid and can be used to understand complex systems like random walks and quantum circuits. However, they also noted that they didn't solve every possible problem; for instance, they had to leave out a very difficult rule called the "Archimedean rule" because it requires an infinite number of steps to check, which is impractical. Instead, they offered a "good enough" version that gets closer and closer to the perfect answer. This work doesn't just sit in a textbook; it provides a new way to think about how we can trust computers when the world around them is messy and uncertain.

Technical Summary: Quantalic Lambda-Calculus and Additive Disjunction

Problem Statement
The paper addresses a limitation in the existing framework of quantalic linear $\lambda$ -calculus, which was previously introduced to reason about higher-order programs quantitatively (e.g., measuring distances between program behaviors). While the original calculus handled multiplicative structures (tensor products and linear implication), it lacked additive disjunction ( $\oplus$ ). The absence of this operator prevented the quantitative reasoning of "case" statements or conditionals, which are ubiquitous in practical programming. Specifically, the authors note that substituting approximate distributions or predicates in conditional branches (e.g., in random walks) requires a formal system that can track how small perturbations propagate through disjunctive types while maintaining congruence properties.

Methodology
The authors extend the quantalic linear $\lambda$ -calculus by incorporating additive disjunction. The methodology involves three primary components:

Syntactic Extension: The term language is augmented with introduction rules for $\oplus$ (injections inl and inr) and an elimination rule (case). The equational system is extended to a quantalic setting where (in)equations between terms are labelled by elements of a quantale $V$ . Crucially, the new rules governing case statements interact with the quantale's structure using both the monoidal operation ( $\otimes$ ) and the Cartesian structure (infima/meets, $\wedge$ ). For instance, the congruence rule for case statements involves a term $p \otimes (q \wedge r)$ , encoding a worst-case assumption regarding the divergence of branches.
Categorical Semantics: The semantics are defined within $V\text{-Cat}$ $V -Cat$ -enriched co-Cartesian autonomous categories. A key theoretical innovation is the dual nature of the enrichment:
- The multiplicative structure (tensor, linear implication) is enriched over the monoidal structure of the base category of generalized metric spaces ( $V\text{-Cat}$ ).
- The additive structure (coproducts) is enriched over the Cartesian (product) structure of $V\text{-Cat}$ .
  This distinction allows the system to model the interaction between quantitative metrics and branching logic.
Model Construction: The authors construct several models to validate the calculus:
- Generalized Metric Spaces: Using categories of preordered sets, metric spaces, and their symmetric/separated variants.
- Gluing Construction: Extending the Artin gluing technique to the quantalic setting to study meta-theoretical properties.
- Enriched Presheaves: Constructing a reflective subcategory of finite-product preserving presheaves to embed co-Cartesian monoidal categories into closed ones.
- Probabilistic Programming: Modeling the calculus in the category of Banach spaces and linear contractions ( $\mathbf{Ban}$ ), utilizing measures and total variation norms.
- Quantum Programming: Constructing a model using the Karoubi envelope (idempotent split completion) of the category of quantum channels ( $\mathbf{CPTP}$ ) to recover binary coproducts, then embedding this into enriched presheaves to handle higher-order structure.

Key Contributions and Results

Soundness and Approximate Completeness: The authors prove that the extended equational system is sound with respect to the categorical semantics. Furthermore, assuming the underlying quantale is continuous (satisfying specific continuity properties regarding the "way-below" relation), the system is shown to be approximately complete. This means that if an inequation holds in all models, it is provable for all approximations $r \ll q$ of the label $q$ . The authors explicitly omit the Archimedean rule (which requires infinite premises) to achieve this result without infinitary logic.
Quantitative Extensionality: The paper demonstrates a quantitative form of extensionality for disjunctive types. It proves that if two terms $t$ and $s$ of type $A \oplus B \to C$ are close (within distance $q$ and $r$ respectively) when restricted to inputs of type $A$ and $B$ , then the terms themselves are close within distance $q \wedge r$ .
Concrete Application to Random Walks: In the probabilistic model, the authors illustrate how the framework handles Cauchy sequences of random walks. They show how replacing an irrational threshold in a predicate with a sequence of rational approximations creates a Cauchy sequence of program behaviors that converges to the behavior of the original program. This allows for reasoning about the error propagation when approximating predicates or distributions in probabilistic algorithms.
Quantum Modeling: The paper successfully constructs a model for higher-order quantum programming by using the Karoubi envelope of $\mathbf{CPTP}$ to introduce coproducts (conditionals) and then embedding this into a presheaf category to support higher-order types, all while maintaining a metric enrichment based on the diamond norm.

Significance and Claims
The paper claims to advance the "science of program equivalence" by shifting towards flexible, quantitative perspectives that integrate functional analysis and categorical logic. The primary significance lies in:

Bridging Theory and Practice: Providing a formal mechanism to reason about the effects of small perturbations (approximations) in conditional branches of higher-order programs, a common requirement in probabilistic and quantum computing.
Structural Unification: Demonstrating that additive and multiplicative structures in quantitative logic require distinct enrichment strategies (Cartesian vs. Monoidal) within the same categorical framework.
Model Diversity: Establishing that the calculus is robust across different domains, from abstract generalized metric spaces to concrete models of probabilistic and quantum computation.

The authors remain modest regarding future work, noting that while they focused on additive disjunction, additive conjunction could likely be added analogously. They also suggest that merging these results with quantalic graded $\lambda$ -calculus could address the restrictiveness of linearity in certain paradigms, and that the established reflection and gluing constructions offer avenues for studying conservativity and concrete completeness results.

More like this