Bon matériel d'introduction sur les classes de complexité de calcul quantique

10

Je souhaite en savoir plus sur les classes de complexité informatique dans le contexte de l'informatique quantique.

Le médium n'est pas si important; il peut s'agir d'un livre, de notes de cours en ligne ou similaires. Ce qui importe le plus, c'est le contenu.

Le matériel devrait couvrir les bases des classes de complexité de calcul quantique et discuter des similitudes, des différences et des relations entre elles et peut-être aussi avec les classes de complexité de calcul classiques.

Je préférerais un traitement rigoureux à un traitement intuitif. Le style de l'auteur n'a pas d'importance.

En ce qui concerne les conditions préalables, je ne sais presque rien sur le sujet, donc peut-être que plus de matériel autonome serait mieux. Cela étant dit, je ne lirais probablement pas un livre de 1000 pages à moins qu'il ne soit phénoménalement bon, n'importe quoi dans la gamme de 1 à 500 pages pourrait fonctionner.

En ce qui concerne la disponibilité, je préférerais bien sûr du matériel qui ne se trouve pas derrière un mur payant et qui puisse être trouvé en ligne, mais ce n'est pas une exigence stricte.

Que recommandez-vous?

complexity-theory resource-request Kiro
la source
De manière générale, la sollicitation de recommandations pour une classe ou d'autres documents n'est pas considérée sur le sujet d'un site Stack Exchange; mais cette question mise à part, le sujet de votre message n'est pas vraiment sur le sujet de "l'informatique quantique". L'enseignement des concepts de complexité informatique convient mieux à notre site informatique .
Robert Cartaino
@RobertCartaino Merci pour la rétroaction, permettez-moi d'essayer d'aborder vos points. Je demandais du matériel pour l'auto-apprentissage, et les demandes de ressources afaik sont autorisées dans les paramètres . Je ferai de mon mieux pour modifier la question pour qu'elle soit sur le sujet.
Kiro
1
@MEE Sauf que vous avez ignoré le nœud de ce sujet hors sujet - enseigner les rudiments de la complexité informatique n'est qu'une coïncidence avec l'expertise de l'informatique quantique. J'appelle ce problème "la boisson gazeuse préférée des programmeurs" . C'est un problème informatique où l'ajout de "dans le contexte de l'informatique quantique" ne fait pas plus de sujet ici dans ce cas. Peu importe; l'internaute n'a pas de question sur ce sujet, et il veut simplement aller ailleurs pour trouver cette information. Quoi que vous décidiez.
Robert Cartaino
@RobertCartaino ok, je comprends votre point maintenant, j'ai mal compris la raison de la fermeture. Je voudrais donc retirer mon vote de réouverture maintenant, mais comme ce n'est pas possible, j'ai voté pour clore cette question.
MEE - Rétablir Monica
1
@RobertCartaino "les rudiments de la complexité de calcul ne sont que des coïncidences avec l'expertise de l'informatique quantique" Je conviens que les "rudiments" sont coïncidents, mais je pense que la question telle qu'elle est actuellement posée est suffisamment thématique pour que je puisse me référer à des notes de cours sur l'informatique quantique comme réponse. Je suis d'accord que la version précédente serait en effet par un cas de " la boisson gazeuse préférée des programmeurs ", mais je pense que cela a été résolu maintenant.
Lézard discret

Réponses:

7

Je pense que l'enquête de John Watrous est un excellent point de départ (le professeur Watrous me l'a recommandé il y a très longtemps et je suis accro depuis!):

J. Watrous. Complexité informatique quantique. Encyclopédie de la complexité et de la science des systèmes, Springer, 2009. arXiv: 0804.3401 [quant-ph]

À ma connaissance, il présente le rapport classes / pages de complexité le plus élevé.

J'aime aussi beaucoup les notes de lecture de la Barbade de Scott Aaronson 2016:

S. Aaronson (avec A. Bouland et L. Schaeffer). La complexité des états quantiques et des transformations: de l'argent quantique aux trous noirs. ECCC TR16-109

Sanketh Menda
la source
3

Je peux recommander les notes de cours de Ronald de Wolf, utilisées pour un cours de semestre enseigné par lui sur l'informatique quantique dans le cadre du programme néerlandais «Mastermath».

Le chapitre 10 "Théorie de la complexité quantique", couvre brièvement les classes de complexité "classiques", mais donne suffisamment de contexte pour parler des classes de complexité "quantiques" et les comparer avec les classes classiques. Il ne couvre pas tout, mais renvoie à d'autres documents pour une lecture plus approfondie.

Le chapitre 12 «Complexité de la communication quantique» est également pertinent et plus technique, principalement parce que la théorie de la complexité de la communication a des applications intéressantes dans le calcul quantique.

Lézard discret
la source