↵ open · Esc close
Home/ Papers/ DisCoCat & lambeq
2010–2024 NLP/LLM

DisCoCat & lambeq: Compositional Quantum NLP

Coecke, Sadrzadeh, Clark (DisCoCat, 2010); Kartsaklis, Fan, Yeung et al. (lambeq, 2021)
Mathematical Structures in CS (2010) · arXiv:1003.4394  |  lambeq: arXiv:2110.04236

Contents

  1. Motivation: Grammar as Quantum Structure
  2. Pregroup Grammars
  3. DisCoCat Framework
  4. The Meaning Functor
  5. lambeq Pipeline
  6. Sentence → Quantum Circuit
  7. Training & Classification
  8. Connection to Quixer/LLMs

1. Motivation: Grammar as Quantum Structure

DisCoCat (Distributional Compositional Categorical) is motivated by a profound structural coincidence: the mathematical framework underlying quantum mechanics (monoidal categories with tensor products) is the same framework that describes formal grammar and compositional semantics.

Key insight: Sentence meaning can be composed from word meanings using the same tensor calculus as quantum state composition. This makes natural language processing a natural fit for quantum computation.
\underbrace{\textbf{FVect}}_{\text{Vector spaces}} \cong \underbrace{\textbf{Circ}}_{\text{Quantum circuits}} \supseteq \underbrace{\textbf{FGram}}_{\text{Formal grammars}}
Eq. (1) — Structural isomorphism: vector semantics, quantum circuits, and grammars share compact closed category structure

2. Pregroup Grammars

Pregroup grammar assigns types to words using a type system with left ($l$) and right ($r$) adjoints:

Basic types:
  n  = noun phrase
  s  = sentence
  np = noun phrase (same as n in some formulations)
  p  = prepositional phrase

Word type assignments:
  "Alice"  : n           (noun)
  "likes"  : n^r · s · n^l  (transitive verb: takes noun on right and left)
  "Bob"    : n           (noun)
  "big"    : n · n^l     (adjective: left-cancels with following noun)

Sentence parsing: "Alice likes Bob"
  n    (n^r · s · n^l)    n
  ─────────────────────────
         (cancellation)
  n^r · n ⊗ s ⊗ n^l · n
  1       ⊗ s ⊗ 1
  = s    ✓ (valid sentence type)

The type reductions correspond to cups in string diagrams:

$$\eta_{n^r}: n^r \otimes n \to 1 \qquad \eta_{n^l}: n \otimes n^l \to 1$$
Eq. (2) — Cup morphisms encoding type cancellation (adjoint elimination)

3. DisCoCat Framework

DisCoCat translates the grammatical string diagram into a tensor network computation:

"Alice likes Bob"  →  String Diagram:

     Alice        likes           Bob
       │           │ │             │
       │     ╔═════╧═╧═════╗      │
       │     ║  cup n^r⊗n  ║      │
       │     ╚════╤════════╝      │
       │          │         ╔═════╧═╧═════╗
       │          │         ║  cup n⊗n^l  ║
       │          │         ╚═════╤═══════╝
       │          │               │
    [A ∈ ℝⁿ] [L ∈ ℝⁿ⊗ᵈ⊗ⁿ]  [B ∈ ℝⁿ]
                  │
       ∀i,j: contraction over noun spaces
                  │
       Result: s = L(A, B) ∈ ℝᵈ  (sentence meaning vector)

Where:
  A = meaning vector of "Alice"  ∈ ℝⁿ
  L = meaning tensor of "likes"  ∈ ℝⁿ ⊗ ℝᵈ ⊗ ℝⁿ
  B = meaning vector of "Bob"    ∈ ℝⁿ
  s = L(A, B)  (tensor contraction over noun wires)
     = Σᵢⱼ Aᵢ Lᵢₖⱼ Bⱼ  (Einstein summation)  ∈ ℝᵈ
$$\llbracket \text{"Alice likes Bob"}\rrbracket = \sum_{i,j} A_i\, L_{ikj}\, B_j \in \mathbb{R}^d$$
Eq. (3) — DisCoCat compositional meaning: tensor contraction over grammatical connections

4. The Meaning Functor

DisCoCat is formalised as a strong monoidal functor $F$ from the grammar category $\textbf{FGram}$ to the semantics category $\textbf{FVect}$ (or $\textbf{Circ}$):

$$F: \textbf{FGram} \to \textbf{FVect}$$
Eq. (4) — DisCoCat semantics functor

The functor maps:

\begin{aligned} F(n) &= \mathbb{R}^{d_n} \quad \text{(noun space)} \\ F(s) &= \mathbb{R}^{d_s} \quad \text{(sentence space)} \\ F(n^r \otimes s \otimes n^l) &= \mathbb{R}^{d_n} \otimes \mathbb{R}^{d_s} \otimes \mathbb{R}^{d_n} \quad \text{(verb tensor)} \\ F(\eta_{n^r}) &= \sum_i |i\rangle\langle i| \quad \text{(cup = trace)} \end{aligned}
Eq. (5) — Functor action on types and morphisms

Quantum Functor

The key innovation: replace $\textbf{FVect}$ with $\textbf{Circ}$ (the category of quantum circuits):

$$F_Q: \textbf{FGram} \to \textbf{Circ}$$
Eq. (6) — Quantum DisCoCat functor: sentence = quantum circuit
\begin{aligned} F_Q(n) &= \mathbb{C}^{2^{q_n}} \quad \text{($q_n$ qubits for noun)} \\ F_Q(\text{word}) &= \text{parameterised quantum circuit on word qubits} \\ F_Q(\eta) &= \text{qubit post-selection / Bell measurement} \end{aligned}

5. lambeq Pipeline

lambeq (Kartsaklis et al. 2021) is the software library implementing the full DisCoCat-to-circuit pipeline:

LAMBEQ PIPELINE
═══════════════════════════════════════════════════════════════════

Step 1: PARSING
  Input: "Alice likes Bob"
  Tool: bobcat parser (CCG/pregroup)
  Output: Pregroup diagram (string diagram)

Step 2: REWRITE RULES (optional)
  Input: String diagram
  Simplifications: curry, remove cups, merge wires
  Purpose: Reduce circuit size before translation
  Output: Simplified diagram

Step 3: PARAMETERISATION
  Input: Simplified diagram
  Assign: n qubits per noun-type wire
  Each word → ansatz circuit (IQP, StronglyEntangling, etc.)
  Output: Parameterised quantum circuit

Step 4: CIRCUIT COMPILATION
  Input: Abstract circuit
  Target: Qiskit, PennyLane, pytket
  Apply: Hardware topology mapping, gate decomposition
  Output: Hardware-specific circuit

Step 5: TRAINING
  Input: Labelled sentences
  Forward: Execute circuits → measure expectation ⟨Z_s⟩
  Loss: Cross-entropy L = -y log⟨Z_s⟩
  Gradient: Parameter-shift rule
  Update: Adam / SPSAOptimiser
  Output: Trained circuit parameters θ*

Step 6: INFERENCE
  Input: New sentence
  Output: ⟨Z_s⟩ → class probabilities → classification

6. Sentence → Quantum Circuit

Each word in a sentence is mapped to a quantum circuit block. Noun connections (cups) become qubit connections (Bell measurements or post-selection).

"Alice likes Bob"  →  Quantum Circuit:

Alice (noun, 1 qubit):
  |0⟩ ──[Ry(θ_A₁)]──[Rz(θ_A₂)]──●── ... →  noun wire (1 qubit out)

"likes" (transitive verb, 3 qubits: n^r ⊗ s ⊗ n^l):
  |0⟩ ──[Ry(θ_L₁)]────────────────────── [CNOT]──  → n^r wire
  |0⟩ ──[Ry(θ_L₂)]──[Ry(θ_L₃)]──[CNOT]──────────  → s wire (output)
  |0⟩ ──[Ry(θ_L₄)]────────────────────── [CNOT]──  → n^l wire

Bob (noun, 1 qubit):
  |0⟩ ──[Ry(θ_B₁)]──[Rz(θ_B₂)]──●── ... →  noun wire (1 qubit out)

Cup connections (grammatical contractions):
  Alice wire ──┬── Bob wire
  noun wire (from likes n^r) ──(Bell measure)
  noun wire (from likes n^l) ──(Bell measure)

Sentence wire:
  s qubit from "likes" → measure Z → ⟨Z_s⟩ ∈ [-1, 1]

Classification:
  ⟨Z_s⟩ → sigmoid → P(class=1)

Circuit Ansätze in lambeq

IQP Ansatz

Instantaneous Quantum Polynomial: $H^{\otimes n}$ then diagonal gates. Classically hard to simulate. Small circuit depth.

$$U_{\text{IQP}}(\boldsymbol{\theta}) = H^{\otimes n}\, e^{i\sum_k \theta_k Z_k \otimes Z_{k+1}}\, H^{\otimes n}$$

Strongly Entangling Ansatz

$L$ layers of parameterised single-qubit rotations followed by CNOTs with periodic boundary. High expressibility — prone to barren plateaus for large $n$.

$$U_{\text{SE}}^{(l)} = \prod_j \text{CNOT}_{j,j+1} \prod_j R_j(\theta_j^{(l)})$$

7. Training & Classification

For binary sentence classification (e.g. sentiment analysis):

$$y_{\text{pred}} = \sigma\!\left(\langle 0|\, U_{\text{sent}}^\dagger(\boldsymbol{\theta})\, Z_s\, U_{\text{sent}}(\boldsymbol{\theta})\, |0\rangle\right)$$
Eq. (7) — Prediction: expectation value of sentence qubit $Z_s$, passed through sigmoid
$$\mathcal{L} = -\sum_i \left[y_i \log y_{\text{pred},i} + (1-y_i)\log(1-y_{\text{pred},i})\right]$$
Eq. (8) — Binary cross-entropy training loss

Results (lambeq benchmarks)

· MC task (MC-TEST): ~84% accuracy (5 qubits/sentence average)
· Relative clause classification: ~90% accuracy
· Sentiment (short sentences): competitive with classical bag-of-words
· Advantage: compositional — meaning computed respecting grammar structure

8. Connection to Quixer / Quantum LLMs

DisCoCat/lambeq represents the structure-preserving approach to quantum NLP, while Quixer/HyQuT represent the black-box deep learning approach. Key differences:

Approach DisCoCat / lambeq Quixer / HyQuT
Grammar Explicit (functorial) Implicit (attention patterns)
Compositionality Exact (categorical) Emergent
Scalability Limited (circuit per sentence) Scales with sequence length
Interpretability High (grammatical structure visible) Low (black-box)
Open frontier (2025–26): Bridging DisCoCat's principled compositionality with Quixer's scalability — possibly via categorical quantum LLMs or tensor network-based language models with quantum simulation.

Related Papers

NLP/LLMHybrid Q-C
Quixer · HyQuT · QTHA
Black-box quantum transformer approach
Algorithms
HHL & QSVT
Linear algebra foundations for quantum NLP