@inproceedings{srikumar-2025-arent,
    title = "These Aren{'}t the Vectors You{'}re Looking For: A Proof of Quantum Advantage in Compositional Generalization",
    author = "Srikumar, Karthik",
    editor = "Pal, Santanu  and
      Pakray, Partha  and
      Jain, Priyanka  and
      Ekbal, Asif  and
      Bandyopadhyay, Sivaji",
    booktitle = "Proceedings of the QuantumNLP{\{}:{\}} Integrating Quantum Computing with Natural Language Processing",
    month = nov,
    year = "2025",
    address = "Mumbai, India (Hybrid)",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-ijcnlp-aacl/2025.quantumnlp-1.2/",
    pages = "6--9",
    ISBN = "979-8-89176-306-7",
    abstract = "Compositional generalization, the ability to systematically combine known concepts to understand and produce novel expressions, remains a fundamental, unsolved challenge for classical neural language models, whose reliance on statistical correlations in high-dimensional vector spaces inherently limits them. This paper establishes the first rigorous theoretical guarantee of an exponential quantum advantage for compositional generalization. We prove that classical language models, which represent concepts as vectors in $\mathbb{R}^d$, require a latent dimension scaling linearly with the number of concepts and compositional rules to avoid catastrophic interference. In contrast, we introduce the Quantum Compositional Embedding (QCE) framework, which leverages the intrinsic properties of quantum mechanics. In doing so, we demonstrate that QCE, utilizing only a logarithmic number of qubits, can perfectly represent and generalize compositional structures, a task provably impossible for classical models of equivalent dimensionality. The separation is proven to be exponential, providing a compelling theoretical foundation for quantum natural language processing."
}