Resumo Técnico: Sobre a Dificuldade da Membrosia Aproximada de Circuitos Quânticos e Otimização

1. Definição do Problema

O artigo investiga a complexidade computacional de dois problemas fundamentais na teoria de circuitos quânticos: Membrosia Aproximada e Otimização Aproximada.

• Membrosia Aproximada ($\text{ApproxMember}$): Dado um circuito quântico $C$ sobre um conjunto de portas $G$, um conjunto de unitárias $S$, uma métrica de distância $m$ e uma tolerância $\epsilon$, decida se existe uma unitária $U \in S$ tal que a distância $d_m(C, U) \le \epsilon$.
  • Um caso especial é a Identidade Aproximada ($\text{ApproxId}$), onde $S = \{I\}$.
  • O artigo considera três conjuntos específicos para $S$:
    1. $S = \{I\}$ (Identidade).
    2. $S \subseteq S_{\text{Cliff}}$ (Unitárias implementáveis por circuitos de Clifford).
    3. $S \subseteq S_{\text{GP}}$ (Matrizes de Permutação Generalizadas, ou seja, unitárias que não criam superposição).
• Otimização Aproximada ($\text{ApproxOpt}$): Dado um circuito $C$, uma função de custo $f$ e um orçamento $k$, decida se existe um circuito equivalente $C'$ tal que $d_m(C, C') \le \epsilon$ e $f(C') \le k$. A função de custo $f$ é caracterizada pelo seu "conjunto livre" $S_f = \{U_{C'} \mid f(C') = 0\}$.

O estudo foca em entradas sem promessa (promise-free), contrastando com o trabalho anterior de Janzing, Wocjan e Beth (2005), que estabeleceu a QMA-completude para o problema de "verificação de não-identidade" sob uma promessa de que o circuito está próximo ou longe da identidade. Este trabalho remove essa promessa, questionando se o problema permanece difícil quando a distância do circuito de entrada para o conjunto alvo é desconhecida.

Os autores analisam três métricas padrão para medir a distância entre unitárias:

1. Métrica de Seno (Sine Metric): Baseada no traço, capturando diferenças de caso médio ($d_{\text{Sine}}$).
2. Métrica Espectral (Spectral Metric): Baseada na norma do operador, capturando diferenças de pior caso ($d_{\text{sp}}$).
3. Métrica de Operador (Operator Metric): A versão da métrica espectral invariante à fase global ($d_{\text{op}}$).

2. Metodologia

Os autores estabelecem a dificuldade reduzindo a classe de complexidade PP (Tempo Polinomial Probabilístico) ao problema de membresia aproximada. O núcleo de sua metodologia envolve as seguintes etapas:

1. Problema de Origem: Eles utilizam o AtMostSat, um problema PP-difícil que pergunta se uma fórmula proposicional $\phi$ é satisfeita por, no máximo, uma fração $\beta$ de suas atribuições. Eles introduzem uma versão com promessa, PromiseAtMostSat, onde a fração de atribuições satisfatórias é prometida como sendo no máximo $\kappa$.
2. Redução de Promessa para Aproximação: Eles provam que o PromiseApproxId (verificar se um circuito está $\epsilon$-próximo da identidade sob a promessa de que ele é $\tau$-próximo) é PP-difícil. Isso é alcançado construindo circuitos Clifford+T a partir de fórmulas $\phi$ de modo que a distância $d_m(I, C)$ seja uma função estritamente crescente $g(\gamma(\phi))$ da fração de satisfação $\gamma(\phi)$.
   • Para a métrica de Seno, eles constroem um circuito implementando uma operação controlada-XOR ($|x\rangle|b\rangle \mapsto |x\rangle|b \oplus \phi(x)\rangle$).
   • Para as métricas Espectral e de Operador, eles utilizam a iteração de Grover para construir circuitos com ângulos de autovalores dependentes de $\gamma(\phi)$. Para a métrica de operador, eles empregam produtos tensoriais desses circuitos para controlar o comprimento de arco dos ângulos de autovalores no círculo unitário.
3. Removendo a Promessa:
   • Caso $S = \{I\}$: A dificuldade da versão com promessa implica diretamente a dificuldade da versão sem promessa para os intervalos específicos de $\epsilon$.
   • Caso $S \subseteq S_{\text{Cliff}}$: Eles utilizam um argumento de desigualdade triangular (Lema 6). Eles mostram que para $\epsilon$ suficientemente pequeno (especificamente $\epsilon < \sqrt{2}/4$), se um circuito $C$ tem a promessa de estar próximo de $I$, os únicos elementos em $S_{\text{Cliff}}$ que podem estar $\epsilon$-próximos de $C$ são aqueles à distância 0 de $I$ (ou seja, $I$ propriamente dito). Isso se baseia em limitar inferiormente a distância mínima não nula entre $I$ e qualquer outra unitária de Clifford.
   • Caso $S \subseteq S_{\text{GP}}$: Eles constroem circuitos específicos onde a distância para o conjunto de matrizes de permutação generalizadas é exatamente a distância para a identidade para pequenos valores de $\gamma(\phi)$, permitindo uma redução direta do problema de promessa. Esta redução aplica-se especificamente quando a identidade $I$ está incluída no conjunto $S$ (ou seja, $I \in S \subseteq S_{\text{GP}}$).

3. Principais Contribuições e Resultados

Teorema Principal (Teorema 1)

O artigo prova que ApproxMember é PP-difícil para uma ampla gama de parâmetros, desde que o conjunto de portas $G$ possa implementar exatamente Clifford+T. A dificuldade mantém-se para:

• Conjuntos $S$: $S=\{I\}$, $I \in S \subseteq S_{\text{Cliff}}$, e $I \in S \subseteq S_{\text{GP}}$.
• Métricas: Métricas de Seno, Espectral e de Operador.
• Tolerância $\epsilon$:
  • Para $S=\{I\}$ e métricas baseadas em traço (Seno): PP-difícil para todo $0 < \epsilon < 1$ (o diâmetro total).
  • Para $S=\{I\}$ e métricas Espectral/de Operador: PP-difícil para todo $0 < \epsilon < 2$.
  • Para $I \in S \subseteq S_{\text{Cliff}}$: PP-difícil para $0 < \epsilon < \sqrt{2}/4 \approx 0.3536$.
  • Para $I \in S \subseteq S_{\text{GP}}$: PP-difícil para $0 < \epsilon < 1$ (Seno) e $0 < \epsilon < \sqrt{2}$ (Espectral/Operador).

Corolário 1 (Dificuldade de Otimização)

Os resultados implicam diretamente que ApproxOpt é PP-difícil para minimizar a profundidade total de portas/contagem de portas, profundidade de portas não-Clifford/contagem de portas, e profundidade de portas de superposição/contagem de portas, dentro dos respectivos intervalos de $\epsilon$.

Descobertas Técnicas Específicas

1. Dificuldade para Portas Clássicas-Reversíveis: Mesmo quando o conjunto de portas $G$ consiste apenas em portas clássicas-reversíveis (ex: X, CNOT, Toffoli) que não podem criar superposição, o problema ApproxId sob a métrica de Seno permanece PP-difícil para todo $0 < \epsilon < 1$.
2. Robustez: Os resultados de dificuldade generalizam-se para qualquer medida de distância derivada das métricas de Seno, Espectral ou de Operador via uma função estritamente crescente. Além disso, os problemas permanecem PP-difíceis mesmo se o objetivo for apenas aproximar o custo mínimo dentro de qualquer fator (constante ou não), pois a dificuldade se mantém quando o custo ótimo é 0.
3. Comparação com Trabalho Anterior: O artigo fortalece o resultado de Janzing, Wocjan e Beth (2005). Enquanto o resultado deles mostrou a QMA-completude para o problema de promessa de verificação de não-identidade, este trabalho mostra que o problema sem promessa é PP-difícil (uma classe presumidamente mais difícil que QMA) para um conjunto mais amplo de métricas e conjuntos $S$.

4. Significância e Alegações

Os autores alegam que seus resultados demonstram que a otimização aproximada de circuitos quânticos é fundamentalmente mais difícil sobre entradas sem promessa comparado à QMA-completude da verificação de não-identidade baseada em promessa.

• Independência de Recursos: A dificuldade persiste independentemente dos recursos quânticos disponíveis (quaisquer portas, portas não-Clifford ou superposição).
• Independência de Métrica: A dificuldade mantém-se através de várias métricas de distância (baseadas em traço, espectrais ou de operador).
• Implicações Práticas: Como os conjuntos de portas padrão (como Clifford+T) satisfazem as condições, esses resultados de dificuldade aplicam-se diretamente a tarefas reais de compilação e otimização quântica. Os resultados indicam que encontrar um circuito aproximadamente equivalente com custo mínimo (por exemplo, contagem de T ou profundidade mínima) é intratável para computadores clássicos, mesmo permitindo erros de aproximação, a menos que a tolerância de erro seja trivialmente grande (excedendo o diâmetro do espaço métrico).

O artigo conclui observando problemas abertos relativos à complexidade para valores maiores de $\epsilon$ (especificamente $\epsilon \ge \sqrt{2}/4$ para conjuntos de Clifford e $\epsilon \ge \sqrt{2}$ para conjuntos de permutação) e limites superiores correspondentes, embora note que, para conjuntos de portas algébbricas e a métrica de Seno em $\epsilon = \sqrt{2}/2$, o problema é PP-completo.