Quantum Occam Learning

---
name: quantum-occam-learning
description: "Quantum Occam Learning methodology — information-theoretic framework for balancing expressibility and learnability in circuit-based quantum machine learning. Use when designing quantum neural network ansätze, choosing quantum data encoding circuits, or analyzing generalization bounds for variational quantum algorithms. arXiv: 2606.12211"
tags: ["quantum", "machine-learning", "information-theory", "generalization", "ansatz-design"]
related_skills: ["qml-feature-encoding", "qml-expressivity-separation", "quantum-ml-certified-training"]
---

# Quantum Occam Learning

**Source**: arXiv:2606.12211 — "Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning" by Jeongho Bang, Kyoungho Cho, Jeongwoo Jae (2026-06-10)

## Overview

A central principle in quantum machine learning is that an ansatz should be expressive enough to represent the quantum data of interest. Yet, expressibility is statistically meaningful only insofar as it can be learned from finitely many copies of an unknown quantum state. This paper develops an information-theoretic **Occam theory** for quantum data generated by finite-size quantum circuits, introducing **Sample-Supported Expressibility (SSE)** as a quantifiable measure that bridges the gap between expressiveness and learnability.

## Core Concepts

### Sample-Supported Expressibility (SSE)

SSE quantifies how much expressibility of a quantum circuit ansatz is actually supported by the available training samples. Key insight: a highly expressive circuit that requires more copies than available to learn is effectively useless — it over-expresses relative to sample support.

$$\text{SSE} = f(\text{Expressibility}, \text{Sample Size}, \text{Circuit Depth})$$

The framework provides:
- **Information-theoretic bounds** on generalization error for quantum learning
- **Sample complexity analysis** for circuit-based quantum learning tasks
- **Ansatz selection criteria** that balance expressiveness with finite-sample learnability

### Key Results

1. **Occam Bound**: A quantum learning problem admits a generalization bound scaling with the "effective expressibility" of the circuit, not its raw expressibility
2. **Sample-Expressibility Trade-off**: Beyond a critical circuit depth, additional expressibility is not supported by finite samples and degrades generalization
3. **Optimal Ansatz Design**: The framework provides criteria for choosing circuit architectures that maximize learnability under sample constraints

## Workflow

### Step 1: Quantify Ansatz Expressibility

For a given parameterized quantum circuit (PQC):
```python
from qiskit.circuit.library import RealAmplitudes
from qiskit.quantum_info import random_statevector

def compute_circuit_expressibility(circuit, n_samples=100):
    """Measure how well the circuit covers the Hilbert space."""
    from scipy.stats import kstest
    import numpy as np
    
    entanglements = []
    for _ in range(n_samples):
        params = np.random.uniform(0, 2*np.pi, circuit.num_parameters)
        # Compute entanglement entropy or similar metric
        entanglements.append(measure_entanglement(circuit, params))
    
    # Compare to Haar random distribution via KS test
    ks_stat, p_value = kstest(entanglements, 'uniform')
    return 1 - ks_stat  # Higher = more expressive
```

### Step 2: Compute Sample Complexity

```python
def sample_complexity_bound(circuit_depth, n_qubits, target_error=0.1):
    """Lower bound on number of quantum state copies needed."""
    # From the Occam theory framework
    # d = circuit_depth, n = n_qubits
    # Sample complexity ~ O(2^n * d * log(1/epsilon))
    import numpy as np
    return int(np.ceil((2**n_qubits * circuit_depth * np.log(1/target_error))))
```

### Step 3: Compute SSE Score

```python
def compute_sse(expressibility, n_copies, n_qubits, circuit_depth):
    """Sample-Supported Expressibility score.
    
    Returns a value in [0, 1] where:
    - 1.0 = all expressibility is sample-supported
    - 0.0 = no expressibility is sample-supported (over-expressed)
    """
    required_copies = sample_complexity_bound(circuit_depth, n_qubits)
    
    if n_copies >= required_copies:
        return expressibility  # Fully supported
    else:
        # Scale down by sample support ratio
        support_ratio = n_copies / required_copies
        return expressibility * support_ratio
```

### Step 4: Ansatz Selection

```python
def select_optimal_ansatz(candidates, n_copies_available, n_qubits):
    """Select the circuit ansatz with highest SSE."""
    best_score = -1
    best_ansatz = None
    
    for circuit in candidates:
        expr = compute_circuit_expressibility(circuit)
        sse = compute_sse(expr, n_copies_available, n_qubits, circuit.depth())
        if sse > best_score:
            best_score = sse
            best_ansatz = circuit
    
    return best_ansatz, best_score
```

## Application Domains

- **VQA Ansatz Design**: Choosing parameterized circuits for variational quantum algorithms
- **Quantum Kernel Methods**: Determining optimal feature map circuits
- **Quantum Neural Architecture Search**: Automating circuit selection under sample constraints
- **Generalization Analysis**: Understanding why some quantum models overfit despite limited parameters

## Activation

- quantum occam learning
- quantum generalization bounds
- quantum ansatz design
- quantum sample complexity
- quantum overfitting
- quantum machine learning expressibility
- 量子奥卡姆学习
- 量子泛化界
- 量子ansatz设计

## Model Recommendation

- **sonnet4.5** (Balanced for quantum ML analysis)
- **opus4.5** (For theoretical derivations)

## Tools Used

- **qiskit** or **pennylane** for circuit simulation
- **numpy/scipy** for statistical analysis
- **terminal** for executing quantum circuit simulations

## Pitfalls

1. **Expressibility ≠ Learnability**: A maximally expressive circuit may require exponentially many copies to learn — high expressibility without sample support leads to overfitting
2. **Finite-Resource Regime**: The framework is most relevant in NISQ era where state copies are limited (not asymptotic)
3. **Circuit Depth vs Width Trade-off**: Deeper circuits increase expressibility but also increase sample complexity — the optimal point depends on available copies
4. **Noise Effects**: The base theory assumes ideal circuits — noisy implementations may further reduce effective sample support
5. **Not a Replacement for All Ansatz Design**: SSE complements other criteria (hardware efficiency, gate fidelity) rather than replacing them

## References

- Bang, J., Cho, K., & Jae, J. (2026). "Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning." arXiv:2606.12211
- Related work on quantum generalization bounds and expressibility-trainability trade-offs