A computação quântica adiabática é tão poderosa quanto o modelo de circuito?

9

Grande parte da literatura da computação quântica se concentra no modelo de circuito. A computação quântica adiabática não se baseia na aplicação de uma sequência de operadores unitários, mas na alteração de um hamiltoniano dependente do tempo. Estou procurando informações sobre qualquer um dos seguintes.

  1. A computação quântica adiabática é tão poderosa quanto o modelo de circuito ou é inerentemente menos poderosa?
  2. Existem classes de complexidade especificamente relacionadas à computação adiabática em oposição ao modelo de circuito?
  3. Como se mede quantitativamente o poder da computação adiabática versus o poder do modelo de circuito?
cc.complexity-theory reference-request complexity-classes quantum-computing quantum-information vzn
fonte
ok NdB sim, não foi formulado da maneira perfeita, agradecendo aos respondentes para esclarecimentos, exatamente o que foi procurado. surgiu em reação a outra pergunta de pessoas no chat , pode continuar a discussão lá por qualquer pessoa interessada. Tenho certeza de que outros com maior número de representantes poderiam descobrir melhores perguntas, mas parece haver uma forte correlação inversa. quanto ao bkg, todos os árbitros que o fizeram foram cortados na 1ª edição. também, fez outra pergunta há muito tempo que levou a essa, mas essa outra pergunta foi vaporizada. poof
vzn
2
Eu vi a edição anterior. Os comunicados à imprensa não são artigos de pesquisa. Mais exatamente, qualquer artigo de pesquisa indicaria que a computação quântica adiabática é essencialmente baseada em qubit. Não importa o que a levou: sua pergunta não mostra muito esforço - e atividade por atividade é o que os fóruns do StackExchange tentam evitar .
Niel de Beaudrap 23/03
3
Vzn: o ponto principal é este: por que você não investiga isso sozinho? E se, depois de realmente investigar, você não encontrar referências, por que não fazer essa pergunta? Isso seria construtivo, e você poderia perguntar (e investigar) essa pergunta sobre a computação quântica em geral, não apenas a computação adiabática.
Niel de Beaudrap 23/03
4
@NieldeBeaudrap: Para mim, parecia que ele simplesmente usava o "modelo qubit" como substituto do modelo de circuito, o que obviamente não é uma substituição precisa, mas achei que esse era o significado da pergunta.
Joe Fitzsimons 23/03
11
@ JoeFitzsimons: justo o suficiente - essa é provavelmente a abordagem mais prática, pois implica que a pergunta tem uma resposta sensata, ou seja, as que estão abaixo. Embora vzn deva editar a pergunta para realmente fazer essa pergunta, se sim, para posteridade.
Niel de Beaudrap 24/03

Respostas:

19

Dois esclarecimentos rápidos:

  1. O controle de qualidade adiabático geralmente é "baseado em qubits", assim como o controle de qualidade baseado em circuito - não sei de onde você tirou a ideia de que não é! (Embora também se possa usar qutrits ou outros elementos básicos, tanto no circuito quanto nos modelos adiabáticos.)

  2. Como apontou Mateus, o resultado justamente famoso de Aharonov et al. afirma que "o controle de qualidade adiabático é equivalente ao controle de qualidade padrão". Mas esse resultado precisa ser interpretado com um pouco de cuidado. É válido se o estado final da computação adiabática puder ser arbitrário - para que, em particular, o estado final possa codificar toda a história de uma computação quântica baseada em circuito. No entanto, se o estado final precisar ser um estado básico computacional clássico - como normalmente está no algoritmo de otimização adiabática(o exemplo "original" de CQ adiabático) --- então o CQ adiabático certamente pode ser simulado no modelo de circuito, mas o inverso não é conhecido e está longe de ser claro. Portanto, com a última hipótese, é possível que a otimização adiabática realmente dê origem a uma nova classe de complexidade intermediária entre BPP e BQP.

Scott Aaronson
fonte
3
O artigo de Bacon e Flammia sobre computação adiabática de estado de cluster parece dar uma rota alternativa que, até onde eu posso ver, contorna um pouco a necessidade de uma história, embora você ainda tenha muitos qubits adicionais.
Joe Fitzsimons 23/03
2
No entanto, o esquema de Bacon e Flammia não possui um estado fundamental único e, portanto, difere significativamente do AQC convencional.
Norbert Schuch
3
@ NorbertSchuch: Mas se você adicionar os termos extras do estabilizador ao Hamiltoniano inicial correspondente à fixação do estado inicial, o estado fundamental será não degenerado.
21813 Joe Fitzsimons