¿Hay problemas en los que se sabe que las computadoras cuánticas proporcionan una ventaja exponencial?

27

En general, se cree y se afirma que las computadoras cuánticas pueden superar a los dispositivos clásicos en al menos algunas tareas.

Uno de los ejemplos más comúnmente citados de un problema en el que las computadoras cuánticas superarían a los dispositivos clásicos es , pero de nuevo, tampoco se sabe si también se puede resolver de manera eficiente con una computadora clásica (que es decir, si ).Factoring Factoring PFactorizaciónFactorizaciónFactorizaciónPAGS

Para otros problemas comúnmente citados en los que se sabe que las computadoras cuánticas proporcionan una ventaja, como la búsqueda en la base de datos, la aceleración es solo polinómica.

¿Existen casos conocidos de problemas en los que se pueda demostrar (ya sea probado o probado bajo fuertes supuestos de complejidad computacional) que las computadoras cuánticas proporcionarían una ventaja exponencial?

glS
fuente
Diría que la respuesta es no si restringe los problemas a problemas de decisión , porque hay problemas de muestreo (por ejemplo, BosonSampling e IQP) para los cuales se ha demostrado una ventaja cuántica exponencial (o más bien, se ha demostrado con fuertes suposiciones). Puede haber otros que no conozco.
glS
Tenga en cuenta que ya hay muchos algoritmos clásicos de costo subexponencial para la factorización. (Existe una brecha sustancial entre los costos polinómicos y exponenciales)
Squeamish Ossifrage
Como dice Heather, actualmente esto no se sabe ya que no se conocen los límites de las computadoras clásicas (y cuánticas). Los criterios que establezca en su pregunta en última instancia requieren que el respondedor vaya más allá de probar la relación más allá de P y NP. Te sugiero que reformules tu pregunta para pedir otros ejemplos probables (además de factorizar).
Toby Hawkins
2
Las consecuencias prácticas de una aceleración cuántica, por ejemplo , si el algoritmo de Shor realmente puede superar el GNFS clásico, tampoco están necesariamente implicadas por las relaciones asintóticas de las curvas de crecimiento de los costos. Vea esta respuesta para un poco más sobre el asintótico entorno versus concreto, y por qué las preguntas sobre P = NP son un poco falsas para la criptografía y las comparaciones prácticas de rendimiento.
Squeamish Ossifrage
1
@SqueamishOssifrage Exactamente. Me gustaría agregar que equiparar la membresía de P con 'eficiente' es más una ilusión de los científicos informáticos que la verdad absoluta. La idea es que, una vez que ha demostrado que un problema radica en P , incluso si es algo horrible como , habrá mejoras que lo afeiten a algo similar a O ( n 3 ) , un poco más cerca de acogedor 'límites inferiores condicionales'. A crédito, esto ha sucedido generalmente en el pasado. Pero esto no es garantía y en cuanto a la practicidad, incluso existen algoritmos 'lineales' que se consideran 'no implementables'. O(norte1235436546)O(norte3)
Lagarto discreto

Respuestas:

9

Suponga que una función tiene la siguiente propiedad curiosa: existe s { 0 , 1 } n tal que f ( x ) = f ( y ) si y solo si x + y = s . Si s = 0 es la única solución, esto significa que f es 1 a 1; de lo contrario, hay un valor distinto de ceroF:F2norteF2nortes{0 0,1}norteF(X)=F(y)X+y=ss=0 0F tal que f ( x )s para todo x , lo cual, debido a que 2 = 0 , significa que f es 2 a 1.F(X)=F(X+s)X2=0 0F

¿Cuál es el costo para cualquier probabilidad prescrita de éxito, en una computadora clásica o cuántica, de distinguir una función aleatoria uniforme 1 a 1 de una función aleatoria uniforme 2 a 1 que satisfaga esta propiedad, si cada opción (1 a -1 o 2 a 1) tiene la misma probabilidad?

Es decir, en secreto lanzo una moneda de manera justa; si obtengo caras, te entrego un circuito de caja negra (clásica o cuántica, resp.) para una función aleatoria uniforme 1 a 1 , mientras que si obtengo colas, te entrego un circuito de caja negra para un aleatorio uniforme de 2 a -1 función f . ¿Cuánto tiene que pagar para obtener una probabilidad determinada de éxito p de saber si llegué a cara o cruz?FFpags

Este es el escenario del algoritmo de Simon . Tiene aplicaciones esotéricas en criptoanálisis sin sentido , * y fue un instrumento temprano en el estudio de las clases de complejidad BQP y BPP y una inspiración temprana para el algoritmo de Shor.

Simon presentó un algoritmo cuántico (§3.1, p. 7) que cuesta qubits y el tiempo esperado de O ( n T f ( n ) + G ( n ) ) para una probabilidad cercana a 1 de éxito, donde T f ( n ) es el tiempo para calcular una superposición de valores de f en una entrada de tamaño ny donde G n × nO(norte+El |FEl |)O(nTf(n)+G(n))Tf(n)fn es el tiempo para resolver unG(n)n×n sistema de ecuaciones lineales en .F2

Simon esbozó además una prueba (Teorema 3.1, p. 9) de que un algoritmo clásico que evalúa en no más de 2 n / 4 valores discretos distintos no puede adivinar la moneda con ventaja mejor que 2 - n /f2n/4 sobre una suposición aleatoria uniforme.2n/2

En cierto sentido, esto responde positivamente a su pregunta: un cálculo cuántico que requiere un número lineal de evaluaciones de función aleatoria en una superposición cuántica de entradas puede lograr una probabilidad de éxito mucho mejor que un cálculo clásico que requiere un número exponencial de evaluaciones de una función aleatoria en modo discreto entradas , en el tamaño de las entradas. Pero en otro sentido, no responde a su pregunta en absoluto, porque podría ser que para cada función particular haya una forma más rápida de calcular la búsqueda.f

El algoritmo Deutsch-Jozsa sirve como una ilustración similar para un problema artificial ligeramente diferente al estudiar diferentes clases de complejidad, P y EQP, descubriendo los detalles que quedan como ejercicio para el lector.


* Simon no tiene sentido para el criptoanálisis porque solo un idiota inconcebiblemente confundido introduciría su clave secreta en el circuito cuántico del adversario para usarlo en una superposición cuántica de entradas, pero por alguna razón causa un revuelo cada vez que alguien publica un nuevo artículo sobre el uso del algoritmo de Simon romper las llaves de los idiotas con hardware imaginario, que es cómo funcionan todos estos ataques. Excepción: es posible que esto pueda romper la criptografía de caja blanca , pero la historia de seguridad para la criptografía de caja blanca incluso contra adversarios clásicos no es prometedora.

Ossifrage aprensivo
fuente
1
interesante, gracias por la respuesta. ¿Puedes explicar por qué esto no es una prueba de que ? Supongo que la respuesta es algo similar a esto que muestra una separación oracular , a diferencia de una "regular", pero no estoy lo suficientemente versado en estos temas para decir realmente. Creo que una breve discusión sobre esto mejoraría la respuesta. BQPBPP
glS
@glS Agregué una oración que creo que debería reducir el quid de la diferencia. ¿Eso ayuda?
Squeamish Ossifrage
12

No estoy seguro si esto es estrictamente lo que estás buscando; y no sé si calificaría esto como "exponencial" (tampoco soy un informático, por lo que mi capacidad para hacer análisis de algoritmos es más o menos inexistente ...), pero un resultado reciente de Bravyi et. Todos presentaron una clase de 'problemas de funciones lineales ocultas en 2D' que probablemente usan menos recursos en un dispositivo cuántico paralelo.

El documento está en el arxiv aquí , pero aquí hay un resumen rápido. La ventaja cuántica está en la profundidad del circuito en paralelo, por lo que el número de hilos en los que se puede dividir el problema es inferior al abanico acotado. Al problema se le da una matriz A y un vector de entrada b , se puede definir una forma cuadrática q y un subespacio especial para esa forma. El objetivo del "problema de la función lineal oculta" es encontrar una linealización para esa función cuadrática en un subespacio especial.norte×norteUNAsiq

Un circuito probabilístico clásico está limitado a ~ profundidad, si desea que su cómputo a tener éxito con probabilidad > 7 / 8Iniciar sesiónnorte>7 7/ /8 (es probable que quieren que tenga éxito con al menos esta probabilidad). Un circuito cuántico puede hacerlo con una profundidad constante, por lo que es una gran mejora.

La prueba esencialmente equivale a que un estado de gráfico específico es difícil de simular para un circuito clásico, este resultado secundario se probó un poco antes . Luego, el resto del documento muestra que la clase mayor de problemas contiene este problema difícil.

Emily Tyhurst
fuente
5

La clase de complejidad de los problemas de decisión que se pueden resolver de manera eficiente en una computadora clásica se llama BPP (o P , si no permite la aleatoriedad, pero de todos modos se sospecha que son iguales). La clase de problemas que se pueden resolver de manera eficiente en una computadora cuántica se llama BQP . Si existe un problema para el cual una computadora cuántica proporciona una aceleración exponencial, entonces esto implicaría que BPP BQP . Sin embargo, la pregunta BQP versus BPP es una pregunta abierta importante en la informática teórica, por lo que no se ha demostrado que exista tal problema (y si encuentra uno, definitivamente ganará todo tipo de premios).

BPPOBQPO

tparker
fuente
2
2

Si bien no puedo proporcionar una prueba formal, se cree que la simulación de (la evolución temporal) de un sistema cuántico es un caso así: no se conoce una mejor manera de hacerlo en una computadora clásica que en tiempo exponencial, pero una computadora cuántica puede trivialmente hazlo en tiempo polinómico.

La idea de un simulador cuántico de este tipo (ver también el artículo de Wikipedia ) es, de hecho, cómo se propusieron las computadoras cuánticas por primera vez.

pirámides
fuente