Contexto :
Existem vários artigos que estudam as implicações das curvas timelike fechadas (CTCs) na complexidade quântica. Em 2008, Aaronson e Watrous publicaram seu famoso artigo sobre esse tópico, que mostra que certas formas de viagem no tempo podem tornar equivalentes a computação quântica e clássica, ou seja, computadores quânticos não oferecem vantagem computacional se puderem enviar informações ao passado através de curvas de tempo fechado.
Perguntas :
O resumo diz claramente que não se sabe que existem curvas fechadas no tempo . Então, por que exatamente os teóricos da complexidade estão interessados neste tópico? O estudo dos CTCs fornece uma visão não trivial dos fundamentos da teoria da complexidade?
Existem outras linhas do mundo que são popularmente estudadas no contexto da teoria da complexidade? Se sim, por que? Se não, por que não (e o que há de tão especial nos CTCs)?
Eu realmente não cheguei a trabalhar nos documentos da CTC, mas estou tentando ter uma idéia do "quadro geral" aqui, para entender a motivação por trás do estudo deste tópico.
Nota : Eu perguntei anteriormente sobre isso no Quantum Computing SE, no contexto da teoria da informação quântica, mas aqui estou especificamente tentando visualizá-lo através das lentes de um teórico da complexidade ou cientista da computação.
Respostas:
Penso que a grande questão aqui é "Como é a complexidade / poder dos algoritmos no nosso universo?" Se ignorarmos a relatividade e o QM, as máquinas simples de Turing com baunilha são um modelo decente. Mas a relatividade e a QM são nossas melhores teorias físicas atuais para explicar o universo; portanto, a questão é se tomar efeitos relativísticos ou quânticos muda o cenário da complexidade.
No caso da QM, isso agora também é motivado pelo potencial da engenharia de computadores quânticos em funcionamento. No caso dos CTCs, embora eles não existam, meu entendimento é que eles são permitidos de acordo com a relatividade. Portanto, a questão é: se eles existissem e pudéssemos tirar proveito deles, o que mais os computadores poderiam fazer / como a complexidade muda? (O mesmo vale para QM, estamos apenas mais próximos dos computadores quânticos existentes.)
Finalmente, um pouco sobre o gosto pessoal; Embora isso seja subjetivo, a questão em si é pelo menos um pouco sobre o gosto subjetivo, por isso espero que seja apropriado. Na verdade, eu quero (amigavelmente) discordar um pouco de usul aqui. Não acho que todos os recursos sejam necessariamente interessantes para (a maioria) teóricos da complexidade. Por exemplo, em uma máquina de Turing, pode-se considerar a inversão da cabeça como um recurso (quantas vezes a cabeça da fita muda de direção durante um cálculo?). Pode-se até mostrar que essa é uma medida de complexidade de Blum, com os teoremas de gap, aceleração e hierarquia análogos ao tempo ou ao espaço. Eu vi isso como um exercício divertido nos cursos de graduação, mas não vi muita pesquisa sobre isso. Por quê? Talvez você se sinta mais dependente do modelo e menos relevante para outras coisas com as quais as pessoas se preocupam com relação à complexidade dos algoritmos. Da mesma forma, as pessoas estudam hipercomputação (o que uma MT poderia fazer com infinitas etapas); embora certamente haja mais pesquisas sobre isso, acho que é menos motivado pela realidade física ... Meu objetivo aqui não é difamar nenhuma direção de pesquisa específica (na verdade, acho que são um pouco interessantes), mas mais que não achamos que os teóricos da complexidade estão necessariamente interessados nos CTCs "por definição", mas há considerações adicionais que os levam a ser interessantes para muitos. (E, é claro, provavelmente nem todos os teóricos da complexidade os acham interessantes!) embora certamente haja mais pesquisas sobre isso, acho que é menos motivado pela realidade física ... Meu objetivo aqui não é difamar nenhuma direção de pesquisa específica (na verdade, acho que são um pouco interessantes), mas mais que não achamos que os teóricos da complexidade estão necessariamente interessados nos CTCs "por definição", mas há considerações adicionais que os levam a ser interessantes para muitos. (E, é claro, provavelmente nem todos os teóricos da complexidade os acham interessantes!) embora certamente haja mais pesquisas sobre isso, acho que é menos motivado pela realidade física ... Meu objetivo aqui não é difamar nenhuma direção de pesquisa específica (na verdade, acho que são um pouco interessantes), mas mais que não achamos que os teóricos da complexidade estão necessariamente interessados nos CTCs "por definição", mas há considerações adicionais que os levam a ser interessantes para muitos. (E, é claro, provavelmente nem todos os teóricos da complexidade os acham interessantes!) mas há considerações adicionais que os levam a ser interessantes para muitos. (E, é claro, provavelmente nem todos os teóricos da complexidade os acham interessantes!) mas há considerações adicionais que os levam a ser interessantes para muitos. (E, é claro, provavelmente nem todos os teóricos da complexidade os acham interessantes!)
fonte
Desculpe a resposta muito "ampla" de um não-teórico quântico, mas esse contraste pode ajudar: você pode descrever algoritmos como o estudo de como resolver problemas computacionais, enquanto a teoria da complexidade estuda os recursos (especialmente o tempo) necessários na teoria. para resolvê-los. Quão difíceis são esses problemas realmente em algum nível fundamental e como eles são classificados por requisitos de recursos? Essa questão é considerada interessante, independentemente de quantos tipos de recursos humanos insignificantes tenham à sua disposição.
A questão de quanto tempo é necessário na teoria para resolver um problema muda se você permitir CTCs; portanto, eles são interessantes para a teoria da complexidade por definição.
Então, sinto que sua primeira pergunta é como perguntar por que os teóricos da computabilidade estudariam graus de Turing maiores que zero; é o que eles fazem.
fonte
Se considerarmos a geodésica como uma análise geométrica da linha de mundo da pesquisa Grover, mostre em uma métrica que a pesquisa Grover segue uma geodésica. Sob pequenas perturbações também, a pesquisa Grover funciona bem. Além disso, dada uma perturbação, sob um tipo de métrica de kahler - a métrica de Fubini-Study - a pesquisa de Grover não pode seguir uma geodésica, veja estudo de perturbação . Referências para otimização e estudo geométrico das informações da pesquisa Grover .
Alvarez e cols. Começaram a mostrar que a pesquisa de Grover segue uma geodésica sob a métrica Fubini-Study, e eles exploraram outros algoritmos quânticos, como o algoritmo de Shors. Embora isso tenha sido feito no contexto das informações de Fisher, ainda mostrou que, na métrica de Fubini-Study, a pesquisa de Grover segue uma geodésica. Além disso, Alvarez e cols. Mostram sob suposições de informações de Fisher - "A fatoração de Shor não preserva as informações constantes de Fisher".
fonte