Respuesta: el algoritmo de Grover. Pero puede establecer intersecciones clásicamente superrápidas si preindexa. Eso es lo que hace Google, y estoy seguro de que Quora también lo hace. Si pre-indexa una consulta puede decirle si un elemento en el conjunto A también se encuentra en el conjunto B. Si no indexa previamente y el tamaño de B es N, necesita, por supuesto, N consultas clásicamente. Grover puede hacer el trabajo en consultas [math] \ sqrt {N} [/ math]. [La reciente compra de Google de una computadora cuántica Dwave 2x probablemente implica que desean buscar en conjuntos de datos que no pueden preindexar].
Excepto para la mayoría de los funcionarios electos de EE. UU., Un billón es un gran número (los EE. UU. Rutinariamente agregan un billón de dólares al déficit sin mucho aviso). Un billón es la aceleración de Grover alcanzable. Por ejemplo, nuestros sistemas operativos estándar actuales de 64 bits pueden almacenar y acceder a una palabra exo (exo = [math] 10 ^ {18} [/ math]). Entonces, si no preindexamos y necesitamos ver si hay una palabra de 64 bits en la memoria accesible para las máquinas estándar de hoy, somos un billón ([matemáticas] 10 ^ 9 [/ matemáticas]) más rápido con Quantum.
Nota nerd: Grover es más general, encuentra una coincidencia de función inversa. Si calculamos previamente el inverso, esto no tiene ningún valor (la indexación previa es el inverso de la intersección establecida). ¿Cómo funciona Grover? Es un poco misterioso, pero aquí hay una pista, la superposición cuántica “olfatea” la función inversa y la interferencia de onda cuántica “elimina” los cables malos rápidamente.
- ¿Qué es mejor para la computación cuántica: Harvard o Stanford?
- ¿Podemos mover algo más rápido que la luz dentro de la pantalla de una computadora? ¿Qué pasará si tratamos de hacerlo?
- ¿Quiénes son las principales empresas y startups involucradas en la computación cuántica a mediados de 2017?
- ¿La computación cuántica es solo analógica?
- ¿Cuál es el futuro de la investigación en mecánica cuántica?
