Quantum algorithms help computers understand language

PhD project brings together physics and linguistics

Tools from quantum mechanics can help computers to interpret ambiguous language. PhD candidate Adriana Duarte Correia showed that the application of quantum algorithms might allow computers to understand language better and faster. Today, she will defend her thesis entitled ‘Quantum distributional semantics’ at Utrecht University.

Words or sentences can often have multiple meanings. This is a concept that is hard to grasp for regular computers. Correia used quantum algorithms to make computers understand that a sentence like ‘Look at the dog with one eye’ can mean two different things at the same time.

Cover of Correia's dissertation

Natural language processing

When you do an online search, your search engine tries to understand what you are writing so it can give useful suggestions. The process behind this is called natural language processing (NLP). Currently, most NLP researchers use a method that is not flawless: the computer gets about 80 percent of the cases right. Correia: “Those are the simple cases, linguistically speaking. But if you want to make sure that the computer gets the more complex cases right, the method becomes really computationally expensive. Our goal was to improve the rate of understanding and to speed up the process by using quantum computations.”

Schrödinger’s cat

But how can quantum computers and algorithms improve NLP? It all has to do with Schrödinger’s cat. This famous thought experiment illustrates the concept of quantum superposition, which allows for two apparently opposite states to exist at the same time. Correia: “What we really went for were the complex cases like ‘Fluffy cats and birds’. Does it mean that only the cats are fluffy, or are the birds fluffy as well? Using our quantum approach, both possibilities can co-exist at the same time, until more information makes clear what the intended meaning was.”

Theoretical quantum speedup

“We applied Grovers algorithm, a well-known quantum algorithm. Using this approach, we proved that our methods need less computations to answer certain language related questions than the currently used methods. Most excitingly, this speedup was completely due to our quantum approach. A more common approach to speed up the processing of language by computers is to use machine learning. In contrast to machine learning, our computer did not need to be trained at all.”

Correia explains that her results are still purely mathematical and therefore theoretical. Other students are now trying to implement it on real quantum computers, but the road ahead is still long. “The implementations of these quantum computers are still in its infancy. More research is needed to translate the theoretical speedup to an actual speedup in time.’

Challenging but rewarding

Correia studied Theoretical Physics at Utrecht University. At the end of her master’s, she realised she wanted to work on a project that combined theoretical physics and language. Together with professor Henk Stoof, her master’s thesis supervisor, she contacted linguistics professor Michael Moortgat and applied for a scholarship at the Centre for Complex Systems Studies. Correia is proud of the results they got, especially as the project was quite challenging because of its interdisciplinary nature.

“The people from physics spoke a different language, so to speak, than the people from linguistics. I had to find out how to bring the two fields together.”