Exact Quantum Circuit Optimization is co-NQP-hard

Resumo Técnico: Otimização Exata de Circuitos Quânticos é co-NQP-difícil

1. O Problema

O artigo aborda o problema fundamental de otimização exata de circuitos quânticos. Dado um circuito quântico $C$ (definido sobre um conjunto de portas fixo $A$), o objetivo é encontrar um circuito equivalente $C'$ (definido sobre um conjunto de portas $B$, possivelmente diferente) que minimize o consumo de um recurso quântico específico, mantendo a equivalência exata em um subespaço desejado de estados de entrada.

Os autores focam em quatro tipos de recursos a serem minimizados:

1. Contagem/Profundidade total de portas (qualquer porta).
2. Contagem/Profundidade de portas não-Clifford (ex: portas $T$).
3. Contagem/Profundidade de portas que geram superposição (ex: portas $H$).
4. Contagem/Profundidade de portas que geram emaranhamento (ex: portas $CX$).

A equivalência é definida como exata (não aproximada) em um subespaço específico, o que é crucial para a canonicidade de circuitos e otimizações composicionais sem acúmulo de erros de aproximação.

2. Metodologia e Abordagem

Para estabelecer a dureza computacional do problema, os autores utilizam uma abordagem baseada em reduções de Karp e complexidade quântica:

• Definição de um Problema de Promessa Intermediário: Os autores introduzem o problema Promise-IsIdentity(A).
  • Entrada: Um circuito $C$ e uma string de bits $x$.
  • Promessa: Ou $U_C |x\rangle = |x\rangle$ (o circuito age como identidade), ou $U_C |x\rangle$ é um estado de superposição que exibe correlações não-affines (uma propriedade que requer recursos não-Clifford).
  • Questão: O circuito age como identidade?
• Construção de um "Gadget" (Dispositivo): Eles constroem um circuito baseado no algoritmo Deutsch-Josza, denotado como $Q(G, \phi)$.
  • Este gadget utiliza um circuito $G$ arbitrário e uma fórmula booleana $\phi$.
  • Se $\phi$ for balanceado, o gadget age como identidade.
  • Se $\phi$ não for balanceado, o gadget aplica $G$ e gera um estado de superposição com correlações não-affines.
• Redução: Eles reduzem o problema clássico IsBalanced (determinar se uma fórmula booleana tem o mesmo número de atribuições satisfatórias e insatisfatórias) para o problema de otimização.
  • O problema IsBalanced é conhecido por ser completo para a classe $C_=P$, que é equivalente a co-NQP.
  • Ao mostrar que resolver a otimização exata permitiria distinguir entre os casos de identidade e superposição não-affine, eles provam que a otimização é pelo menos tão difícil quanto IsBalanced.

3. Principais Contribuições

1. Estabelecimento de Limites Inferiores (Lower Bounds): O trabalho demonstra que a otimização exata de circuitos quânticos, para qualquer conjunto de portas capaz de implementar as portas $H$ (Hadamard) e $TOF$ (Toffoli) exatamente, é co-NQP-difícil.
2. Generalização de Recursos: Diferente de trabalhos anteriores que focavam apenas no tamanho do circuito ou em contagens específicas de portas (como $T$-count) sobre o espaço de estados completo, este trabalho generaliza a dureza para:
   • Minimização de recursos não-Clifford.
   • Minimização de recursos de superposição.
   • Minimização de recursos de emaranhamento.
3. Refinamento da Hierarquia de Complexidade: O resultado preenche a lacuna entre o limite inferior de NP-dificuldade (estabelecido em trabalhos recentes para o espaço de estados completo) e o limite superior conhecido de $NPNQP$. O resultado mostra que o problema está provavelmente fora da Hierarquia Polinomial (PH), a menos que a PH colapse.

4. Resultados Chave

• Teorema 1: Para qualquer conjunto de portas $A$ que implemente $H$ e $TOF$ exatamente, o problema Promise-IsIdentity(A) é co-NQP-difícil.
• Corolário 1: O problema de Otimização Exata (minimizar contagem ou profundidade de portas não-identidade, não-Clifford, de superposição ou de emaranhamento) é co-NQP-difícil.
  • Isso se aplica mesmo se o algoritmo de otimização puder usar qubits auxiliares (ancillae) limpos ou emprestados.
  • Aplica-se a conjuntos de portas comuns, como Clifford+T e conjuntos usados em plataformas de hardware reais.
• Implicação Específica: Minimizar o número de portas $T$ (T-count) em circuitos Clifford+T, considerando equivalência em um subespaço, é co-NQP-difícil.

5. Significado e Impacto

• Barreira Teórica: O resultado indica que não existem algoritmos eficientes (dentro da Hierarquia Polinomial) para resolver a otimização exata de circuitos quânticos de forma geral. Isso sugere que a otimização automática de circuitos quânticos para vantagem prática é um problema intrinsecamente difícil.
• Relevância Prática: Como os recursos quânticos (qubits, portas não-Clifford, profundidade) são escassos e caros devido a taxas de erro, a dificuldade de encontrar o circuito ótimo exato reforça a necessidade de heurísticas, aproximações ou otimizações restritas a casos específicos, em vez de soluções gerais perfeitas.
• Complemento à Literatura: O trabalho complementa resultados anteriores que mostravam dureza NP para o espaço de estados completo, elevando o limite de dificuldade para uma classe de complexidade quântica mais alta (co-NQP) quando se considera subespaços e recursos específicos.

Em resumo, o artigo prova que a busca pela otimização perfeita de circuitos quânticos, considerando a minimização de recursos críticos como emaranhamento e portas não-Clifford, é um problema computacionalmente intratável para classes de complexidade clássicas padrão, situando-se fora da Hierarquia Polinomial.