Contexto :
Hay varios documentos que estudian las implicaciones de las curvas cerradas de tiempo (CTC) para la complejidad cuántica. En 2008, Aaronson y Watrous publicaron su famoso artículo sobre este tema que muestra que ciertas formas de viaje en el tiempo pueden hacer que la computación clásica y cuántica sea equivalente, es decir, las computadoras cuánticas no brindan ninguna ventaja computacional si pueden enviar información al pasado a través de curvas cerradas.
Preguntas :
El resumen dice claramente que no se sabe que existan curvas cerradas en forma de tiempo . Entonces, ¿por qué exactamente los teóricos de la complejidad están interesados en este tema? ¿El estudio de los CTC proporciona una visión no trivial de los fundamentos de la teoría de la complejidad?
¿Hay otras líneas mundiales que se estudien popularmente en el contexto de la teoría de la complejidad? ¿Si es así por qué? Si no, ¿por qué no (y luego, ¿qué tienen de especial los CTC)?
Realmente no he llegado a trabajar en los documentos de CTC, pero estoy tratando de tener una idea del "panorama general" aquí, para comprender la motivación detrás de estudiar este tema.
Nota : Previamente pregunté sobre esto en Quantum Computing SE, en el contexto de la teoría de la información cuántica, pero aquí estoy tratando específicamente de verlo a través de los lentes de un teórico de la complejidad o un informático.
fuente
Respuestas:
Creo que la gran pregunta aquí es "¿Cómo se ve la complejidad / potencia de los algoritmos en nuestro universo?" Si ignoramos la relatividad y la QM, entonces las máquinas simples de Turing son un modelo decente. Pero la relatividad y la QM son nuestras mejores teorías físicas actuales para explicar el universo, por lo que la pregunta es si tomar efectos relativistas o cuánticos cambia el panorama de la complejidad.
En el caso de QM, esto también está motivado por el potencial para la ingeniería de las computadoras cuánticas en funcionamiento. En el caso de los CTC, aunque no se sabe que existan, entiendo que están permitidos según la relatividad. Entonces la pregunta es: si existieran y pudiéramos aprovecharlos, ¿qué más podrían hacer las computadoras / cómo cambia la complejidad? (Lo mismo ocurre con QM, estamos más cerca de las computadoras cuánticas existentes).
Finalmente, un poco sobre el gusto personal; Aunque esto es subjetivo, la pregunta en sí misma es al menos un poco sobre el gusto subjetivo, así que espero que sea apropiado. De hecho, quiero estar (amigablemente) en desacuerdo con usul un poco aquí. No creo que todos los recursos sean necesariamente interesantes para (la mayoría) de los teóricos de la complejidad. Por ejemplo, en una máquina Turing se pueden considerar las inversiones de cabezales como un recurso (¿cuántas veces cambia la dirección de la cabeza de la cinta durante un cálculo?). Incluso se puede demostrar que se trata de una medida de complejidad de Blum, con teoremas de brecha, aceleración y jerarquía análogos al tiempo o al espacio. He visto esto dado como un ejercicio divertido en los cursos de pregrado, pero no he visto mucha investigación al respecto. ¿Por qué? Tal vez usted porque se siente más dependiente del modelo y menos relevante para otras cosas que a las personas les interesan con respecto a la complejidad de los algoritmos. Del mismo modo, las personas estudian hipercomputación (¿qué podría hacer una TM con infinitos pasos?); Si bien ciertamente hay más investigación sobre esto, creo que está menos motivado por la realidad física ... Mi punto aquí no es difamar ninguna dirección de investigación en particular (de hecho, creo que son algo interesantes), pero más que no No creo que los teóricos de la complejidad estén necesariamente interesados en los CTC "por definición", sino que hay consideraciones adicionales que hacen que sean interesantes para muchos. (Y, por supuesto, ¡probablemente no todos los teóricos de la complejidad los encuentren interesantes!) Si bien ciertamente hay más investigación sobre esto, creo que está menos motivado por la realidad física ... Mi punto aquí no es difamar ninguna dirección de investigación en particular (de hecho, creo que son algo interesantes), pero más que no No creo que los teóricos de la complejidad estén necesariamente interesados en los CTC "por definición", sino que hay consideraciones adicionales que hacen que sean interesantes para muchos. (Y, por supuesto, ¡probablemente no todos los teóricos de la complejidad los encuentren interesantes!) Si bien ciertamente hay más investigación sobre esto, creo que está menos motivado por la realidad física ... Mi punto aquí no es difamar ninguna dirección de investigación en particular (de hecho, creo que son algo interesantes), pero más que no No creo que los teóricos de la complejidad estén necesariamente interesados en los CTC "por definición", sino que hay consideraciones adicionales que hacen que sean interesantes para muchos. (Y, por supuesto, ¡probablemente no todos los teóricos de la complejidad los encuentren interesantes!) sino que hay consideraciones adicionales que hacen que sean interesantes para muchos. (Y, por supuesto, ¡probablemente no todos los teóricos de la complejidad los encuentren interesantes!) sino que hay consideraciones adicionales que hacen que sean interesantes para muchos. (Y, por supuesto, ¡probablemente no todos los teóricos de la complejidad los encuentren interesantes!)
fuente
Perdón por la respuesta del "panorama general" de un teórico no cuántico, pero este contraste podría ayudar: podría describir algoritmos como el estudio de cómo resolver problemas computacionales, mientras que la teoría de la complejidad estudia los recursos (especialmente el tiempo) requeridos en teoría para resolverlos ¿Cuán difíciles son estos problemas realmente en algún nivel fundamental y cómo se clasifican según los requisitos de recursos? Esta pregunta se considera interesante independientemente de cuántos o qué tipos de recursos tengan los humanos insignificantes a su disposición.
La cuestión de cuánto tiempo se necesita en teoría para resolver un problema cambia si permite los CTC, por lo tanto, son interesantes para la teoría de la complejidad por definición.
Entonces, creo que su primera pregunta es como preguntar por qué los teóricos de la computabilidad estudiarían grados de Turing superiores a cero; Es lo que hacen.
fuente
Si se considera la geodésica como un análisis geométrico mundial de la búsqueda de Grover, muestre bajo una métrica que la búsqueda de Grover sigue una geodésica. También en pequeñas perturbaciones, la búsqueda de Grover funciona bien. Además, dada una perturbación, bajo un tipo de métrica de Kahler, la métrica de Fubini-Study, la búsqueda de Grover no puede seguir una geodésica, ver estudio de perturbación . Referencias para la optimización , y el estudio geométrico de la información de búsqueda de Grover .
Alvarez et al comenzaron a mostrar que la búsqueda de Grover sigue una geodésica bajo la métrica Fubini-Study, y exploraron otros algoritmos cuánticos como el algoritmo Shors. Aunque esto se hizo en el contexto de la información de Fisher, todavía se demostró que, según la métrica de Fubini-Study, la búsqueda de Grover sigue una geodésica. Además, Alvarez et al muestran, bajo los supuestos de información de Fisher: "La factorización de Shor no preserva la información constante de Fisher".
fuente