Supposons que nous avons construit un ordinateur quantique universel.
À l'exception des problèmes liés à la sécurité (cryptographie, confidentialité, ...), quels problèmes actuels du monde réel peuvent bénéficier de son utilisation?
Je suis intéressé par les deux:
- problèmes actuellement insolubles pour une entrée pratique,
- problèmes qui sont actuellement en cours de résolution, mais une accélération significative améliorerait considérablement leur facilité d'utilisation.
quantum-computing
application-of-theory
Piotr Migdal
la source
la source
Réponses:
Simuler efficacement la mécanique quantique.
la source
Brassard, Hoyer, Mosca et Tapp ont montré que la recherche généralisée de Grover, appelée amplification d'amplitude, peut être utilisée pour obtenir une accélération quadratique sur une grande classe d'heuristiques classiques. L'intuition derrière leur idée est que l'heuristique classique utilise l'aléatoire pour rechercher une solution à un problème donné, nous pouvons donc utiliser l'amplification d'amplitude pour rechercher l'ensemble de chaînes aléatoires pour une qui fera que l'heuristique trouvera une bonne solution. Cela donne une accélération quadratique dans le temps d'exécution de l'algorithme. Voir la section 3 du document lié ci-dessus pour plus de détails.
la source
Simuler des systèmes quantiques!
J'ai remarqué que dans l'autre réponse qui mentionnait cela, il y avait plusieurs commentaires à savoir si cela était vrai puisqu'il s'agit d'une affirmation non évidente. Et les gens ont demandé des références. Voici quelques références.
Proposition originale de Feynman:
Algorithmes efficaces pour tous les systèmes quantiques définis par des hamiltoniens "locaux". (Lloyd explique également que tout système compatible avec la relativité restreinte et générale évolue en fonction des interactions locales.)
Généralisation supplémentaire aux Hamiltoniens clairsemés, qui sont plus généraux que les Hamiltoniens locaux:
Lectures complémentaires:
la source
La vision est à la fois dangereuse et polémique dans ce domaine, nous devons donc être prudents avec ce sujet. Pourtant, certains algorithmes Q avec des accélérations polynomiales ont des applications potentielles intéressantes.
Il est connu que la recherche de Grover peut être utilisée pour trouver polynomialement la solution à des problèmes NP-complets [1] . Ceci est prouvé pour le 3-SAT dans [2] . Certaines applications de SAT, empruntées à [3] , sont: la vérification de l'équivalence des circuits , la génération automatique de motifs de test , la vérification des modèles à l'aide de la logique temporelle linéaire , la planification en intelligence artificielle et l' haplotypage en bioinformatique . Bien que je ne sache pas grand-chose sur ces sujets, cette ligne de recherche me semble plutôt pratique.
En outre, il existe un algorithme quantique pour évaluer les arbres NAND avec une accélération polynomiale par rapport au calcul classique [ 8 , 10 , 11 ]. L'arbre NAND est un exemple d'arbre de jeu, une structure de données plus générale utilisée pour étudier les matchs de jeux de société tels que Chess and Go. Il semble plausible que ce type d'accélérations puisse être utilisé pour concevoir des joueurs de jeux logiciels plus puissants. Cela pourrait-il intéresser certains développeurs de jeux vidéo quantiques?
Malheureusement, jouer à des jeux en réalité n'est pas exactement la même chose qu'évaluer des arbres: il y a des complications, par exemple, si vos joueurs n'utilisent pas des stratégies optimales [ 12 ]. Je n'ai vu aucune étude envisageant un scénario réel, il est donc difficile de dire dans quelle mesure l'accélération de [ 8 ] est bénéfique dans la pratique. Cela pourrait être un bon sujet de discussion.
la source
Je pense que vous avez soulevé une excellente question aux frontières de la recherche QM (partiellement indiquée par votre manque de réponses jusqu'à présent), mais elle n'a pas été entièrement formellement définie ou capturée comme un problème. la question est de savoir "qu'est-ce que les algorithmes QM peuvent exactement calculer de toute façon efficacement?" et une réponse complète n'est pas connue et est activement recherchée. une partie de cela est liée à la (questions ouvertes sur) la complexité des classes liées à QM.
ce serait le cas où une question quelque peu formelle est définie. s'il peut être démontré que les classes QM sont équivalentes à des classes non QM "significativement puissantes", alors il y a votre réponse. le thème général de ce type de résultat serait une classe "pas si difficile dans QM" est équivalente à une classe "dur dans non-QM". il existe différentes séparations de classes de complexité ouvertes de ce type (peut-être que quelqu'un d'autre peut les suggérer plus en détail).
quelque chose d'étrange à propos des connaissances QM actuelles sur les algorithmes quantiques est qu'il existe une sorte de sac à main étrange d'algorithmes qui sont connus pour fonctionner dans QM, mais il n'y a apparemment pas beaucoup de cohérence / cohésion pour eux. ils semblent étranges et déconnectés à certains égards. Il n'y a pas de "règle empirique" apparente pour les "problèmes qui sont calculables dans QM sont généralement sous cette forme" malgré une attente raisonnable que l'on pourrait être là.
par exemple, comparer cela à la théorie de la complétude de NP qui est beaucoup plus cohérente en comparaison. il semble que si la théorie QM est mieux développée, elle obtiendrait ce plus grand sentiment de cohésion qui rappelle la théorie de la complétude NP.
une idée plus forte pourrait être qu'à terme, lorsque la théorie de la complexité de la gestion de la qualité sera mieux étoffée, l'intégralité du NP s'intégrera "proprement" en quelque sorte.
Pour moi, l'accélération QM la plus générale ou la stratégie la plus largement applicable que j'ai vue semble être l'algorithme Grovers parce que beaucoup de logiciels pratiques sont liés aux requêtes db. et à certains égards, de plus en plus "non structurés":
la source