Idées de projets d'informatique quantique

14

Je suis étudiant en informatique de premier cycle et je planifie actuellement mon projet de fin d'études. J'ai besoin de quelques idées dans le domaine de l'informatique quantique. de l'aide?

quantum-computing soft-question Deyaa
la source
Il serait utile de donner un exemple du type de projet que vous jugeriez approprié compte tenu du temps dont vous disposez pour ce projet et de la difficulté prévue. Comme la lecture d'un article en détail est-elle acceptable comme projet?
Robin Kothari
Exemple: combiner (ou en inventer de nouvelles) des techniques d'apprentissage automatique avec l'informatique quantique pour résoudre un problème difficile Google a utilisé des algorithmes d'apprentissage automatique et un ordinateur quantique à onde D pour effectuer une recherche d'images beaucoup plus rapide. Temps, j'ai: 11 mois de difficulté: moyen (premier cycle)
Deyaa
3
Je pense que cela devrait être un wiki communautaire, en supposant qu'il soit de portée.
Lev Reyzin
2
@ Ross: Je l'ai rétrogradé, tout simplement parce que la question n'était pas claire, très ouverte, subjective et certainement pas quelque chose avec une "réponse correcte" claire (voir aussi cstheory.stackexchange.com/faq ). Avec des explications plus précises et en mode "wiki communautaire", cela aurait très probablement évité mon downvote. Toutes mes excuses si cela semble inutilement dur, mais je pense que les gens devraient prêter plus d'attention à la formulation de leurs questions (et utiliser le drapeau CW correctement, d'autant plus que personne d'autre ne peut le réparer actuellement).
Jukka Suomela
3
@Deyaa, je pense qu'essayer de répondre aux questions de Joe Fitzsimmons et Jukka Suomela vous aidera à créer une meilleure question.
Suresh Venkat

Réponses:

27

J'ai posté quelques idées de projets de théorie de la complexité quantique sur http://scottaaronson.com/blog/?p=471

(Mais attention, la plupart de ces problèmes sont ouverts depuis des années! Ma suggestion pour un projet de premier cycle serait de rompre une partie de l'un des problèmes.)

Scott Aaronson
la source
17

Un projet que je suggérerais est le suivant: Essayez de développer un algorithme quantique basé sur la marche aléatoire quantique pour la programmation linéaire. Pour le projet, vous devez d'abord apprendre quelques faits de base sur les marches aléatoires quantiques et leur utilité algorithmique, deuxièmement sur les algorithmes de type simplex randomisés et troisièmement essayer de combiner les deux. La partie 3 est très ambitieuse et je ne sais pas si quelque chose de fructueux peut être dit du tout, mais les parties 1 et 2 sont déjà bien pour un projet de premier cycle.

Gil Kalai
la source
1
C'est une très bonne suggestion. Il existe en effet un bon nombre d'algorithmes qui pourraient bénéficier de marches aléatoires spécialisées. Les codes de correction d'erreur LT / Raptor sont basés sur une marche aléatoire par exemple. Up vote de moi. Et je suis ravi de vous voir ici, Gil. :-)
Ross Snider
Je ne savais pas qu'il y avait des choses comme des promenades aléatoires quantiques! bonne idée !
Suresh Venkat
2
Suresh: Oui, il y en a. Ils s'avèrent être une approche assez importante des algorithmes quantiques. La chose à propos des projets d'algorithmes, cependant, est qu'il est trivial d'obtenir une accélération de la racine carrée, et très très difficile d'obtenir quelque chose de mieux. Une autre idée serait peut-être d'envisager de réduire les algorithmes polynomiaux en temps pour enregistrer le temps, comme dans l'algorithme récent de résolution de systèmes linéaires d'équations.
Joe Fitzsimons
11

Les résultats DWaves avec recherche d'images sont un peu bizarres. Il n'y a actuellement aucune preuve solide que les appareils DWave ne peuvent pas être simulés efficacement. Cela a été discuté en détail sur un certain nombre de blogs (pour Scott Aaronson et Dave Bacon ont tous deux couvert DWave à plusieurs reprises).

Maintenant, en laissant cela de côté, il existe un grand nombre de projets potentiels, selon l'aspect de l'informatique quantique qui vous intéresse. Cela dépend également du niveau de vos connaissances en mécanique et physique quantiques. Les questions de type architecture deviennent souvent assez physiques, car les limites expérimentales jouent un grand rôle dans la détermination des problèmes qui méritent d'être examinés. Les algorithmes et la complexité des communications sont des domaines beaucoup plus orientés CS.

Il existe un certain nombre de modèles différents de calcul quantique, et il existe des barrières à l'entrée plus fortes pour certains plutôt que pour d'autres. L'informatique quantique adiabatique et topologique a tendance à être un peu plus difficile à intégrer que le modèle de circuit et le modèle de calcul basé sur des mesures.

Un problème sur lequel j'ai eu du succès avec un étudiant d'été travaillant était la approximation des seuils de tolérance aux pannes pour divers codes de correction d'erreur par simulation. C'est quelque chose qui a une barrière à l'entrée relativement faible. Une autre idée consiste à examiner les schémas d'automates cellulaires quantiques pour des tâches spéciales (codage, mesure, préparation d'état).

Vous avez mentionné l'apprentissage automatique, alors vous voudrez peut-être envisager d'utiliser la programmation évolutive pour faire évoluer les circuits quantiques pour divers problèmes simples. J'ai joué avec cela plusieurs fois, et il semble que vous pouvez obtenir un comportement assez agréable (par exemple, l'évolution des règles de recherche).

Je pourrais continuer à énumérer des idées aléatoires qui pourraient faire un projet approprié, mais si vous pouviez donner une idée plus précise du domaine qui vous intéresse, je pense que vous obtiendrez de meilleures réponses. Une question fondamentale pourrait simplement être: êtes-vous intéressé par un projet de codage, un sur la conception matérielle, un sur la théorie pure, etc.? Selon la direction que vous souhaitez prendre, il y aura une gamme de possibilités différentes.

Joe Fitzsimons
la source
4

Je suggère quelque chose comme fournir des outils actuels de développement de l'informatique quantique (tels que libquantum) avec la capacité de tirer parti des GPU compatibles CUDA pour accélérer les simulations. L'informatique quantique concerne plus ou moins l'algèbre linéaire, c'est-à-dire les opérations matricielles et vectorielles, pour lesquelles les GPU ont été conçus en premier lieu.

M. Alaggan
la source
des simulations comme quoi?
Deyaa
Les outils de développement de l'informatique quantique vous permettent de simuler des algorithmes et protocoles quantiques, y compris l'algorithme de Shor, la recherche de Grover, la téléportation quantique, les codes de correction d'erreurs et les algorithmes que vous avez créés et que vous souhaitez tester par vous-même.
M. Alaggan
3

Des langages à thème d'informatique quantique tels que QCL ont été créés pour des projets de thèse. En fait, tous les langages basés sur l'informatique quantique que j'ai vus implémentés sur le Web ont été réalisés pour des projets de thèse. Vous pouvez également essayer de coder un émulateur quantique. Dans le livre "Quantum Computing for Computer Scientists", ils fournissent des exercices de programmation qui s'ajoutent collectivement à un tel émulateur.

Vincent Russo
la source
2

Je ne sais pas à quel point cela sera utile, mais peut-être que cela offrira quelques conseils.

Au printemps 2009, Sasha Razborov a donné un cours sur l'informatique quantique. Le site Web du cours contient quelques idées de «projets», ainsi que des références à quelques articles quantiques séminaux.

Les "projets" sur la page ne sont en réalité que des "problèmes de devoirs plus impliqués", donc ils ne conviennent probablement pas en soi à une thèse de troisième cycle, et ils ne prendront pas 11 mois. Cependant, ces problèmes et / ou certaines des références pourraient susciter de bonnes idées pour vous.

Joshua Grochow
la source