Recientemente, he leído sobre 'quantum bogosort' en alguna wiki. La idea básica es que, al igual que bogosort, simplemente barajamos nuestra matriz y esperamos que se ordene 'por accidente' y vuelva a intentarlo en caso de falla.

La diferencia es que ahora, tenemos un " cuántico mágico ", por lo que simplemente podemos probar todas las permutaciones a la vez en "universos paralelos" y "destruir todos los universos malos" donde el tipo es malo.

Ahora, obviamente, esto no funciona. Quantum es física, no magia. Los principales problemas son

1. 'Universos paralelos' es simplemente una interpretación de los efectos cuánticos, no algo que explota la computación cuántica. Quiero decir, podríamos usar números duros aquí, la interpretación solo confundirá los asuntos aquí, creo.

2. 'Destruir todos los universos malos' es un poco como la corrección de errores qubit, un problema muy difícil en la computación cuántica.

3. El género Bogo sigue siendo estúpido. Si podemos acelerar la clasificación a través de Quantum, ¿por qué no basarla en un buen algoritmo de clasificación ? (¡Pero necesitamos aleatoriedad, protestas de mi vecino! Sí, pero ¿no se te ocurre un algoritmo clásico mejor que se base en la aleatoriedad ?)

Si bien este algoritmo es principalmente una broma, podría ser una 'broma educativa', como el bogosort 'clásico', ya que la diferencia entre el mejor caso, el peor caso y la complejidad del caso promedio para algoritmos aleatorios es fácil y muy claro aquí. (para el registro, el mejor caso es , somos muy afortunados pero aún debemos verificar que nuestra respuesta sea correcta escaneando la matriz, el tiempo esperado es simplemente horrible (IIRC, proporcional al número de permutaciones, entonces ) y el peor de los casos es que nunca terminamos)$\Theta(n)$$O(n!)$

Entonces, ¿qué podemos aprender del 'cuántico bogosort'? En particular, ¿existen algoritmos cuánticos reales que sean similares o es una imposibilidad teórica o práctica? Además, ¿ha habido investigaciones sobre 'algoritmos de clasificación cuántica'? Si no, ¿por qué?

DESCARGO DE RESPONSABILIDAD: el Quantum-bogosort es un algoritmo de broma

Permítanme indicar el algoritmo brevemente:

• Paso 1: Usando un algoritmo de aleatorización cuántica, aleatorice la lista / matriz, de modo que no haya forma de saber en qué orden está la lista hasta que se observe. Esto dividirá el universo en universos ; sin embargo, la división no tiene costo, ya que de todos modos ocurre constantemente.$O(N!)$

• Paso 2: Verifique si la lista está ordenada. Si no, destruye el universo (descuidando la posibilidad física real).

Ahora, todos los universos restantes contienen listas / matrices que están ordenadas.

La peor complejidad del caso :$O(N)$

(solo consideramos aquellos universos que pueden observar que la lista está ordenada)

Complejidad promedio / mejor caso :$O(1)$

Uno de los principales problemas con este algoritmo es la gran posibilidad de ampliación de errores como Nick Johnson menciona aquí :

Sin embargo, este algoritmo tiene un problema mucho mayor. Suponga que una de cada 10 mil millones de veces concluirá erróneamente que una lista está ordenada cuando no lo está. Hay 20! formas de ordenar una lista de 20 elementos. Después de la clasificación, los universos restantes serán aquellos en los que la lista se ordenó correctamente, y los 2.4 millones de universos en los que el algoritmo concluyó erróneamente que la lista se ordenó correctamente. Entonces, lo que tiene aquí es un algoritmo para aumentar enormemente la tasa de error de una pieza de maquinaria.

'Universos paralelos' es una interpretación altamente simplificada de los efectos cuánticos , no algo que explota la computación cuántica.

No estoy realmente seguro de lo que quiere decir con "interpretación altamente simplificada de los efectos cuánticos". Las fuentes ( esto y esto ) que encontré en Internet con respecto al bogosort cuántico no mencionan explícitamente que están utilizando la interpretación alternativa de QM, es decir, la interpretación de Everett en la que podría estar pensando. De hecho, ni siquiera estoy seguro de cómo unir la interpretación de Everett y el cuántico-bogosort (usando post-selección, como comentaron algunas personas). De todos modos, solo como una nota: en la cosmología convencional, se cree ampliamente que existe más de un universo e incluso hay clasificaciones para ellos, llamados los cuatro niveles de Max Tegmark y Brian Greene 'Teorías cíclicas . Lea el artículo de Wiki sobre Multiverso para más detalles.

'Destruir todos los universos malos' es un poco como la corrección de errores qubit, un problema muy difícil en Quantum Computing.

Claro, de hecho es mucho más difícil, y no esperamos destruir universos literalmente. El bogosort cuántico es solo un concepto teórico, sin aplicaciones prácticas (que yo sepa).

El género Bogo sigue siendo estúpido. Si podemos acelerar la clasificación a través de Quantum, ¿por qué no basarla en un buen algoritmo de clasificación? (¡Pero necesitamos aleatoriedad, protestas de mi vecino! Sí, pero ¿no se te ocurre un algoritmo clásico mejor que se base en la aleatoriedad?)

Sí, sigue siendo estúpido . Parece haber comenzado como una "broma educativa" como usted dijo. Intenté encontrar el origen de este tipo, o documentos académicos relevantes, pero no pude encontrar ninguno. Sin embargo, incluso el clásico bogosort es estúpido en el sentido de que es ampliamente considerado como uno de los algoritmos de clasificación más ineficientes. Todavía se ha investigado, por puro interés educativo.

En particular, ¿existen algoritmos cuánticos reales que sean similares o es una imposibilidad teórica o práctica?

Ninguno que yo sepa. Tales algoritmos son de hecho posibilidades teóricas, pero definitivamente no son prácticas (al menos, todavía no).

Además, ¿ha habido investigaciones sobre 'algoritmos de clasificación cuántica'? Si no, ¿por qué?

De hecho, ha habido investigaciones sobre la "clasificación cuántica". Pero el problema con tales algoritmos de clasificación es que cualquier algoritmo de clasificación cuántica basado en la comparación tomaría al menos pasos , lo cual ya se puede lograr con algoritmos clásicos. Por lo tanto, para esta tarea, las computadoras cuánticas no son mejores que las clásicas. Sin embargo, en las clases limitadas por el espacio, los algoritmos cuánticos superan a sus contrapartes clásicas. Esto y esto son dos documentos relevantes.$\Omega (N\log N)$