Quantum Algorithms for Compositional Text Processing

Abstract

Quantum computing and AI have found a fruitful intersection in the field of natural language processing. We focus on the recently proposed DisCoCirc framework for natural language, and propose a quantum adaptation, QDisCoCirc. This is motivated by a compositional approach to rendering AI interpretable: the behavior of the whole can be understood in terms of the behavior of parts, and the way they are put together. For the model-native primitive operation of text similarity, we derive quantum algorithms for fault-tolerant quantum computers to solve the task of question-answering within QDisCoCirc, and show that this is BQP-hard; note that we do not consider the complexity of question-answering in other natural language processing models. Assuming widely-held conjectures, implementing the proposed model classically would require super-polynomial resources. Therefore, it could provide a meaningful demonstration of the power of practical quantum processors. The model construction builds on previous work in compositional quantum natural language processing. Word embeddings are encoded as parameterized quantum circuits, and compositionality here means that the quantum circuits compose according to the linguistic structure of the text. We outline a method for evaluating the model on near-term quantum processors, and elsewhere we report on a recent implementation of this on quantum hardware. In addition, we adapt a quantum algorithm for the closest vector problem to obtain a Grover-like speedup in the fault-tolerant regime for our model. This provides an unconditional quadratic speedup over any classical algorithm in certain circumstances, which we will verify empirically in future work.

In Proceedings QPL 2024, arXiv:2408.05113

References in corpus (24)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• An introduction to quantum machine learning
• Quantum fingerprinting
• Parameterized quantum circuits as machine learning models
• Quantum random access memory
• Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms
• Towards Quantum Machine Learning with Tensor Networks
• Matchgates and classical simulation of quantum circuits
• Quantum fidelity measures for mixed states
• QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer
• The Frobenius anatomy of word meanings I: subject and object relative pronouns
• Quantum Analog-Digital Conversion
• Quantum Algorithms for Compositional Natural Language Processing
• Exact two-qubit universal quantum circuit
• Quantum Natural Language Processing on Near-Term Quantum Computers
• Re-examining the quantum volume test: Ideal distributions, compiler optimizations, confidence intervals, and scalable resource estimations
• Grammar-aware sentence classification on quantum computers
• Quantum Natural Language Processing
• Near-Term Advances in Quantum Natural Language Processing
• Characterization of variational quantum algorithms using free fermions
• Compositionality as we see it, everywhere around us
• Uniqueness of Composition in Quantum Theory and Linguistics
• Distilling Text into Circuits
• A categorical semantics of quantum protocols