One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem

Resumo Técnico: Algoritmos Quânticos de Uma Consulta para o Problema do Subgrupo Oculto Indexado-q

Definição do Problema
O artigo aborda o papel da estrutura algébrica, especificamente a Transformada de Fourier Quântica (QFT), em algoritmos de consulta quântica. O foco recai sobre o Problema do Subgrupo Oculto (HSP) para grupos abelianos finitos. Os autores introduzem uma variante específica denominada HSP indexado-$q$. Neste problema, uma função oráculo $f: G \to X$ oculta um subgrupo $H \le G$. A promessa é que o índice do subgrupo, $[G:H]$, seja igual a $1$ (significando $H=G$) ou um inteiro conhecido $q > 1$. O objetivo é duplo:

1. Decisão: Determinar se o índice é $1$ ou $q$.
2. Identificação: Se possível, identificar exatamente o subgrupo oculto $H$ utilizando uma única consulta ao oráculo.

Os autores distinguem entre a estrutura algébrica necessária para o sucesso do algoritmo e a implementação específica em nível de portas (por exemplo, circuitos baseados em qubits). Eles observam que, embora a QFT seja central para algoritmos emblemáticos como os de Shor e Simon, sua necessidade nem sempre é clara em contextos mais simples, como no algoritmo de Deutsch–Jozsa (DJ).

Metodologia
Os autores desenvolvem um quadro unificado que generaliza o algoritmo de Deutsch–Jozsa–Høyer (DJH) e o algoritmo de Bernstein–Vazirani (BV), contrastando-os com a abordagem padrão de Shor–Kitaev.

1. Separação entre Estrutura e Implementação: Os autores argumentam que o algoritmo DJ não requer inerentemente uma estrutura de grupo no domínio ou uma QFT. Em vez disso, exige uma unitária $V$ cuja primeira coluna seja uma "superposição democrática" (amplitudes uniformes). Isso permite que o algoritmo distinga entre funções constantes e balanceadas sem assumir que o domínio é um grupo.

2. O Algoritmo Indexado-$q$:

   • Configuração: O algoritmo opera no espaço de Hilbert $\mathbb{C}^G$. Inicia-se com o estado do caráter trivial $|\rho_0\rangle$ na base dos caracteres.
   • Pré-processamento: Aplica-se uma QFT inversa ($F^\dagger$) para criar uma superposição uniforme sobre $G$.
   • Consulta ao Oráculo: Implementa-se um oráculo de fase. Utilizando o truque "deslocamento-para-fase" (Seção II.A), o oráculo de deslocamento $U_f^{\text{shift}}$ é convertido em um oráculo de fase $U_f^{\text{phase}}$ usando um caráter não trivial $\chi$ do contradomínio $X$. O estado torna-se $\sum_g \chi(f(g)) |g\rangle$.
   • Pós-processamento: Aplica-se uma QFT ($F$) ao grupo $G$. O estado resultante é a transformada de Fourier da função $\chi \circ f$.
   • Medição: Uma medição na base dos caracteres produz um caráter $\rho$. O algoritmo produz como saída o subgrupo $H' = \ker \rho$.

3. Condições para Identificação Exata:
   Para que a consulta única identifique $H$ com certeza (ou seja, $\ker \rho = H$), condições específicas devem ser atendidas:

   • O grupo quociente $G/H$ deve ser cíclico de ordem $q$ (ou trivial se o índice for 1).
   • O alfabeto de saída $X$ deve ser equipado com uma estrutura compatível com $\mathbb{Z}/q\mathbb{Z}$, até um reetiquetamento afim (automorfismo e deslocamento constante).
   • O caráter $\chi$ usado para o oráculo de fase deve ser fiel na imagem de $f$.

Principais Contribuições e Resultados

• Decisão Incondicional: O artigo apresenta um algoritmo de consulta única que sempre distingue entre índice $1$ e índice $q$ para qualquer estrutura abeliana no contradomínio $X$. Isso generaliza a capacidade de decisão do DJH.
• Identificação Exata para Pequenos $q$: Os autores provam que, para $q \in \{2, 3\}$, as condições para identificação exata são satisfeitas automaticamente, independentemente de como o alfabeto de saída $X$ seja rotulado.
  • Para $q=2$, qualquer rotulagem de um conjunto de 2 elementos é compatível com $\mathbb{Z}/2\mathbb{Z}$ até uma troca (automorfismo).
  • Para $q=3$, qualquer rotulagem de um conjunto de 3 elementos é compatível com $\mathbb{Z}/3\mathbb{Z}$ até automorfismos e deslocamentos.
  • Consequentemente, os HSPs indexados-2 e indexados-3 podem ser resolvidos com identificação exata em uma única consulta, sem promessas adicionais sobre a estrutura de saída do oráculo.
• Bernstein–Vazirani como Caso Especial: O artigo demonstra que o problema de Bernstein–Vazirani é uma instância do HSP indexado-2 onde $G = (\mathbb{Z}/2\mathbb{Z})^n$. O algoritmo BV é mostrado como uma realização específica do algoritmo genérico indexado-$q$, utilizando a transformada de Hadamard (QFT sobre $(\mathbb{Z}/2\mathbb{Z})^n$).
• Redução para BV: Os autores mostram que qualquer HSP indexado-2 em um grupo abeliano finito arbitrário $G$ pode ser reduzido ao problema de Bernstein–Vazirani em $(\mathbb{Z}/2\mathbb{Z})^n$ ao quocientar o subgrupo $2G = \{g+g \mid g \in G\}$. Isso implica que uma transformada de Hadamard de profundidade um é suficiente para resolver qualquer HSP indexado-2, em vez de exigir uma QFT dedicada para o grupo específico $G$.
• Comparação com Shor–Kitaev: O artigo contrasta sua abordagem de consulta única com o método de amostragem de Shor–Kitaev. Embora Shor–Kitaev possa recuperar $H$ com alta probabilidade dada múltiplas consultas, uma única amostra de Shor–Kitaev não pode garantir identificação exata. A probabilidade de sucesso para uma única amostra é, no máximo, $\phi(q)/q$ (onde $\phi$ é a função totiente de Euler), e falha completamente se $G/H$ for não cíclico. Em contraste, o algoritmo proposto garante recuperação exata em uma consulta sob as condições estruturais declaradas.

Significado e Alegações
O artigo afirma afinar a compreensão da "solubilidade quântica de uma consulta" para HSPs abelianos. Seu significado principal reside em:

1. Clarificação do Papel da QFT: Delimita quando a QFT é uma ferramenta algébrica essencial (como em BV e identificação indexada-$q$) versus quando é meramente uma descrição matemática conveniente para uma unitária com colunas uniformes (como na decisão DJ).
2. Quadro Unificado: Coloca os algoritmos DJ, BV e Shor–Kitaev sob um quadro comum do HSP indexado-$q$, revelando o BV como um caso especial de uma classe mais ampla de problemas solúveis com uma única consulta.
3. Optimalidade de Consultas Únicas: Estabelece que, para $q=2$ e $q=3$, a identificação exata de consulta única é possível sem promessas estruturais adicionais, enquanto a abordagem padrão de amostragem (Shor–Kitaev) é inerentemente probabilística para uma única consulta.

Os autores concluem que identificar a estrutura algébrica correta (especificamente, a natureza cíclica do quociente e a estrutura compatível do contradomínio) é a chave para alcançar soluções determinísticas de consulta única, sugerindo que generalizações futuras devem focar nesses pré-requisitos estruturais, em vez de apenas em otimizações em nível de circuito.