Boson Sampling , a veces estilizado como BosonSampling, es un problema candidato atractivo para establecer la supremacía cuántica; los problemas de ingeniería parecen más superables que los asociados con una computadora cuántica completa de Turing.

Sin embargo, Boson Sampling tiene una desventaja, ya que la salida de una computadora cuántica fotónica capaz de ejecutar Boson Sampling con solo un puñado ( o más) de qubits puede que ni siquiera pueda simularse de manera clásica. Esto es, por supuesto, a diferencia de los problemas como la factorización, cuyos aspectos de ingeniería son significativamente más difíciles.N $\le 100$$\mathsf{NP}$

Por lo tanto, podemos establecer los resultados del muestreo de bosones en aproximadamente fotones, pero para verificar los resultados, necesitamos calcular el permanente de una matriz . Esto es famoso computacionalmente difícil de verificar. 100 × $100$$100\times100$

Tal vez una supercomputadora lo suficientemente potente como para calcular el permanente pueda hacer el truco. Pero entonces todo el mundo tendría que creer tanto los resultados del superordenador y los resultados de muestreo de Higgs.

¿Hay algo en Boson Sampling que pueda verificarse fácilmente?

He tenido un vuelo sofisticado para quizás usar los recursos de una red de minería de criptomonedas para calcular tal permanente, y confiando en algunos trucos / para verificación pública, pero yo No he llegado muy lejos.I $\mathsf{\#P}$$\mathsf{IP}$

EDITAR

Me gusta la respuesta de @ gIS.

Compare Boson Sampling con Appel y la prueba asistida por computadora de Franken del Teorema de los cuatro colores . La prueba original del 4CT supuestamente era controvertida, precisamente porque la prueba era demasiado larga para ser verificada públicamente por un lector humano. Nos hemos mudado tan lejos de los años 70 con nuestra confianza en las computadoras, en donde creo que ahora la mayoría de la gente acepta la prueba del 4CT sin mucha controversia. Pero pensar en cómo hacer que las cosas como una prueba de 4CT verificables por humanos pueda conducir a ideas interesantes como el teorema .$\mathsf{PCP}$

Sobre la necesidad de la verificación del muestreo de bosones

En primer lugar, permítanme señalar que no es estrictamente necesario verificar la salida de una muestra de bosones. Con esto, no quiero decir que no sea útil o interesante intentar hacerlo, sino que, en cierto sentido, es más una necesidad práctica que fundamental.

Creo que usted mismo presenta un buen argumento para esto cuando escribe

Tal vez una supercomputadora lo suficientemente potente como para calcular el permanente pueda hacer el truco. Pero entonces todos tendrían que creer tanto en los resultados de la supercomputadora como en los resultados del muestreo de bosones.

De hecho, hay muchos casos en los que uno resuelve un problema y confía en una solución que realmente no puede verificarse completamente. Quiero decir, olvida la mecánica cuántica, solo usa tu computadora para multiplicar dos números enormes. Probablemente tenga una gran confianza en que el resultado que obtiene es correcto, pero ¿cómo lo verifica sin usar otra computadora?

En términos más generales, la confianza en los resultados de un dispositivo proviene de una variedad de cosas, como el conocimiento del funcionamiento interno del dispositivo y las pruebas unitarias del dispositivo en sí (es decir, probar que funciona correctamente para las instancias especiales que puede verificar con algún otro método).

El problema de la certificación de muestreo de bosones no es diferente. Sabemos que, en algún momento, no podremos verificar completamente la salida de una muestra de bosones, pero eso no significa que no podamos confiar en ella. Si el dispositivo se construye con la debida minuciosidad, y su salida se verifica para una variedad de pequeñas instancias, y todas las pruebas que uno puede llevar a cabo son exitosas, entonces en algún momento se genera suficiente confianza en el dispositivo para hacer un afirmación de supremacía cuántica (o cualquier otra cosa para la que se quiera usar la muestra de bosones) significativa.

¿Hay algo sobre BosonSampling que pueda verificarse fácilmente?

Sí, hay propiedades que se pueden verificar. Debido a la naturaleza de muestreo del problema, lo que la gente suele hacer es descartar modelos alternativos que podrían haber generado las muestras observadas. Por ejemplo, Aaronson y Arkhipov ( 1309.7460 ) mostraron que la distribución BosonSampling está lejos de la distribución uniforme en la distancia de variación total (con alta probabilidad sobre las matrices aleatorias de Haar que inducen la distribución), y dieron un protocolo para distinguir eficientemente las dos distribuciones. Un trabajo más reciente que muestra cómo se pueden usar las firmas estadísticas para certificar la distribución de muestreo de bosones contra hipótesis alternativas es ( Walschaers et al. 2014 ).

Todos los demás trabajos que conozco se centran en certificar aspectos específicos de una muestra de bosones, en lugar de abordar directamente el problema de encontrar distribuciones alternativas que están lejos de la de BosonSampling para interferómetros aleatorios.

Más específicamente, se pueden aislar dos posibles fuentes principales de error en un aparato de muestreo de bosones: las que surgen de la implementación incorrecta del interferómetro y las que surgen de los fotones de entrada que no son lo que deberían (es decir, totalmente indistinguibles).

El primer caso es (relativamente) fácil de manejar porque uno puede caracterizar eficientemente un interferómetro usando fotones individuales. Sin embargo, certificar la indistinguibilidad de los fotones de entrada es más complicado. Una idea para hacer esto es cambiar el interferómetro a uno no aleatorio, como el interferómetro QFT, y ver si algo se puede verificar de manera eficiente en este caso más simple. No intentaré agregar todas las referencias relevantes aquí, pero esta dirección comenzó con (Tichy et al. 2010 , 2013 ).

Con respecto al aspecto de verificación pública, no he hecho nada en esta dirección de lo que he oído hablar. Tampoco estoy seguro de si es incluso una dirección particularmente significativa para explorar: ¿por qué deberíamos requerir un "alto estándar" de verificación para una muestra de bosones, cuando prácticamente para cualquier otro tipo de experimento estamos satisfechos de confiar en las personas que realizan el experimentar para ser bueno en lo que están haciendo?

Solo un pequeño complemento a la excelente respuesta de @gIS: conozco a varias personas (incluido yo mismo) interesadas en el aspecto de verificación pública. Hasta donde sé, todos los intentos han fallado, de ahí la falta de literatura sobre el tema: tan pronto como se puede probar que la muestra de Boson actuó correctamente, es un régimen en el que la muestra de Boson se puede simular eficientemente de manera clásica.

$IQP$$IQP$$P$