¿Algoritmo más simple para demostrar intuitivamente la aceleración cuántica?

8

¿Cuál es el algoritmo más simple (como el algoritmo de Deutsch y el algoritmo de Grover ) para demostrar intuitivamente aceleración cuántica? ¿Y puede este algoritmo explicarse intuitivamente?

Idealmente, esto también ilustraría claramente cómo se está utilizando la interferencia cuántica y por qué no es posible o útil usar solo la interferencia de ondas clásicas .

algorithm quantum-information classical-computing models Steven Sagona
fuente

¿Qué tipo de aceleración (polinomio vs exponencial) y qué tipo de ventaja (incondicional vs oracular)?

glS

No importa, siempre que esté claro. Sin embargo, puede ser agradable ver una aceleración exponencial.

Steven Sagona

Los ejemplos más simples también funcionarán con ondas clásicas. De hecho, todos los ejemplos, excepto que las ondas clásicas pueden (y deben) tomar exponencialmente muchos caminos en la cantidad de qubits involucrados.

Norbert Schuch

6

$\Delta p$ $p$ $p$ $\Delta p$ $\sqrt{\Delta p}$ $p$ $O(\log p)$

$O(\log p)$

$O(\log p)$ $O(\sqrt{\Delta p})$ $p$ $O(\sqrt{p})$

pirámides
fuente

4

La dificultad con la pregunta es la palabra intuitiva . La intuición básicamente refleja nuestra comprensión del mundo que nos rodea, que es descrito por la física clásica. La mecánica cuántica es exactamente el régimen donde nuestra intuición se rompe porque funciona de manera muy diferente al mundo de nuestra experiencia cotidiana. Como dijo Terry Pratchett:

Es muy difícil hablar cuántico usando un lenguaje originalmente diseñado para decirles a otros monos dónde está la fruta madura.

Es exactamente esa diferencia la que estamos usando para obtener la aceleración computacional.

Existe una secuencia de algoritmos estándar por los que avanza la mayoría de los textos de computación cuántica: el algoritmo de Deutsch , Deutsch-Jozsa , Simon's / Bernstein-Vazirani. Estos se eligen porque son los más fáciles de entender. Todos tienen, en términos generales, la misma estructura, pero una complejidad creciente, con una ganancia correspondiente en velocidad computacional (con Simon dando aceleración exponencial). No los entenderás intuitivamente. Tienes que hacer los cálculos. Creo que lo más cerca que llegarás es a través de la siguiente explicación del algoritmo de Deutsch:

$f(x)$ $f(0)=f(1)$ $f(0)$ $f(1)$ $f(0)\oplus f(1)$

DaftWullie
fuente

2

"La dificultad con la pregunta es la palabra intuitiva. La intuición básicamente refleja nuestra comprensión del mundo que nos rodea, que es descrito por la física clásica". Esta palabra se usa comúnmente dentro de las matemáticas, y a menudo no significa "análogo a la física clásica". " Lo que quiero decir (y a menudo se entiende) por intuición es tener un / entendimiento / de un mecanismo dentro de un marco. Es fácil enseñar a alguien a enchufar fórmulas para obtener una respuesta, pero hacer que comprenda fundamentalmente / entienda / el marco y la lógica es de lo que trata esta definición estándar de intuición.

Steven Sagona

1

@StevenSagona "tener una comprensión de un mecanismo dentro de un marco". Sí estoy de acuerdo. Si conoce algunos mecanismos dentro de un marco, puede comprender uno nuevo sin resolver todos los detalles porque tiene contexto, proporcionado por el conocimiento existente. Y si comprende algo, debería ser capaz, con algo de trabajo, de reconstruir los detalles matemáticos. Pero no puede entender el primer mecanismo en un marco completamente nuevo intuitivamente. Muchas personas interesadas pero sin experiencia intentan hacer esto, por ejemplo, a través de análogos clásicos, y fracasan, pero pueden creer que están teniendo éxito.

DaftWullie

2

Hay un buen ejemplo en la conferencia de Microsoft . Supongamos que tiene un cuadro negro clásico con 1 entrada y 1 salida. ¿Cuántas consultas necesita para determinar si la salida es constante o variable? Evidentemente necesitas 2 consultas; primero ingresas 0, segundo ingresas 1; si ambas salidas son idénticas, tiene constante, de lo contrario variable. Resulta que después de convertir el cuadro negro clásico en un cuadro negro cuántico, puede construir un circuito que solo necesita una sola consulta (la conferencia explica cómo hacerlo).

kludg
fuente

3

También conocido como algoritmo de Deutsch.

DaftWullie

1

Si está interesado en aprender más sobre el problema de Deutsch – Jozsa, le recomiendo echar un vistazo a los Quantum Katas . El Deutsch – Jozsa kata pasa por los conceptos necesarios como una serie de ejercicios a su propio ritmo, y puede ser una buena forma de aprender.

Chris Granade

Tenga en cuenta que esto solo da una aceleración cuántica si desea una respuesta con certeza. Si desea la respuesta con cierta certeza, se necesita un número constante de consultas, incluso si el tamaño del problema aumenta (como con Deutsch-Jozsa)

nippon

¿Algoritmo más simple para demostrar intuitivamente la aceleración cuántica?

Respuestas: