⚛️ quantum physics

Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm

Este trabalho apresenta um algoritmo de multiplicação de matrizes baseado em kernels quânticos (QKMM) que alcança uma complexidade computacional assintoticamente ótima de $O(N^2 \log_2 N)$ , superando a eficiência dos algoritmos clássicos atuais.

Autores originais: Jiaqi Yao, Ding Liu

Publicado 2026-02-10

📖 4 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Jiaqi Yao, Ding Liu

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

O Super-Calculador de Matrizes: Como a Computação Quântica pode acelerar a Inteligência Artificial

Imagine que você é um bibliotecário em uma biblioteca gigantesca, com milhões de livros. De repente, alguém te dá uma tarefa: "Encontre a soma de todas as palavras de todos os livros desta biblioteca."

Se você for um humano comum (ou um computador clássico, como o seu notebook), você terá que pegar um livro por vez, ler cada palavra, somar e passar para o próximo. Se a biblioteca crescer, você vai levar anos, décadas ou séculos para terminar. Isso é o que chamamos de "complexidade alta".

Agora, imagine que você ganha um superpoder mágico: você pode se transformar em um "fantasma" que consegue estar em todos os corredores da biblioteca ao mesmo tempo. Em vez de ler um livro por vez, você lê todos de uma vez só. Isso é o que a Computação Quântica tenta fazer.

O Problema: O "Cálculo de Matrizes"

No mundo da tecnologia, quase tudo o que é importante — desde os filtros do Instagram até o ChatGPT — funciona através de algo chamado Multiplicação de Matrizes. Pense nas matrizes como enormes tabelas de números que contêm todas as informações de uma imagem ou de um pensamento de uma IA.

O problema é que, quanto maior a tabela (mais "inteligente" a IA), mais tempo o computador leva para fazer essas contas. Atualmente, os computadores mais rápidos do mundo ainda "batem cabeça" quando as tabelas ficam grandes demais.

A Descoberta do Artigo: O Algoritmo QKMM

Os pesquisadores da Universidade de Tiangong criaram um novo método chamado QKMM (Multiplicação de Matriz baseada em Kernel Quântico).

Para entender a diferença, vamos usar uma analogia de Culinária:

O Método Clássico (O Chef Tradicional): Imagine um chef que precisa fazer 1.000 sanduíches. Ele pega o pão, coloca o queijo, coloca o presunto, fecha o pão. Depois faz o segundo, o terceiro... Ele é muito bom, mas ele é limitado pela velocidade das suas mãos.
O Método Quântico Antigo: Era como se o chef tivesse várias mãos extras, mas ele ainda precisava de uma mesa enorme e muito espaço para cada mão trabalhar. Era um pouco bagunçado e gastava muito recurso.
O Novo Método QKMM (O Chef Mágico): Esse novo algoritmo é como se o chef pudesse criar uma "nuvem de ingredientes" que se transforma em sanduíches instantaneamente. Ele não precisa de uma mesa gigante para cada sanduíche; ele usa a própria natureza das partículas quânticas para fazer com que a resposta (o resultado da conta) apareça quase "sozinha" através de um fenômeno chamado Kernel.

Por que isso é importante? (A Matemática da Velocidade)

O artigo usa uma fórmula matemática para dizer que esse método é "assintoticamente ótimo".

Em termos simples: conforme a tabela de números cresce para o infinito, o esforço que o computador faz para resolvê-la cresce de forma muito, muito lenta, quase encostando no limite mínimo possível. É como se, quanto mais difícil a tarefa ficasse, mais eficiente o seu "superpoder" se tornasse.

Mas tem um porém: O "Ruído"

O artigo também faz um teste de realidade. Computadores quânticos atuais são muito sensíveis. É como tentar ler um livro enquanto alguém fica balançando a sua cadeira e acendendo e apagando as luzes (isso é o que chamamos de Ruído Quântico).

Os pesquisadores descobriram que:

O método é incrivelmente rápido e estável quando o ambiente está calmo.
Quando o "barulho" (ruído) aumenta, a precisão cai, mas o método ainda se sai melhor do que as técnicas antigas.

Resumo da Ópera

Este trabalho é como se tivéssemos encontrado uma nova maneira de organizar o trânsito de uma cidade inteira. Em vez de cada carro ter que esperar o sinal verde, um dia todos os carros poderão se mover como uma única onda fluida, chegando ao destino quase ao mesmo tempo. Isso abre caminho para que as Inteligências Artificiais do futuro sejam muito mais rápidas, poderosas e capazes de resolver problemas que hoje parecem impossíveis.

Resumo Técnico: Redução da Complexidade da Multiplicação de Matrizes para $O(N^2 \log^2 N)$ via um Algoritmo Quântico Assintoticamente Ótimo

1. O Problema

A multiplicação de matrizes é uma operação fundamental na computação clássica, sendo o núcleo de aplicações de larga escala, como o treinamento de redes neurais profundas (Deep Learning). Atualmente, o limite superior da complexidade clássica é de aproximadamente $O(N^{2.371552})$ . Embora a computação quântica ofereça paralelismo inerente, a pesquisa em Multiplicação de Matrizes Quânticas (QMM) carece de um padrão de métrica unificado (alguns usam complexidade de consultas, outros de qubits ou portas) e muitos algoritmos existentes sofrem com um alto custo de recursos (escalonamento cúbico) ou baixa capacidade de paralelismo, tornando-os inviáveis para a era NISQ (Noisy Intermediate-Scale Quantum).

2. Metodologia

Os autores propõem o Quantum Kernel-based Matrix Multiplication (QKMM). A metodologia baseia-se na decomposição da multiplicação de matrizes em operações sucessivas de produto interno (inner product) utilizando o método de módulo de produto interno de kernel quântico.

O algoritmo é estruturado em quatro níveis de extensão paralela:

V2V (Vector-to-Vector): O bloco fundamental que utiliza o método de kernel quântico para calcular o módulo do produto interno entre dois vetores sem a necessidade de qubits auxiliares extras para estabelecer relações, permitindo a leitura direta do termo de correlação do estado fundamental.
V2M (Vector-to-Matrix): Uma extensão que utiliza um registrador de índice para tratar cada linha de uma matriz como um vetor individual, permitindo a multiplicação matriz-vetor em um único circuito.
M2M (Matrix-to-Matrix): Uma extensão de dupla paralelização que utiliza dois registradores de índice (para linhas da matriz A e colunas da matriz B), permitindo o cálculo completo da multiplicação de duas matrizes em um único circuito quântico.
M-MM (Multi-Matrix Multiplication): Uma extensão que permite computar o produto de uma matriz por múltiplas matrizes simultaneamente, aproveitando a superposição quântica para processamento paralelo massivo.

A codificação de dados é feita via codificação de amplitude (amplitude encoding), mapeando vetores normalizados em estados quânticos.

3. Principais Contribuições

Complexidade Assintoticamente Ótima: O algoritmo atinge uma complexidade de portas quânticas de $O(N^2 \log^2 N)$ . Os autores provam matematicamente que, conforme $N \to \infty$ , essa complexidade aproxima-se do limite teórico inferior de $O(N^2)$ , superando o melhor algoritmo clássico conhecido.
Padronização de Métricas: O trabalho estabelece a contagem de portas quânticas básicas como a métrica fundamental para avaliação, permitindo uma comparação direta e justa entre abordagens quânticas e clássicas.
Arquitetura de Baixo Recurso: Ao contrário de métodos baseados em Swap Test ou Hadamard Test, o QKMM minimiza o uso de qubits auxiliares e evita a destruição dos qubits de dados, permitindo maior reutilização e paralelismo.

4. Resultados

Os autores validaram o algoritmo através de simulações em computadores clássicos, utilizando tanto modelos ideais (sem ruído) quanto modelos realistas de hardware supercondutor (ruído de relaxação $T_1$ , desfasamento $T_2$ e erro de porta).

Simulação Sem Ruído: Demonstrou que o tempo de computação diminui significativamente à medida que o nível de paralelismo aumenta, validando a eficiência do design para grandes dimensões.
Simulação Com Ruído (Modelo NISQ):
- Em dimensões baixas ( $N=2$ a $4$), o algoritmo mostrou alta robustez, mantendo fidelidade $> 0.95$ .
- Em dimensões maiores ( $N=8$ ), identificou-se que o ruído de porta lógica é o fator dominante de perda de fidelidade, superando o ruído ambiental ( $T_1/T_2$ ).
- O ruído combinado (interação não linear de múltiplos ruídos) causa uma queda acentuada na fidelidade, o que aponta para a necessidade de algoritmos de codificação de dados mais eficientes para mitigar o aumento da profundidade do circuito.

5. Significância

Este trabalho representa um avanço teórico e prático crucial. Ao fornecer um algoritmo que se aproxima do limite de complexidade ideal, ele abre caminho para a aceleração de tarefas de computação intensiva em IA e computação científica. Além disso, o conceito de "computação intensiva quântica" (quantum-intensive computing) introduzido pelos autores sugere um novo paradigma onde o hardware quântico não é apenas um acelerador de nicho, mas uma solução fundamental para o gargalo de processamento de modelos de inteligência artificial em larga escala.