Unbounded degree overhead for Alice-conditioned quantum Bell certificates

Resumen Técnico: Sobrecarga de Grado Ilimitada para Certificados Cuánticos de Bell Condicionados por Alice

Planteamiento del Problema
El artículo investiga el costo computacional de certificar cotas de Bell cuánticas dentro de la jerarquía de Navascués–Pironio–Acín (NPA) cuando la estructura del certificado está restringida. Específicamente, examina jerarquías "condicionadas por Alice", donde cada término de suma de cuadrados (SOS) en el certificado dual debe involucrar únicamente una de las preguntas de medición de Alice. Esta estructura es relevante para juegos no locales compilados y pruebas específicas de solidez criptográfica (por ejemplo, la ruta "nice-SOS"). La cuestión central es si restringir el certificado a esta estructura de "pregunta única" impone una sobrecarga acotada en el grado de la descomposición SOS en comparación con los certificados estándar no restringidos. El autor se centra en la familia de funcionales de Bell de CHSH inclinado (tilted-CHSH) donde se sabe que los certificados estándar son exactos en el nivel dos.

Metodología
El autor emplea una combinación de construcción analítica, verificación algebraica y optimización numérica dentro del marco de la programación semidefinida (SDP) y los álgebras de operadores.

1. Jerarquías y Conos: El estudio compara dos conos de certificados SOS en el espacio real de brecha de Bell:

   • $D_k$: Certificados estándar de grado-$k$ (palabras de longitud total reducida $\le k$).
   • $O_k$: Certificados de grado-$k$ condicionados por Alice (palabras de Bob de longitud $\le k$ en bloques indexados por la pregunta/respuesta de Alice).
     La conversión de grado $d_{std}$ y $d_{os}$ se define como el nivel mínimo requerido para certificar una cota específica $\beta$.

2. Contraejemplos Analíticos (Sobrecarga Ilimitada): Para probar que ningún nivel condicionado finito contiene todos los certificados de nivel dos estándar, el autor construye una familia de testigos factibles utilizando funcionales positivos sobre el grupo diedro infinito ($\mathbb{Z}_2 * \mathbb{Z}_2$).

   • Utilizan un traza ponderada por Fejér para construir un funcional positivo que concentra la masa en palabras específicas de Bob.
   • Al restar un término de rango uno correspondiente a una respuesta determinista de Bob ponderada por $r_k \sim k^{-2}$, crean un testigo que viola las restricciones de positividad de cualquier nivel condicionado $k$ finito para un tilt $\alpha_k$ que se aproxima al punto final local ($\alpha \to 2$).
   • Esta construcción se basa en la matriz de Gram de una media móvil, donde la sustracción de rango uno permanece semidefinida positiva solo si el nivel condicionado es suficientemente alto.

3. Certificados Exactos en Intervalos: Por el contrario, para identificar regímenes donde la sobrecarga está acotada, el autor construye certificados exactos para intervalos específicos del parámetro de inclinación (tilt).

   • Reducción al Cara Óptima (Optimal-Face Reduction): Utilizan la estrategia óptima del juego CHSH inclinado para identificar el núcleo (kernel) de las matrices de momentos. Esto reduce la búsqueda del certificado dual a encontrar matrices semidefinidas positivas (PSD) en el complemento ortogonal del núcleo.
   • Familias de Funciones Racionales: Para el intervalo $\alpha \in [13/10, 3/2]$, parametrizan la cota cuántica y los núcleos de la estrategia utilizando funciones racionales. Construyen una familia continua de certificados donde las matrices de Gram son polinomios matriciales de grado 20.
   • Positividad de Bernstein: Verifican la positividad de estos polinomios sobre el intervalo expandiéndolos en bases de Bernstein y comprobando que todas las matrices de coeficientes son estrictamente PSD.

4. Certificación de Aleatoriedad: El artículo traduce estas separaciones de cotas de Bell en la certificación de aleatoriedad independiente del dispositivo. Usando un criterio de contacto que involucra la concavidad de la función de probabilidad de adivinación, muestran que una separación en las cotas de Bell implica directamente una separación en la entropía mínima certificada.

Contribuciones Claves y Resultados

• Sobrecarga de Grado Ilimitada: El resultado principal (Teorema 1) prueba que, para la familia de CHSH inclinado, ningún nivel finito de la jerarquía condicionada por Alice contiene todos los certificados de nivel dos estándar. Específicamente, a medida que el tilt $\alpha$ se aproxima al punto final local ($\alpha \to 2$), el nivel condicionado requerido $d_{os}$ crece al menos como $\Omega((2-\alpha)^{-1/2})$.

  • Para cualquier entero $k$, existe un tilt $\alpha_k$ tal que el certificado estándar es exacto en el nivel 2 ($d_{std}=2$), pero el certificado condicionado requiere un nivel estrictamente mayor que $k$ ($d_{os} > k$).
  • Esto establece que la restricción de "pregunta única" puede forzar un aumento ilimitado de los recursos algebraicos, incluso cuando existe un certificado de bajo grado estándar.

• Conversión Finita Exacta en Intervalos: A pesar de la sobrecarga ilimitada cerca del punto final, el autor prueba (Teorema 2) que en el intervalo continuo $\alpha \in [13/10, 3/2]$, la sobrecarga es exactamente de un nivel.

  • Para todo $\alpha$ en este rango, $d_{std} = 2$ y $d_{os} = 3$.
  • Esto se demuestra mediante una familia de certificados de funciones racionales explícitas verificada mediante positividad de Bernstein, probando que la jerarquía condicionada puede cerrarse exactamente en el nivel 3 para esta subfamilia.

• Separación de Valores de Nivel Uno: El artículo corrige una afirmación previa sobre la equivalencia de nivel uno. Prueba (Teorema 3.7) que para CHSH inclinado con $\alpha > 0$, el valor de nivel uno estándar es estrictamente mayor que el valor de nivel uno condicionado por Alice ($\omega_{std}^1 > \omega_{os}^1$). Esto se debe a que los bloques condicionados en el nivel uno incluyen implícitamente momentos de grado total tres (vía la etiqueta del bloque) que están ausentes en la truncación estándar de nivel uno.

• Aleatoriedad Independiente del Dispositivo: El autor demuestra (Teorema 3) que la sobrecarga de grado ilimitada tiene consecuencias operativas. Ningún nivel condicionado finito puede certificar todo el compromiso de aleatoriedad de CHSH óptimo frente a información lateral cuántica, mientras que el nivel dos estándar sí puede. Específicamente, para una secuencia de valores CHSH $s_k \to 2$, la entropía mínima certificada usando el nivel condicionado $k$ es estrictamente menor que la óptima cuántica, con un déficit que supera los $10^{-3}$ bits para puntos específicos.

• Implicaciones para la Solidez Compilada: Los resultados proporcionan una obstrucción cuantitativa para las entradas "nice-SOS" en las pruebas de solidez de juegos no locales compilados. El grado de los factores de las palabras de Bob en un certificado nice-SOS exacto para un límite inclinado cerca del punto final debe crecer como $\Omega(\epsilon^{-1/2})$, limitando la eficiencia de tales pruebas para tilts arbitrarios.

Significado y Reivindicaciones
El artículo pretende separar el "grado SOS ordinario" de los "recursos impuestos por la estructura del certificado de pregunta única". Demuestra que las restricciones estructurales en los certificados, a menudo motivadas por aplicaciones criptográficas (juegos compilados), pueden alterar fundamentalmente las propiedades de convergencia de la jerarquía NPA.

• Modestia de las Reivindicaciones: El autor establece explícamente que no pretende alegar un fallo en la seguridad de los protocolos compilados o un fallo en la tasa de clave finita. Los resultados se refieren a la precisión de los métodos de certificación de un solo turno y al grado algebraico requerido para los certificados exactos.
• Problemas Abiertos: El trabajo reconoce que, si bien se ha probado un límite inferior asintótico de $\Omega(\epsilon^{-1/2})$, sigue abierto un límite superior exacto o la prueba de un cierre exacto finito para cada sub-crítico de tilt fijo. La saturación numérica sugiere un crecimiento de raíz cuadrada, pero no se establece un límite superior riguroso que coincida con este exponente.
• Corrección de la Literatura: El trabajo refina la comprensión de la relación entre las jerarquías estándar y condicionadas, corrigiendo una aserción previa sobre la igualdad de los valores de nivel uno para CHSH inclinado y aclarando la distinción entre las filtraciones de POVM/localizador y el cociente de PVM bruto utilizado aquí.

En resumen, el artículo establece que, si bien las jerarquías condicionadas por Alice pueden ser exactas en niveles bajos para regímenes de parámetros específicos, sufren una sobrecarga de grado ilimitada cerca del límite del conjunto cuántico, lo que impide que reemplacen universalmente a las jerarquías estándar para tareas de certificación exacta.