Quantum Algorithms for Compositional Natural Language Processing

Abstract

We propose a new application of quantum computing to the field of natural language processing. Ongoing work in this field attempts to incorporate grammatical structure into algorithms that compute meaning. In (Coecke, Sadrzadeh and Clark, 2010), the authors introduce such a model (the CSC model) based on tensor product composition. While this algorithm has many advantages, its implementation is hampered by the large classical computational resources that it requires. In this work we show how computational shortcomings of the CSC approach could be resolved using quantum computation (possibly in addition to existing techniques for dimension reduction). We address the value of quantum RAM (Giovannetti,2008) for this model and extend an algorithm from Wiebe, Braun and Lloyd (2012) into a quantum algorithm to categorize sentences in CSC. Our new algorithm demonstrates a quadratic speedup over classical methods under certain conditions.

In Proceedings SLPCS 2016, arXiv:1608.01018

References in corpus (13)

• Quantum support vector machine for big data classification
• Quantum random access memory
• Quantum Data Fitting
• Experimental Support for a Categorical Compositional Distributional Model of Meaning
• Entanglement-Based Machine Learning on a Quantum Computer
• Quantum Algorithm for Linear Regression
• Quantum Inference on Bayesian Networks
• Mathematical Foundations for a Compositional Distributional Model of Meaning
• Compositional Distributional Semantics with Compact Closed Categories and Frobenius Algebras
• Category-Theoretic Quantitative Compositional Distributional Models of Natural Language Semantics
• Graded Entailment for Compositional Distributional Semantics
• A quantum teleportation inspired algorithm produces sentence meaning from word meaning and grammatical structure
• Learning Type-Driven Tensor-Based Meaning Representations

Cited by in corpus (19)

• QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer
• Quantum Natural Language Processing on Near-Term Quantum Computers
• Quantum Language Model with Entanglement Embedding for Question Answering
• Quantum Machine Learning for Finance
• Advances in Quantum Deep Learning: An Overview
• Applying QNLP to sentiment analysis in finance
• DisCoPy: Monoidal Categories in Python
• Grammar-aware sentence classification on quantum computers
• A hybrid classical-quantum workflow for natural language processing
• Foundations for Near-Term Quantum Natural Language Processing
• Autonomization of Monoidal Categories
• lambeq: An Efficient High-Level Python Library for Quantum NLP
• Meaning updating of density matrices
• Functorial Question Answering
• Property-guided Inverse Design of Metal-Organic Frameworks Using Quantum Natural Language Processing
• Fast Extraction of Word Embedding from Q-contexts
• Implications of Deep Circuits in Improving Quality of Quantum Question Answering
• Quantum Algorithms for Compositional Text Processing
• Quantum Computation