💻 computer science

Quantum Bayesian Networks: Compositionality and Typing via Linear Logic

This paper introduces a compositional framework for Quantum Bayesian Networks that unifies classical and quantum causal reasoning by employing a linear logic proof-net typing discipline, which recovers standard Bayesian semantics for classical causes and tensor networks for purely quantum systems.

Original authors: Rémi Di Guardia, Thomas Ehrhard, Claudia Faggian

Published 2026-04-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rémi Di Guardia, Thomas Ehrhard, Claudia Faggian

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

The Big Picture: Building with Quantum LEGO

Imagine you are trying to predict the future of a complex system. In the classical world (like weather forecasting or medical diagnosis), we use Bayesian Networks. Think of these as a set of LEGO instructions. Each block (a node) represents a piece of information, and the connections (edges) tell you how one piece affects another. If you know the rules for each small block, you can snap them together to understand the whole structure.

However, when we enter the quantum world (where particles can be entangled and exist in multiple states at once), the old LEGO instructions break. The rules for snapping blocks together change because quantum particles follow different laws (like the "No-Cloning" rule, which says you can't make a perfect copy of a quantum state).

This paper introduces a new, upgraded set of instructions called Quantum Bayesian Networks (QBNs). The authors solve two major problems that were missing in previous attempts:

Compositionality: The ability to build the big picture by understanding and combining small, independent parts.
Typing: A safety system that ensures you only snap together compatible pieces, preventing "illegal" structures.

The Problem: The "Global" vs. "Local" Puzzle

In the old way of doing things (based on the work of Henson, Lal, and Pusey), understanding a quantum network was like trying to solve a giant jigsaw puzzle by looking at the entire picture at once. You couldn't easily look at just the left side of the puzzle, figure out what it means, and then attach it to the right side. The instructions were "global," meaning you had to calculate everything together from the start.

The Authors' Solution:
They created a new mathematical tool called a Q-factor (Quantum Factor).

The Analogy: Imagine a "Q-factor" is a smart, self-contained module. It's like a specialized LEGO brick that knows how to talk to other bricks.
How it works:
- If the brick is dealing with classical data (like a coin flip), it behaves exactly like a standard probability brick. It shares information efficiently.
- If the brick is dealing with quantum data (like an entangled particle), it behaves like a "tensor network" (a complex quantum connector) that respects the rule that you cannot copy the data.
The Magic: These Q-factors can be multiplied (snapped together) and summed out (hiding irrelevant details) in any order. This means you can calculate the meaning of a small part of the system, save that result, and then snap it into the larger system later. This is what the authors call Compositionality.

The Safety System: The "Typing" Guard

Even if you have the right bricks, you might try to snap a square peg into a round hole. In quantum computing, this leads to impossible scenarios (like creating a time loop or a causal paradox).

The authors introduce Linear Logic Proof-Nets as a "Typing" system.

The Analogy: Think of this as a strict quality control inspector at a factory. Every LEGO brick has a label (a "type") on it.
- Some bricks are Inputs (Negative types).
- Some bricks are Outputs (Positive types).
- Some are Classical (like a coin), and some are Quantum (like a qubit).
The Rule: You can only connect an Output to an Input. You cannot connect two Outputs together.
The Result: If you try to build a network that creates a time loop (a cycle), the "Inspector" (the typing system) will immediately say, "No, that's not a valid structure." This guarantees that any network you build is logically sound and represents a real, possible physical process.

The Bell Experiment: A Concrete Example

The paper uses the famous Bell Experiment (Alice, Bob, and Quentin) to show how this works.

The Setup: Quentin prepares two entangled quantum coins and sends one to Alice and one to Bob. Alice and Bob each flip a coin to decide how to measure their quantum coin.
The Old Way: To calculate the probability of their results, you had to write down a massive equation involving everyone and everything at once.
The New Way:
1. You define Quentin's preparation as a Q-factor.
2. You define Alice's measurement choice as a Q-factor.
3. You define Bob's measurement choice as a Q-factor.
4. You snap them together using the new "Product" rule.
5. You "sum out" (hide) the hidden quantum details to get the final probability of what Alice and Bob saw.

Because of the new typing system, the paper proves that this process is mathematically identical to the old, complex global method, but it allows you to build the answer piece by piece.

Summary of Achievements

Unified Language: They created a single language (Q-factors) that handles both classical probability and quantum mechanics seamlessly. When there is no quantum stuff, it looks exactly like standard statistics. When there is quantum stuff, it handles the weirdness correctly.
Modular Building: You can now design small quantum systems, test them, and combine them into larger systems without having to restart the math from scratch.
Safety First: By using "Proof-Nets" (a type of graph from logic), they ensure that any network you build is free of logical errors and time loops.

In short: The authors took the messy, "do-it-all-at-once" approach to quantum probability and replaced it with a clean, modular, and safe system where you can build complex quantum predictions just like snapping together LEGO bricks, knowing that the typing system will catch any mistakes before they happen.

1. Problem Statement

Context:
Bayesian Networks (BNs) are the standard framework for probabilistic reasoning and causal inference in classical systems. They rely on a Directed Acyclic Graph (DAG) where nodes represent random variables and edges represent conditional dependencies. The semantics of a BN is defined by a joint probability distribution factorized into Conditional Probability Tables (CPTs). A key strength of classical BNs is compositionality: the ability to compute marginal distributions (inference) by performing local operations (product and sum-out) on factors without constructing the full joint distribution.

The Gap:
When extending BNs to quantum systems (Quantum Bayesian Networks or QBNs), existing frameworks (specifically the instrument-based approach by Henson, Lal, and Pusey [10]) face two critical limitations:

Lack of Compositionality: The standard definition requires a global, top-down evaluation order. It does not allow for the semantics of a sub-network to be computed independently and then composed with others. This prevents modular reasoning.
Incompatibility of Operations: Classical inference relies on "sharing" variables (multiplying factors over shared variables). Quantum mechanics, governed by the No-Cloning Theorem, forbids the duplication of quantum states. Standard tensor networks handle quantum data but lack the mechanism to efficiently handle the "sum-out" (marginalization) of hidden variables in a way that preserves the efficiency of classical inference algorithms.

Goal:
The authors aim to develop a formalism for QBNs that:

Generalizes classical BNs to include quantum data.
Restores compositionality and modularity (allowing sub-networks to be defined and composed independently).
Ensures typing to guarantee that compositions result in valid DAGs (no cycles).
Maintains compatibility with existing classical inference techniques.

2. Methodology

The authors employ a dual approach combining Denotational Semantics (specifically adapting Selinger's work) and Proof Theory (Linear Logic).

A. Quantum Factors (Q-factors)

The core mathematical innovation is the introduction of Quantum Factors (Q-factors).

Definition: A Q-factor is a function $\phi: \text{Val}(X) \to \mathcal{L}(\mathcal{H}_Q)^+$ , mapping classical variable assignments to positive operators on a Hilbert space (quantum register).
Unification: This definition unifies classical factors (where the Hilbert space is 1-dimensional) and quantum states (where the classical set is empty).
Operations: The authors define two operations on Q-factors:
1. Product ( $\odot$ ): Combines two Q-factors. Crucially, for classical variables, it behaves like standard factor multiplication (sharing values). For quantum registers, it behaves like the tensor product but uses a symmetric difference ( $Q_1 \Delta Q_2$ ) for the resulting register scope to respect the No-Cloning theorem (qubits are consumed/merged, not duplicated).
2. Sum-out ( $\sum$ ): Marginalizes variables.
  - For classical variables: Summation over values.
  - For quantum registers: Partial trace ( $\text{tr}$ ).
Closure: The set of Q-factors is closed under both product and sum-out, enabling modular computation of marginals.

B. Quantum CPTs (Q-cpts)

To ensure the semantics of a network results in a valid probability distribution (and not just an arbitrary positive operator), the authors define Quantum CPTs.

These are Q-factors satisfying specific normalization conditions (analogous to stochastic matrices for classical variables and Choi states for quantum channels).
A QBN is defined as a DAG where every node is associated with a Q-cpt.

C. Typed Graphical Formalism (Linear Logic)

To address modularity and the prevention of cycles (DAG property), the authors encode QBNs into Multiplicative Linear Logic (MLL) Proof-Nets.

Types: Classical variables and qubits are assigned polarities (positive/negative).
- Negative atoms ( $X^-, q^-$ ) represent inputs.
- Positive atoms ( $X^+, q^+$ ) represent outputs.
Boxes: Nodes in the QBN are represented as "boxes" in the proof-net, containing a Q-cpt.
Polarity and DAGs: The polarity of formulas induces an orientation on the graph edges. The authors prove that a "polarized" proof-net corresponds exactly to a DAG.
Composition: Two proof-nets can be composed via the Cut Rule if their types are dual (e.g., $A$ and $A^\perp$ ). This typing discipline statically guarantees that the resulting graph is a valid DAG.

3. Key Contributions

Definition of Quantum Factors (Q-factors):
- A new mathematical object that generalizes classical factors and tensor networks.
- It resolves the tension between classical variable sharing and quantum no-cloning by defining a product operation that handles classical sharing and quantum merging (via symmetric difference of registers).
Compositional Semantics for QBNs:
- The paper reformulates QBNs such that the semantics of the whole network is the product of the semantics of its sub-networks ( $\llbracket B \rrbracket = \llbracket B_1 \rrbracket \odot \llbracket B_2 \rrbracket$ ).
- This allows for modular inference: one can compute the marginal of a sub-component by summing out hidden variables locally, a feature missing in previous instrument-based definitions.
Typing Discipline via Linear Logic:
- The authors map QBNs to MLL proof-nets.
- They prove that typing guarantees modularity: composing two well-typed proof-nets (via cut) always yields a valid proof-net (and thus a valid DAG), preventing the formation of causal cycles.
- This provides a static check for the structural validity of quantum causal models.
Equivalence Proofs:
- The Q-factor based definition is proven equivalent to the instrument-based definition in [10].
- The semantics of a QBN is shown to be identical to the semantics of its corresponding quantum proof-net.

4. Results

Theoretical Equivalence: The paper establishes that the new Q-factor formalism is mathematically equivalent to the existing instrument-based QBNs but offers superior structural properties (compositionality).
Preservation of Classical Limits:
- If all nodes are classical, the Q-factor product reduces to standard factor multiplication, and the framework collapses to standard Bayesian Networks.
- If all nodes are quantum, the framework behaves like Tensor Networks.
Invariance of Semantics: The semantics of a proof-net is invariant under reduction (cut-elimination). This means the order of computation (reduction steps) does not change the final probability distribution, ensuring the robustness of the inference process.
Modularity: The typing system successfully prevents the construction of cyclic graphs (e.g., the example in Fig. 4 where $N_0$ and $N_2$ cannot be composed because their types are incompatible, whereas $N_0$ and $N_1$ compose to a valid DAG).

5. Significance

Bridging Inference and Causality: The work successfully integrates the causal modeling perspective (QBNs) with the efficient inference perspective (factor-based algorithms). Previous quantum causal models often struggled to support efficient marginalization of hidden variables.
Algorithmic Potential: By establishing that Q-factors are closed under product and sum-out, the paper paves the way for adapting classical efficient inference algorithms (like Variable Elimination or Belief Propagation) to the quantum domain.
Foundational Rigor: Using Linear Logic provides a rigorous, type-theoretic foundation for quantum causal structures. It moves beyond ad-hoc definitions to a system where structural properties (like acyclicity) are guaranteed by the type system.
Future Applications: This framework is essential for:
- Device-Independent Cryptography: Analyzing protocols where trust in devices is minimized.
- Quantum Machine Learning: Developing models that can reason over mixed classical-quantum data.
- Foundations of Physics: Providing a formal language to discuss non-locality and entanglement within a causal inference framework.

In summary, the paper solves the "compositionality problem" in Quantum Bayesian Networks by introducing Q-factors and a Linear Logic typing system, enabling modular, efficient, and structurally sound reasoning about mixed classical-quantum causal systems.