Unbounded degree overhead for Alice-conditioned quantum Bell certificates

Resumo Técnico: Sobrecarga de Grau Ilimitada para Certificados Quânticos de Bell Condicionados a Alice

Enunciado do Problema
O artigo investiga o custo computacional da certificação de limites de Bell de Navascués–Pironio–Acín (NPA) dentro da hierarquia quando a estrutura do certificado é restrita. Especificamente, examina-se as hierarquias "condicionadas a Alice", onde cada termo de soma de quadrados (SOS) no certificado dual deve envolver apenas uma das perguntas de Alice. Esta estrutura é relevante para jogos não locais compilados e provas específicas de solidez criptográfica (por exemplo, a rota "nice-SOS"). A questão central é se restringir o certificado à esta estrutura de "pergunta única" impõe uma sobrecarga de grau limitada em comparação com certificados padrão não restritos. O autor foca na família de funcionais de Bell CHSH inclinado (tilted-CHSH) de grau dois, onde certificados padrão são conhecidos por serem exatos no nível dois.

Metodologia
O autor emprega uma combinação de construção analítica, verificação algébrica e otimização numérica dentro do framework de programação semidefinida (SDP) e álgebras de operadores.

1. Hierarquias e Cones: O estudo compara dois cones de certificados SOS no espaço real de gap de Bell:

   • $D_k$: Certificados de grau padrão $k$ (palavras de comprimento reduzido total $\le k$).
   • $O_k$: Certificados de grau $k$ condicionados a Alice (palavras de Bob de comprimento $\le k$ em blocos indexados pela pergunta/resposta de Alice).
     A conversão de grau $d_{std}$ e $d_{os}$ é definida como o nível mínimo necessário para certificar um limite $\beta$.

2. Contraexemplos Analíticos (Sobre carga Ilimitada): Para provar que nenhum nível condicionado finito contém todos os certificados de nível dois padrão, o autor constrói uma família de testemunhas viáveis usando funcionais positivos sobre o grupo diedral infinito ($\mathbb{Z}_2 * \mathbb{Z}_2$).

   • Eles utilizam um traço ponderado por Fejér para construir um funcional positivo que concentra massa em palavras específicas de Bob.
   • Ao subtrair um termo de posto um correspondente a uma resposta determinística de Bob ponderada por $r_k \sim k^{-2}$, eles criam uma testemunha que viola as restrições de positividade de qualquer nível condicionado $k$ finito para um tilt $\alpha_k$ aproximando-se do endpoint local ($\alpha \to 2$).
   • Esta construção baseia-se na matriz de Gram de uma média móvel, onde a subtração de posto um permanece semidefinida positiva apenas se o nível condicionado for suficientemente alto.

3. Certificados Exatos em Intervalos: Inversamente, para identificar regimes onde a sobrecarga é limitada, o autor constrói certificados exatos para intervalos específicos do parâmetro de tilt.

   • Redução de Face Ótima: Eles utilizam a estratégia ótima do jogo CHSH inclinado para identificar o núcleo das matrizes de momento. Isso reduz a busca pelo certificado dual à busca por matrizes semidefinidas positivas (PSD) no complemento ortogonal do núcleo.
   • Famílias de Funções Racionais: Para o intervalo $\alpha \in [13/10, 3/2]$, eles parametrizam o limite quântico e os núcleos das estratégias usando funções racionais. Eles constroem uma família contínua de certificados onde as matrizes de Gram são polinômios de matriz de grau 20.
   • Positividade de Bernstein: Eles verificam a positividade destes polinômios sobre o intervalo expandindo-os em bases de Bernstein e verificando se todas as matrizes de coeficientes são estritamente PSD.

4. Certificação de Aleatoriedade: O artigo traduz estas separações de limites de Bell em certificação de aleatoriedade independente de dispositivo. Usando um critério de contato envolvendo a concavidade da função de probabilidade de adivinhação, mostram que uma separação nos limites de Bell implica diretamente uma separação na entropia mínima certificada.

Contribuições Principais e Resultados

• Sobre carga de Grau Ilimitada: O resultado primário (Teorema 1) prova que, para a família CHSH inclinada, nenhum nível finito da hierarquia condicionada a Alice contém todos os certificados de nível dois padrão. Especificamente, conforme o tilt $\alpha$ se aproxima do endpoint local ($\alpha \to 2$), o nível condicionado requerido $d_{os}$ cresce pelo menos como $\Omega((2-\alpha)^{-1/2})$.

  • Para qualquer inteiro $k$, existe um tilt $\alpha_k$ tal que o certificado padrão é exato no nível 2 ($d_{std}=2$), mas o certificado condicionado requer um nível estritamente maior que $k$ ($d_{os} > k$).
  • Isto estabelece que a restrição de "pergunta única" pode forçar um aumento ilimitado de recursos algébricos, mesmo quando um certificado de baixo grau padrão existe.

• Conversão Finita Exata em Intervalos: Apesar da sobrecarga ilimitada perto do endpoint, o autor prova (Teorema 2) que, no intervalo contínuo $\alpha \in [13/10, 3/2]$, a sobrecarga é exatamente de um nível.

  • Para todo $\alpha$ neste intervalo, $d_{std} = 2$ e $d_{os} = 3$.
  • Isto é demonstrado via uma família de certificados de função racional explícita verificada via positividade de Bernstein, provando que a hierarquia condicionada pode fechar exatamente no nível 3 para esta subfamília.

• Separação de Valores de Nível Um: O artigo corrige uma afirmação anterior sobre a equivalência de nível um. Prova (Teorema 3.7) que, para CHSH inclinado com $\alpha > 0$, o valor de nível um padrão é estritamente maior que o valor condicionado a Alice de nível um ($\omega_{std}^1 > \omega_{os}^1$). Isto deve-se ao fato de que blocos condicionados no nível um incluem implicitamente momentos de grau total três (via o rótulo do bloco) que estão ausentes na truncagem padrão de nível um.

• Aleatoriedade Independente de Dispositivo: O autor demonstra (Teorema 3) que a sobrecarga de grau ilimitada tem consequências operacionais. Nenhum nível condicionado finito pode certificar todo o tradeoff de aleatoriedade CHSH ótimo contra informação lateral quântica, enquanto o nível dois padrão pode. Especificamente, para uma sequência de valores CHSH $s_k \to 2$, a entropia mínima certificada usando o nível condicionado $k$ é estritamente menor que o ótimo quântico, com um déficit excedendo $10^{-3}$ bits para pontos específicos.

• Implicações para Solidez Compilada: Os resultados fornecem uma obstrução quantitativa para entradas "nice-SOS" em provas de solidez de jogos não locais compilados. O grau dos fatores de palavras de Bob em um certificado nice-SOS exato para um limite inclinado perto do endpoint deve crescer como $\Omega(\epsilon^{-1/2})$, limitando a eficiência de tais provas para tilts arbitrários.

Significância e Alegações
O artigo afirma separar o "grau SOS ordinário" dos "recursos impostos pela estrutura de certificado de pergunta única". Demonstra que restrições estruturais nos certificados, frequentemente motivadas por aplicações criptográficas (jogos compilados), podem alterar fundamentalmente as propriedades de convergência da hierarquia NPA.

• Modéstia das Alegações: O autor afirma explicitamente que não alega uma falha na segurança do protocolo compilado ou uma falha na taxa de chave finita. Os resultados referem-se à precisão dos métodos de certificação de rodada única e ao grau algébrico necessário para certificados exatos.
• Problemas Abertos: O artigo reconhece que, embora um limite assintótico inferior de $\Omega(\epsilon^{-1/2})$ seja provado, um limite superior exato ou a prova de fechamento exato finito para cada tilt subcrítico fixo permanece aberto. A saturação numérica sugere crescimento de raiz quadrada, mas um limite superior rigoroso correspondente a este expoente não é estabelecido.
• Correção da Literatura: O trabalho refina a compreensão da relação entre hierarquias condicionadas e padrão, corrigindo especificamente uma asserção sobre a igualdade de valores de nível um para o CHSH inclinado e clarificando a distinção entre filtrações POVM/localizador e o quociente PVM bruto usado aqui.

Em resumo, o artigo estabelece que, embora as hierarquias condicionadas a Alice possam ser exatas em níveis baixos para regimes específicos de parâmetros, elas sofrem de uma sobrecarga de grau ilimitada perto da fronteira do conjunto quântico, impedindo que substituam universalmente as hierarquias padrão para tarefas de certificação exata.