INESC TEC, University of Cambridge, and Foxconn publish study in Nature Communications proving the potential of quantum computing

Michael Oliveira, a researcher at INESC TEC, in collaboration with the University of Cambridge and Foxconn, has achieved a significant milestone in quantum computing. The study, published in the journal Nature Communications, clearly demonstrates—without relying on complex theoretical assumptions—that simple and shallow quantum circuits, even when subject to noise, can solve problems that are completely beyond the reach of classical parallel computers, even the most advanced ones.

Using quantum units called qudits—generalised versions of qubits—the authors show that parallel quantum computing can outperform classical models by identifying and analysing a new family of problems called inverted strict modular relation problems (ISMRP). These problems can be efficiently solved by parallel quantum circuits but are exponentially difficult for parallel classical circuits.

“Examples of these models include those inspired by modern neural networks used in artificial intelligence, including even some of the simplest large language models (LLMs), which we know through more elaborate versions like ChatGPT, Gemini, or even DeepSeek,” explains Michael Oliveira, a researcher in the field of quantum computing.

Aiming to deepen the understanding of the differences between classical and quantum models in this area of parallel computing, this research paves the way for future advances in quantum machine learning, highlighting the potential for quantum approaches to surpass classical ones. “Furthermore, this study analyses the computational resources required and indicates that these computational advantages may be demonstrated on quantum computers in the near future,” adds the researcher.

The article, titled “Unconditional advantage of noisy qudit quantum circuits over biased threshold circuits in constant-depth,” was published in Nature Communications, one of the most prestigious journals in the Nature family, and presented at the Theory of Quantum Computation, Communication and Cryptography and Quantum Physics and Logic conferences—two of the most highly regarded events in the field of quantum computing.