⚛️ quantum physics

MOSAIQC: Mixed-topology-aware Optimization for Scalable Approximate noise-Informed Quantum circuit Cutting

O MosaiQC é um novo framework que emprega um warmstart híbrido com otimização de refinamento e um resolvedor de atribuição quadrática aproximada rápido para permitir partições de hardware de topologia mista e tamanho misto, melhorando significativamente a fidelidade local enquanto reduz drasticamente o tempo de execução e o overhead de amostragem para o corte de circuitos quânticos escalonável.

Autores originais: Koen Mesman, Yinglu Tang, Matthias Moller, Boyang Chen, Sebastian Feld

Publicado 2026-07-22

📖 4 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Koen Mesman, Yinglu Tang, Matthias Moller, Boyang Chen, Sebastian Feld

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

Imagine que você está tentando resolver um quebra-cabeça gigante e impossível, mas só tem uma mesa minúscula para trabalhar. Você não consegue colocar o quadro inteiro na mesa de uma só vez, então tem que dividir o quebra-cabeça em pedaços menores, resolver cada pedaço na sua mesa pequena e depois tentar colá-los de volta para ver a imagem final. Este é o drama diário dos cientistas que trabalham com computadores quânticos. Essas máquinas são incrivelmente poderosas, mas atualmente são muito pequenas e frágeis; elas possuem poucos "qubits" (as peças do quebra-cabeça) para lidar com os enormes problemas que queremos que elas resolvam, e são facilmente perturbadas pelo ruído, como um espirro arruinando uma pilha delicada de cartas.

Para contornar isso, os cientistas usam um truque chamado circuit cutting (corte de circuito). É como pegar aquele quebra-cabeça gigante, fatiá-lo em seções gerenciáveis, resolver cada seção em uma mesa pequena diferente (ou até em computadores diferentes) e depois usar uma receita matemática especial para remontar as respostas. No entanto, há uma pegadinha: toda vez que você corta o quebra-cabeça, a receita para colá-lo de volta torna-se exponencialmente mais difícil e exige que você tire milhões de fotos das peças para obter a imagem correta. Se você fizer cortes demais, o esforço para colá-las de volta torna-se tão grande que anula o propósito. A grande questão é: Onde exatamente devemos fazer os cortes para manter as peças do quebra-cabeça pequenas o suficiente para serem resolvidas, mas sem fazer tantos cortes que o processo de colagem demore uma eternidade?

É aqui que um novo framework chamado MosaiQC entra em cena. Pense no MosaiQC como um mestre de quebra-cabeças superinteligente e hiperorganizado que não apenas fatia o quebra-cabeça aleatoriamente. Em vez disso, ele observa a forma das peças, o tamanho das mesas disponíveis e até o quanto cada mesa é instável (o "ruído"). Ele usa uma mistura inteligente de estratégias para encontrar os pontos perfeitos para o corte. Primeiro, ele faz um palpite rápido e aproximado de onde cortar (como um aquecimento). Em seguida, ele refina esse palpite testando pequenos movimentos, trocando as peças de lugar para ver se o quebra-cabeça se encaixa melhor. Crucialmente, ele não se importa apenas com quantos cortes faz; ele também se importa com onde as peças caem. Se uma mesa estiver bamba, o MosaiQC tenta colocar as peças mais importantes e frágeis na mesa mais robusta para evitar erros.

O artigo mostra que este novo método é um divisor de águas. Quando os pesquisadores testaram o MosaiQC contra métodos antigos, descobriram que ele era 2,88 vezes mais rápido em descobrir onde cortar. Mais importante ainda, ele reduziu o número de cortes necessários em uma média de 16,84%, o que parece pouco, mas na verdade significa que o esforço de "colagem" (o overhead de amostragem) caiu por um fator impressionante de 5,38 × 10¹¹. Isso é como passar de precisar tirar uma foto de cada grão de areia em uma praia para apenas tirar uma foto da praia inteira de uma só vez. Além disso, ao prestar atenção em qual hardware é mais "ruidoso", o MosaiQC melhorou a precisão final dos resultados em cerca de 19,56% em comparação aos métodos padrão.

Os autores fazem questão de notar que, embora o MosaiQC torne o planejamento dos cortes muito mais rápido e melhor, o problema fundamental de colar as peças de volta ainda exige muito esforço se os cortes forem numerosos demais. No entanto, ao encontrar melhores cortes e posicioná-los no melhor hardware, o MosaiQC sugere que podemos resolver problemas quânticos muito maiores do que antes, sem ficarmos presos em um gargalo de compilação. Ele prova que uma abordagem inteligente e flexível — que mistura diferentes tipos de cortes e se adapta a diferentes tamanhos de hardware — pode tornar o impossível um pouco mais possível, pavimentando o caminho para que os computadores quânticos enfrentem desafios do mundo real mesmo antes de crescerem para tamanhos massivos.

Resumo Técnico: MOSAIQC

Declaração do Problema

Os computadores quânticos atuais, particularmente na era NISQ (Noisy Intermediate-Scale Quantum), carecem dos recursos de qubits e da fidelidade necessários para executar a maioria dos algoritmos práticos. Para contornar essas limitações de hardware, o "corte de circuitos quânticos" (ou circuit knitting) surgiu como uma técnica para dividir grandes algoritmos em partições menores executáveis em hardware disponível. No entanto, esta abordagem introduz um overhead de amostragem significativo que escala exponencialmente com o número de cortes necessários para a reconstrução exata do estado.

Os frameworks de otimização existentes para determinar a localização dos cortes enfrentam várias limitações críticas:

Escalabilidade: Métodos exatos (ex: Programação Inteira Mista, solvers SMT) frequentemente exibem complexidade computacional fatorial ou exponencial, tornando-os inviáveis para circuitos que se aproximam do regime de mil qubits.
Limitações de Tipo de Corte: Muitas heurísticas otimizam cortes de fios (wire cuts) ou cortes de portas (gate cuts) isoladamente, raramente combinando ambos dentro de um único procedimento de otimização.
Consciência de Hardware: A maioria das abordagens assume partições de hardware homogêneas e negligencia as características específicas de ruído e restrições de conectividade de backends quânticos heterogêneos, levando a uma fidelidade de execução subótima.
Compromissos (Trade-offs): Equilibrar a minimização do overhead de amostragem com a maximização da fidelidade de hardware (redução de ruído) é um problema multiobjetivo complexo que as heurísticas escaláveis existentes frequentemente falham em abordar conjuntamente.

Metodologia

O artigo apresenta o MosaiQC, um framework de otimização heurística projetado para otimizar conjuntamente o overhead de amostragem, o posicionamento consciente de hardware e cortes mistos de portas/fios, mantendo uma complexidade de tempo polinomial. O framework opera através de um pipeline de otimização hierárquico de quatro estágios:

1. Representação em Grafo

Para reduzir o overhead computacional, o circuito quântico e a topologia do hardware são transformados em representações de grafo compactas, em vez de depender de avaliações repetidas de Grafos Acíclicos Dirigidos (DAG).

Grafo de Conectividade: Representa os qubits como nós e as portas de 2 qubits como arestas, ponderadas pela contagem de portas.
Dependências Temporais: Armazenadas separadamente para avaliar eficientemente os cortes de fios quando as partições compartilham qubits.
Topologia de Hardware: Modelada como um grafo ponderado onde os pesos das arestas incorporam métricas de ruído (ex: erros de porta $1-q$ e $2-q$ ) e custos de roteamento (estimados via caminhos mais curtos de Floyd-Warshall).

2. Particionamento Inicial (Warm-Start)

O framework utiliza a biblioteca METIS para realizar o particionamento global do grafo. Este passo gera uma solução inicial que satisfaz as restrições de capacidade de hardware, fornecendo um ponto de partida de alta qualidade para o refinamento subsequente. Este estágio aborda primariamente cortes de portas ou cortes de fios individualmente para estabelecer uma linha de base.

3. Refinamento Local

Um algoritmo de Busca Tabu (Tabu Search) refina iterativamente o particionamento inicial através de movimentos locais:

Adição de nós às partições (sujeito à capacidade).
Movimentação de nós entre partições.
Troca (swap) de nós nas fronteiras das partições.
Avaliação de Corte Misto: A função de custo considera explicitamente tanto os cortes de portas quanto os de fios. O overhead é calculado como $Overhead = (GateCost)^g \cdot 16^w$ , onde $g$ e $w$ são as contagens de cortes de portas e fios, respectivamente. Para otimizar a computação, o logaritmo deste custo é utilizado durante a busca.
Estratégia de Avaliação Local: Em vez de reavaliar o grafo global, o framework utiliza uma estratégia de busca de corte de fios local baseada em representações de grafos ao nível de qubit, reduzindo significativamente a complexidade para $O((a+1)p \log p)$ para partições sobrepostas.

4. Atribuição de Hardware Consciente

Para otimizar a fidelidade de execução, o MosaiQC emprega um solver de Problema de Atribuição Quadrática (QAP) usando o algoritmo de Frank-Wolfe.

Objetivo: Encontrar uma matriz de permutação que mapeie as partições do circuito para os backends de hardware para maximizar a fidelidade esperada (minimizar o ruído).
Pontuação: O algoritmo minimiza o traço do produto da matriz da partição do circuito pela matriz de topologia de ruído do hardware. Os pesos de ruído são transformados logaritmicamente ( $w = \ln(1 - \epsilon_{noise})$ ) para lidar com diferentes escalas de forma eficaz.
Função de Custo Adaptativa: Para equilibrar o custo computacional das avaliações de QAP com a qualidade da otimização, o framework utiliza uma função de custo adaptativa ( $S_{adapt}$ ) que normaliza o overhead de corte contra a pontuação de posicionamento QAP. As avaliações de QAP são realizadas em intervalos definidos, em vez de a cada iteração.

Principais Contribuições

O artigo reivindica as seguintes contribuições específicas:

Framework de Otimização Conjunta: Um framework heurístico que otimiza cortes mistos de fios e portas dentro de um único procedimento, uma capacidade raramente demonstrada em ferramentas escaláveis existentes.
Avaliação de Corte de Fio Local: Uma estratégia baseada em representações de grafos ao nível de qubit que reduz a complexidade computacional de otimções repetidas baseadas em DAG.
Suporte a Hardware Heterogêneo: Uma camada de abstração que suporta backends quânticos com variadas capacidades de qubits e características de ruído, permitindo partições de hardware de tamanhos mistos.
Posicionamento Consciente de Hardware: Um método usando correspondência de grafos duplamente ponderada (resolvido via Frank-Wolfe) para posicionar partições em hardware, otimizando explicitamente para redução de ruído.
Estratégia Híbrida Escalável: Uma combinação de particionamento global via METIS para inicialização warm-start e refinamento por Busca Tabu local, alcançando complexidade de tempo polinomial $O(k \cdot n_q + m \cdot n_q^3)$ .

Resultados

O framework foi avaliado contra o add-on de corte de circuitos do Qiskit (usando o algoritmo de Dijkstra) e métodos de busca exaustiva através de vários benchmarks (ex: Adder, BV, AQFT, QAOA, VQE) e tamanhos de circuito (6 a 1000 qubits).

Desempenho de Tempo de Execução: O MosaiQC alcançou um ganho de velocidade de 2,88× (média geométrica) no tempo de execução em comparação com a linha de base. Crucialmente, ele otimizou com sucesso circuitos de até 1000 qubits, enquanto a linha de base frequentemente sofria timeouts ou estouros de memória.
Overhead de Amostragem: O framework demonstrou uma redução média de 16,84% no número de cortes em comparação com a linha de base. Isso resultou em uma melhoria da média geométrica no overhead de amostragem de aproximadamente $5,38 \cdot 10^{11}\times$ (devido à natureza exponencial do overhead).
Melhoria de Fidelidade: A estratégia de posicionamento consciente de hardware mostrou uma forte correlação de Pearson ( $r \approx 0,83 - 0,87$ ) entre a pontuação QAP e a fidelidade medida. Nos testes de fidelidade, o MosaiQC alcançou uma melhoria de fidelidade local média de +19,56% ± 6,17% sobre a linha de base quando o peso do ruído foi priorizado.
Convergência: A abordagem híbrida de warm-start reduziu significavelmente o número de iterações necessárias para a convergência em comparação com abordagens de apenas refinamento, evitando que o otimizador ficasse preso em mínimos locais precocemente.

Significância e Alegações

Os autores posicionam o MosaiQC como uma evolução necessária nas ferramentas de compilação quântica. Eles afirmam que, à medida que os circuitos quânticos escalam em direção ao regime de mil qubits, a otimização do posicionamento do corte deve deixar de ser um gargalo computacional.

O artigo assegura que o MosaiQC demonstra um equilíbrio superior entre velocidade de execução e qualidade da solução, adicionando recursos fundamentais (cortes mistos, suporte a hardware heterogêneo e posicionamento consciente de ruído) que são excluídos pela maioria dos concorrentes. Embora reconheçam que o corte de circuitos prático continua fundamentalmente limitado pelo overhead de amostragem exponencial necessário para a reconstrução, os autores argumentam que o MosaiQC estabelece uma base prática para o corte de circuitos escalável em futuros sistemas de computação quântica heterogênea. O trabalho sugere que a otimização heurística escalável pode reduzir substancialmente o overhead computacional do posicionamento de cortes de circuitos, permitindo a execução de algoritmos que seriam de outra forma inviáveis nos hardwares atuais.