Probabilistic Links Between Quantum Classification of Patterns of Boolean Functions and Hamming Distance

Resumo Técnico: Vínculos Probabilísticos entre a Classificação Quântica de Padrões de Funções Booleanas e a Distância de Hamming

Enunciado do Problema
Algoritmos de classificação quântica, como o algoritmo de Deutsch-Jozsa e suas extensões, são projetados para classificar perfeitamente funções booleanas que satisfazem "promessas" específicas (ex: serem constantes ou balanceadas) com uma probabilidade de 1,0. No entanto, existe uma lacuna significativa na compreensão do comportamento desses algoritmos quando apresentados a funções desconhecidas que caem fora da classe prometida. Enquanto a literatura anterior focou em distinguir classes específicas ou em utilizar métricas de distância alternativas (como distâncias baseadas em clusters), há uma carência de análise rigorosa sobre como os classificadores quânticos se comportam quando a função de entrada é meramente "próxima" da classe alvo. Este artigo aborda o desafio de determinar se informações úteis podem ser extraídas de uma função booleana desconhecida e não classificável $h$ ao identificar seus "vizinhos mais próximos" dentro de uma classe perfeitamente classificável $F_{P_n}$, utilizando a distância de Hamming como a métrica de proximidade.

Metodologia
Os autores empregam um framework que combina computação quântica, teoria da informação e combinatória, conceituado através de um "Jogo de Kets de Base Mais Próximo" estratégico entre dois jogadores, Alice e Bob.

1. Framework Teórico:

   • Vetores de Bits de Padrão: Funções booleanas são mapeadas para vetores de bits de padrão únicos de comprimento $2^n$, estabelecendo uma bijeção entre funções e vetores.
   • Bases de Padrão e Classes: O estudo utiliza "bases de padrão" ($P_n$), conjuntos de vetores de padrão ortogonais, que definem classes de funções booleanas perfeitamente classificáveis ($F_{P_n}$).
   • Construção do Classificador: Classificadores quânticos ($G$) são construídos como produtos tensoriais de classificadores elementares: a transformada de Hadamard ($H$) e um classificador específico ($C_2$) derivado da razão de desequilíbrio das bases $Q_2$.
   • Métrica de Distância: A distância de Hamming ($d_H$) é definida entre os vetores de bits de padrão da função desconhecida $h$ e as funções na classe $F_{P_n}$. Os "vizinhos mais próximos" são aquelas funções na classe com a distância de Hamming mínima em relação a $h$.

2. Abordagem Experimental:

   • Simulação: Experimentos extensivos foram conduzidos usando Qiskit para simular circuitos quânticos implementando o Esquema de Classificação de Base de Padrão.
   • Escopo:
     • Enumeração Exaustiva: Para escalas menores (vetores de padrão de comprimento 8 e 16), todas as funções booleanas possíveis foram enumeradas para garantir certeza estatística.
     • Amostragem Aleatória: Para escalas maiores (comprimentos 32 e 64), onde a enumeração exaustiva é computacionalmente proibitiva, uma estratégia de amostragem aleatória estatisticamente robusta foi empregada.
   • Métrica: A métrica primária analisada é o "limiar de classificação" ($\vartheta$), definido como a probabilidade de o resultado da medição da função desconhecida $h$ corresponder a um de seus kets de base mais próximos.

Principais Resultados
Os resultados experimentais revelam uma relação forte, embora sutil, entre a distância de Hamming e a probabilidade de classificação:

1. Decréscimo Monotônico: Para a vasta maioria das classes de funções, o limiar de classificação é uma função monotonicamente decrescente da distância de Hamming. À medida que a função desconhecida $h$ se desvia mais da classe $F_{P_n}$, a probabilidade de identificar corretamente um vizinho mais próximo cai.
2. Três Intervalos Distintos: Os autores estabelecem intervalos precisos para a distância de Hamming que delimitam a probabilidade de classificação:
   • Intervalo de Alta Confiança ($1$a$2^n/8$): O limiar de classificação permanece estritamente acima de 0,50, permitindo afirmar com confiança que a medição provavelmente corresponde a um vizinho mais próximo.
   • Intervalo de Transição ($2^n/8 + 1$ a $2^n/2 - 1$): O limiar permanece positivo, mas diminui constantemente em direção a 0,00.
   • Intervalo de Baixa Confiança ($2^n/2$ a $2^n$): O limiar é efetivamente 0,00, indicando que a função não é um vizinho mais próximo.
3. Exceções Sistêmicas (Heterogeneidade Intra-classe): Uma desviação significativa da tendência monotônica foi observada em classes formadas pelo produto estendido da base $Q_2$ ($F_{Q_2}^{\otimes m}$). Nestas classes específicas, a probabilidade de classificação sofre um pico para exatamente 1,0 em uma distância de Hamming específica ($\varrho$), em vez de permanecer em 0,00. Esta anomalia não é aleatória, mas uma consequência previsível da razão fixa de 0s e 1s inerente a essas classes de funções específicas.

Significância e Contribuições
O artigo reivindica diversas contribuições inovadoras para o campo do aprendizado de máquina quântico e classificação:

• Validação da Distância de Hamming: O trabalho valida robustamente a distância de Hamming como uma métrica crítica e eficaz para verificar ou desqualificar candidatos a vizinhos mais próximos, mesmo quando a entrada está fora da classe prometida.
• Quantificação de Irregularidades: O estudo demonstra que os desvios da tendência monotônica esperada não são artefatos estatísticos, mas sim sistêmicos e previsíveis. Especificamente, os autores quantificam o "pico" de probabilidade para as classes $F_{Q_2}^{\otimes m}$, transformando uma potencial fonte de erro em um fenômeno gerenciável e bem compreendido.
• Limites Probabilísticos: Tanto quanto o conhecimento dos autores, este é o primeiro trabalho a demarcar intervalos de distância de Hamming precisos que delimitam os valores possíveis da probabilidade de classificação.
• Framework Prático para Tomada de Decisão: As descobertas fornecem aos praticantes uma ferramenta fundamental para avaliação probabilística. Usuários agora podem:
  1. Endossar resultados de classificação com alta certeza quando a distância de Hamming cai dentro do intervalo de alta confiança.
  2. Descartar resultados com confiança quando a distância cai dentro do intervalo de baixa confiança.
• Insight Teoria dos Jogos: O "Jogo de Kets de Base Mais Próximo" serve como um framework conceitual para ilustrar esses limites probabilísticos, mostrando como a interação entre distância e probabilidade cria vantagens estratégicas tanto para o "Alice" (o classificador) quanto para o "Bob" (o selecionador de funções), destacando particularmente a justiça do jogo quando Bob seleciona funções na distância de limiar crítica ($2^n/8$).

Em resumo, o artigo estabelece que, embora os classificadores quânticos sejam projetados para entradas específicas "prometidas", seu comportamento em entradas não classificáveis não é ruído aleatório, mas segue uma estrutura probabilística previsível governada pela distância de Hamming, com exceções quantificáveis específicas para certas classes estruturadas.