qml-expressivity-separation

name: qml-expressivity-separation description: > Quantum Machine Learning expressivity separation methodology. Based on Anschuetz & Gao (Quantum 10, 1976, 2026). Provides framework for constructing efficiently trainable QNNs with provable polynomial memory separations over classical neural networks. Use when: (1) designing QNN architectures with provable quantum advantage, (2) analyzing expressivity vs trainability trade-offs, (3) implementing quantum contextuality as computational resource, (4) comparing quantum vs classical sequence modeling capabilities. Keywords: quantum machine learning, QNN, expressivity, contextuality, polynomial separation, trainable.

QML Expressivity Separation

Based on Anschuetz & Gao, "Arbitrary Polynomial Separations in Trainable Quantum Machine Learning" (Quantum 10, 1976, 2026).

Core Result

Constructed hierarchy of efficiently trainable QNNs that exhibit unconditionally provable polynomial memory separations of arbitrary constant degree over classical neural networks (including Transformers) for classical sequence modeling tasks.

Key Concepts

Expressivity-Trainability Trade-off

Previous work showed a fundamental tension:

• High expressivity QNNs → exponential training time
• Trainable QNNs → limited expressivity advantage

This work circumvents the trade-off by:

1. Constructing QNNs with constant gate complexity per unit cell
2. Achieving polynomial (not exponential) but arbitrary degree separations
3. Using quantum contextuality as the resource

Quantum Contextuality

Definition: Quantitative notion of semantic ambiguity — the inability to assign consistent classical values to all measurement outcomes simultaneously.

Role in QML: Contextuality in the quantum model's latent space is the source of expressivity separation. Tasks with semantic ambiguity are natural candidates for quantum advantage.

Architecture Design

Unit Cell Structure

Input → [Quantum Gate Layer] → [Measurement] → Output
              ↓
        Constant gate complexity (O(1))

Key Properties

1. Efficient Trainability: Gradient-based optimization converges in polynomial time
2. Polynomial Separation: Memory advantage of degree d for any constant d
3. Constant Gate Complexity: Each unit cell uses O(1) gates
4. Sequence Modeling: Applicable to classical sequential data tasks

Implementation Framework

Step 1: Define the Task

# Sequence modeling task with semantic ambiguity
# Example: Natural language understanding, temporal patterns
# where context changes meaning (contextuality-friendly)
def task(x_sequence):
    # Input: sequence of symbols
    # Output: classification/prediction
    return model(x_sequence)

Step 2: Construct the QNN

import pennylane as qml
import numpy as np

def qnn_unit_cell(wires, params):
    """Single unit cell with constant gate complexity."""
    n_wires = len(wires)
    
    # Ansatz with O(1) gates per cell
    for i, w in enumerate(wires):
        qml.Rot(params[i, 0], params[i, 1], params[i, 2], wires=w)
    
    # Entangling layer
    for i in range(len(wires) - 1):
        qml.CZ(wires=[wires[i], wires[i+1]])
    
    return qml.state()

def qnn_circuit(inputs, params, n_layers):
    """Full QNN with multiple unit cells."""
    n_qubits = len(inputs)
    wires = range(n_qubits)
    
    # Encode input
    for i, x in enumerate(inputs):
        qml.RY(x, wires=i)
    
    # Apply unit cells
    for layer in range(n_layers):
        qnn_unit_cell(wires, params[layer])
    
    # Measure observables
    return [qml.expval(qml.PauliZ(i)) for i in wires]

Step 3: Training Loop

def train_qnn(qnn, data, labels, n_steps, lr=0.01):
    """Gradient-based training (efficiently trainable by construction)."""
    params = initialize_params()
    
    for step in range(n_steps):
        # Forward pass
        predictions = qnn(data, params)
        
        # Compute loss
        loss = compute_loss(predictions, labels)
        
        # Compute gradients (efficient due to structure)
        grads = qml.grad(loss_fn)(params)
        
        # Update
        params -= lr * grads
    
    return params

When to Use This Approach

Suitable Tasks

• Sequence modeling with contextual/ambiguous semantics
• Natural language understanding tasks
• Temporal pattern recognition
• Tasks where classical models need large context windows

Unsuitable Tasks

• Tasks already efficiently solvable classically
• Problems without inherent ambiguity/complexity
• Tasks where polynomial separation is insufficient

Theoretical Guarantees

Relationship to Other Work

• Complements Google's RL-QEC work: This paper addresses algorithmic expressivity, RL-QEC addresses hardware control
• Contrasts with exponential separation claims: Focuses on trainable models with realistic advantages
• Connects to contextuality literature: Formalizes contextuality as ML resource

References

• Quantum 10, 1976 (2026) - Main paper
• arXiv:2402.08606v4 - Preprint version
• "Does provable absence of barren plateaus imply classical simulability?" (Nature Communications, 2025)