En La complejidad computacional de la óptica lineal ( ECCC TR10-170 ), Scott Aaronson y Alex Arkhipov argumentan que si las computadoras cuánticas pueden ser simuladas eficientemente por las computadoras clásicas, entonces la jerarquía polinómica se colapsa al tercer nivel. El problema motivador es el muestreo de una distribución definida por una red lineal-óptica; Esta distribución puede expresarse como el permanente de una matriz particular. En el caso clásico, todas las entradas de la matriz no son negativas, por lo que existe un algoritmo de tiempo polinomial probabilístico, como lo muestran Mark Jerrum, Alistair Sinclair y Eric Vigoda (JACM 2004, doi: 10.1145 / 1008731.1008738) En el caso cuántico, las entradas son números complejos. Tenga en cuenta que en el caso general (cuando no se requiere que las entradas sean no negativas) el permanente no puede ser aproximado ni siquiera dentro de un factor constante, por el clásico resultado de 1979 de Valiant.
El artículo define una distribución definida por una matriz A y un problema de muestreo
Entrada de muestreo de bosones : matriz Muestra: de la distribución D A
El uso de un resultado de dureza parece ser una evidencia débil de una separación entre los mundos clásico y cuántico, ya que es posible que la clase de matrices en la configuración cuántica específica tenga una forma especial. Pueden tener entradas complejas, pero aún pueden poseer mucha estructura. Por lo tanto, podría existir un procedimiento de muestreo eficiente para tales matrices, a pesar de que el problema general es # P-hard.
¿Cómo el uso de BosonSampling en el periódico evita clases fáciles?
El artículo usa muchos antecedentes que no tengo en cuanto a la complejidad cuántica. Dadas todas las personas cuánticas en este sitio, realmente agradecería un puntero en la dirección correcta. ¿Cómo se sostendrían los argumentos si uno descubriera que la clase de matrices de valores complejos observadas en una configuración experimental específica en realidad correspondía a una clase de distribuciones de las que era fácil tomar muestras? ¿O hay algo inherente en el sistema cuántico que garantiza que esto no puede suceder?
fuente