¿Cómo conduce la no conmutatividad de los observables a la aceleración cuántica en la resolución de algoritmos en computación cuántica?

tl; dr No se trata solo de que los observables no viajen. Que los estados se puedan superponer, enredar, etc. también es crucial.

Algunos problemas computacionales pueden existir a diferentes escalas, como ordenar$n$artículos, o elegir qué camino entre$n$ciudades es más rápido . Dada cualquier tarea de este tipo, y una forma de resolverla llamada algoritmo, la complejidad temporal de ese algoritmo cuantifica cuánto se ralentiza como$n$aumenta Por ejemplo, algunas formas de ordenar toman lo que llamamos$O(n^2)$tiempo, y duplicando grandes$n$cuadruplica el tiempo de clasificación, mientras que de lo contrario solo toma$O(n\log n)$tiempo, y duplicando$n$apenas duplica la escala de tiempo (si no fuera por el molesto$\log n$factor, sería una mera duplicación). De cualquier manera, no es tan costoso ordenar una lista. Por el contrario, el otro problema que mencioné toma años a menos que$n$es muy pequeño, aunque cuánto caro uno más grande$n$depende del algoritmo utilizado.

Se sabe que la computación cuántica nos permite reducir la complejidad temporal de algunos problemas al poner a disposición algoritmos que las computadoras clásicas no pueden usar. No se sabe que esto sea una propiedad general de aceleración de las computadoras cuánticas.

Aquí hay un ejemplo. Dada una lista de$n$artículos, tenemos la garantía de que exactamente uno tiene la propiedad deseada y podemos verificar cada uno. ¿Cómo encontramos cuál es? Clásicamente, todo lo que podemos hacer es revisarlos uno por uno, y eso toma$O(n)$tiempo. Sorprendentemente, las computadoras cuánticas solo necesitan$O(\sqrt{n})$¡tiempo! ¿Por qué?

Los detalles completos están aquí , pero la esencia es esta: preparamos una superposición de todas las respuestas candidatas en la que cada una tiene el mismo coeficiente de valor complejo, luego seguimos aplicando lo que se puede considerar como rotaciones y reflexiones que cambian el estado por$2\arcsin\frac{1}{\sqrt{n}}$radianes, y una vez que el cambio total se aproxima$\pi/2$una medición casi con seguridad identificará al candidato correcto.

Sin embargo, la superposición per se no siempre es el quid de la cuestión: un posible resultado, el entrelazamiento, también puede ser crucial. Un ejemplo mucho más difícil que no discutiré en detalle es que la explotación de estados entrelazados permite a las computadoras cuánticas factorizar números enteros positivos grandes más rápido que cualquier algoritmo clásico conocido.

Algunos pensamientos:

1. El aspecto de "observables que no conmutan" de la mecánica cuántica es esencialmente equivalente a la posibilidad de tener superposiciones y, por lo tanto, efectos de interferencia, etc. Decir que dos observables conmutan equivale al hecho de que medir sus respectivas bases propias da "información incompatible", es decir, conocer el resultado de una medición reduce el conocimiento sobre el resultado de la otra.

2. A su vez, la incompatibilidad de diferentes bases de medida equivale a la posibilidad de medir en bases de superposición. Esta es la propiedad de los sistemas cuánticos de poder contener información en las coherencias entre diferentes constituyentes. Con esto quiero decir que un sistema cuántico puede ser tal que sus componentes individuales no contengan ninguna información, y la única forma de acceder a su información es midiendo en bases no locales.

3. No hay una respuesta definitivamente satisfactoria, que yo sepa, a la pregunta: ¿qué propiedades de la mecánica cuántica conducen a la aceleración cuántica en un algoritmo dado? Puede encontrar alguna discusión relevante, por ejemplo, aquí . Claro, se puede decir que los algoritmos cuánticos más rápidos que los clásicos son aquellos que explotan los efectos de interferencia de manera inteligente, pero en mi opinión, eso equivale esencialmente a decir que lo que hace que los algoritmos sean más rápidos es la mecánica cuántica. Los efectos de interferencia son tan fundamentales e intrínsecos a la mecánica cuántica que decir "X es más rápido debido a la interferencia" es lo mismo que decir "X es más rápido debido a la mecánica cuántica". Ciertamente, no ayuda mucho a determinar qué algoritmos realmente brindan una ventaja cuántica.