Bom material introdutório sobre classes de complexidade computacional quântica

10

Desejo aprender mais sobre as classes de complexidade computacional no contexto da computação quântica.

O meio não é tão importante; pode ser um livro, notas de aula on-line ou algo semelhante. O que importa mais são os conteúdos.

O material deve abranger o básico das classes de complexidade computacional quântica e discutir as semelhanças, diferenças e relações entre elas e talvez também com as classes clássicas de complexidade computacional.

Eu preferiria um tratamento rigoroso a um tratamento intuitivo. O estilo do autor não importa.

Quanto aos pré-requisitos, não sei quase nada sobre o assunto, então talvez mais material independente seja melhor. Dito isto, eu provavelmente não leria um livro de 1000 páginas a menos que fosse fenomenalmente bom, qualquer coisa no intervalo de 1 a 500 páginas poderia funcionar.

Quanto à disponibilidade, é claro que eu preferiria material que não esteja protegido por algum tipo de barreira e possa ser encontrado on-line, mas esse não é um requisito estrito.

O que você recomenda?

complexity-theory resource-request Kiro
fonte
De um modo geral, solicitar recomendações para uma classe ou outros materiais não é considerado tópico sobre um site do Stack Exchange; mas esse assunto à parte, o tópico da sua postagem não é realmente sobre o assunto "computação quântica". Ensinar os conceitos de complexidade computacional é mais adequado ao nosso site de Ciência da Computação .
Robert Cartaino 11/04/19
@RobertCartaino Obrigado pelo feedback, deixe-me tentar abordar seus pontos. Eu estava solicitando material para auto-estudo, e solicitações de recursos são permitidas dentro de parâmetros . Vou tentar o meu melhor para modificar a questão para estar no tópico.
Kiro
11
@MEE Exceto se você ignorou o ponto crucial deste assunto: ensinar os rudimentos da complexidade computacional é apenas uma coincidência com os conhecimentos da computação quântica. Eu chamo isso de "o refrigerante favorito dos programadores" . É uma questão de ciência da computação em que adicionar "no contexto da computação quântica" não torna mais difícil o assunto aqui neste caso. Não importa; o usuário não tem uma pergunta sobre esse assunto e simplesmente deseja ir a outro lugar para encontrar essas informações. O que você decidir.
Robert Cartaino 12/04
@RobertCartaino ok, entendo seu ponto agora, não entendi bem o motivo do fechamento. Por isso, gostaria de retirar agora meu voto de reabertura, mas como isso não é possível, votei para encerrar esta pergunta.
MEE - Restabelece Monica
11
@RobertCartaino "os rudimentos da complexidade computacional são meramente coincidentes com os conhecimentos da computação quântica" Concordo que os 'rudimentos' são coincidentes, mas acho que a pergunta atualmente feita é sobre o assunto o suficiente para que eu possa consultar notas de aula sobre computação quântica como resposta. Concordo que a versão anterior seria realmente um caso de " o refrigerante favorito dos programadores ", mas acho que isso já foi resolvido até agora.
Lagarto discreto 12/04

Respostas:

7

Eu acho que a pesquisa de John Watrous é um ótimo lugar para começar (o professor Watrous me recomendou há muito tempo e estou viciado desde então!):

J. Watrous. Complexidade computacional quântica. Enciclopédia de Complexidade e Ciência de Sistemas, Springer, 2009. arXiv: 0804.3401 [quant-ph]

Que eu saiba, ele tem as classes de complexidade mais alta para a proporção da página.

Também gosto muito das notas de aula de Scott Aaronson para 2016 em Barbados:

S. Aaronson (com A. Bouland e L. Schaeffer). A complexidade dos estados e transformações quânticas: do dinheiro quântico aos buracos negros. ECCC TR16-109

Sanketh Menda
fonte
3

Posso recomendar as anotações das aulas de Ronald de Wolf, usadas em um curso do semestre ministrado por ele sobre computação quântica no contexto do programa holandês de 'Mastermath'.

O capítulo 10, "Teoria da complexidade quântica", cobre brevemente as classes de complexidade 'clássica', mas fornece antecedentes suficientes para falar sobre as classes de complexidade 'quântica' e compará-las com a clássica. Não cobre tudo, mas refere-se a outro material para leitura adicional.

O capítulo 12 "Complexidade da comunicação quântica" também é relevante e é mais técnico, principalmente porque a teoria da complexidade da comunicação tem aplicações interessantes na computação quântica.

Lagarto discreto
fonte