Quels types de problèmes statistiques sont susceptibles de bénéficier de l'informatique quantique?

Nous sommes à l'avènement de l'informatique quantique , les langages quantiques anticipant les ordinateurs quantiques matériels désormais disponibles à des niveaux élevés et faibles pour les ordinateurs quantiques simulés. L'informatique quantique apporte de nouvelles fonctions élémentaires comme l' intrication et la téléportation des qubits, la mesure des qubits et l'imposition de superposition sur les qubits.

Quels types de problèmes statistiques sont susceptibles de bénéficier du calcul quantique?

Par exemple, les ordinateurs quantiques fourniront-ils une génération de nombres aléatoires véritablement plus omniprésente? Qu'en est-il de la génération de nombres pseudo-aléatoires à bas coût de calcul? L'informatique quantique aidera-t-elle à accélérer la convergence MCMC ou à garantir les limites supérieures du temps de convergence? Y aura-t-il des algorithmes quantiques pour d'autres estimateurs basés sur l'échantillonnage?

C'est une question large, et les réponses acceptables seront également larges, mais bravo s'ils différencient le calcul quantique et classique. (S'il s'agit d'une question trop large , veuillez m'aider à en faire une meilleure question.)

Les méthodes de force brute sont les plus susceptibles de bénéficier de ce qu'est l'informatique quantique. Pourquoi? Une explication physique possible du chemin d'une balle de baseball lancée est que tous les chemins quantiques possibles sont automatiquement explorés et que le chemin de moindre dépense d'énergie, c'est-à-dire le chemin de moindre résistance disponible, est choisi, et tout cela sans avoir à construire de calculatrice. ; les calculs sont ineffables. Généralisation; la nature peut être considérée comme une calculatrice quantique. Ainsi, les problèmes similaires, ceux qui optimisent, comme la minimisation de la régression de certains critères, sont que la qualité de l'ajustement ou autre (la qualité de l'ajustement est, dans certains cas, mal posée) sont ceux qui en bénéficieront.

BTW, les étapes intermédiaires; les itérations, en optimisation ne seraient pas calculées, seul le résultat final, tout comme lorsqu'un terrain de baseball se produit. Autrement dit, seul le chemin réel du baseball se produit, les chemins alternatifs sont automatiquement exclus. Une différence entre une implémentation statistique et un événement physique est, cependant, que l'erreur du calcul statistique peut être faite aussi petite que souhaité en augmentant arbitrairement la précision, (par exemple, à 65 décimales), et cela n'est généralement pas réalisable physiquement . Par exemple, même une machine à lancer ne lancera pas une balle de baseball dans une voie exactement dupliquée.

J'ai aimé la réponse ci-dessus sur le baseball. Mais je serais prudent quant à ce que l'informatique quantique pourrait bien faire.

Il semble que cela pourrait très bien faire dans des choses comme le craquage de schémas cryptographiques et autres: être capable de superposer toutes les solutions puis de s'effondrer sur la solution réelle pourrait aller assez vite.

Mais dans les années 1980 - il y a très longtemps - il y avait une entreprise très en vue nommée Thinking Machines. Voir cet article: https://en.wikipedia.org/wiki/Thinking_Machines_Corporation

L'idée entière avait une bouffée d'informatique quantique. Il a utilisé un arrangement d'hypercube à n dimensions. Imaginez, si vous voulez, quatre microprocesseurs (très simples) connectés dans un carré. Chacun pourrait faire un calcul, puis partager le résultat avec le processeur avant (dans le sens antihoraire), après (dans le sens horaire), ou en face (à travers). Imaginez ensuite 8 processeurs dans un cube qui peuvent étendre ce concept à trois dimensions (chaque processeur peut désormais partager sa sortie avec un ou plusieurs des 7 autres: 3 le long d'un sommet du cube; trois sur la face d'un carré auquel le processeur faisait partie de, et une diagonale dans 3 espaces).

Prenons maintenant ceci, avec peut-être 64 processeurs dans un hypercube à 6 dimensions.

C'était l'une des idées les plus en vogue de l'époque (avec la machine Lisp 34 bits dédiée que Symbolics a mise en place et le système de mémoire cache un peu bizarre mis en place par Kendall Square Research - les deux ont des pages wikipedia qui valent la peine d'être lues).

Le problème était qu'il y avait précisément un, et un seul algorithme qui fonctionnait bien sur l'architecture TM: une transformation de Fourier rapide utilisant ce qu'on appelait le "Perfect Shuffle Algorithm". C'était un aperçu génial de la façon d'utiliser une technique de masque binaire, l'algorithme sur mesure et l'architecture pour traiter en parallèle une FFT d'une manière brillamment intelligente et rapide. Mais je ne pense pas qu'ils aient jamais trouvé un autre usage unique pour cela. (voir cette question connexe: /cs/10572/perfect-shuffle-in-parallel-processing )

Je suis là depuis assez longtemps pour réaliser que les technologies qui semblent brillantes et puissantes finissent souvent par ne pas résoudre un problème (ou suffisamment de problèmes) pour les rendre utiles.

Il y avait beaucoup d'idées brillantes à l'époque: TM, Symbolics, KSR, ainsi que Tandem (disparu) et Stratus (étonnamment, toujours vivant). Tout le monde pensait que ces entreprises - au moins certaines d'entre elles - allaient conquérir le monde et révolutionner l'informatique.

Mais, à la place, nous avons eu FaceBook.

Quels types de problèmes statistiques sont susceptibles de bénéficier de l'informatique quantique?

À la page 645 de « Chimie physique: concepts et théorie », Kenneth S. Schmitz explique:

Les effets quantiques deviennent importants lorsque la longueur d'onde de Broglie devient comparable ou supérieure aux dimensions de la particule. Lorsque cela se produit, les fonctions d'onde peuvent se chevaucher, donnant différentes propriétés du système.

Les systèmes macroscopiques peuvent être analysés par des méthodes classiques, comme l'explique cette page Wikipedia:

Une considération plus raffinée distingue la mécanique classique et la mécanique quantique sur la base que la mécanique classique ne reconnaît pas que la matière et l'énergie ne peuvent pas être divisées en parcelles infinitésimales, de sorte que finalement une division fine révèle des caractéristiques granulaires irréductibles. Le critère de finesse est de savoir si les interactions sont décrites ou non en termes de constante de Planck. En gros, la mécanique classique considère les particules en termes mathématiquement idéalisés, même aussi fines que des points géométriques sans magnitude, ayant toujours leurs masses finies. La mécanique classique considère également les matériaux étendus idéalisés mathématiquement comme substantiellement géométriquement continus. De telles idéalisations sont utiles pour la plupart des calculs quotidiens, mais peuvent échouer entièrement pour les molécules, les atomes, les photons et autres particules élémentaires. De plusieurs façons, la mécanique classique peut être considérée comme une théorie principalement macroscopique. À une échelle beaucoup plus petite d'atomes et de molécules, la mécanique classique peut échouer, et les interactions des particules sont ensuite décrites par la mécanique quantique.

Par exemple, les ordinateurs quantiques fourniront-ils une véritable génération de nombres aléatoires plus omniprésente ?

Non. Vous n'avez pas besoin d'un ordinateur pour générer un vrai nombre aléatoire, et utiliser un ordinateur quantique pour le faire serait un énorme gaspillage de ressources sans amélioration du caractère aléatoire.

ID Quantique a disponibles, SoC autonomes et les cartes PCIe à vendre pour de U $ 1200 à U $ 3500 . C'est un peu plus que des photons voyageant à travers un miroir semi-transparent, mais il a suffisamment de propriétés aléatoires quantiques pour passer AIS 31 ("Classes de fonctionnalité et méthodologie d'évaluation pour un vrai générateur de nombres aléatoires (physique) - Version 3.1 29 septembre 2001" .PDF ). Voici comment ils décrivent leur méthode:

Quantis est un générateur de nombres aléatoires physiques exploitant un processus d'optique quantique élémentaire. Les photons - particules de lumière - sont envoyés un par un sur un miroir semi-transparent et détectés. Ces événements exclusifs (réflexion - transmission) sont associés à des valeurs binaires «0» - «1». Cela nous permet de garantir un système véritablement impartial et imprévisible.

Un système plus rapide (1 Gbit / s) est proposé par QuintessenceLabs . Leur générateur de nombres aléatoires quantiques «qStream» est conforme au NIST SP 800-90A et répond aux exigences du projet NIST SP 800 90B et C. Il utilise des diodes tunnel Esaki . Leurs produits sont nouveaux et les prix ne sont pas encore accessibles au public.

Des systèmes de Comscire sont également disponibles pour plusieurs centaines à quelques milliers de dollars. Leurs méthodes et brevets PCQNG et RNG post-quantique sont expliqués sur leur site Web.

Quantum Numbers Corp. a développé un appareil de la taille d'une puce pour produire rapidement (1 Gbit / s) des nombres aléatoires quantiques qui, selon eux, seront bientôt disponibles.

Qu'en est-il de la génération de nombres pseudo-aléatoires à bas coût de calcul?

Si vous voulez dire "bon marché sur le plan du calcul" comme dans peu d'instructions et exécution rapide = oui.

Si vous voulez dire que n'importe quel ordinateur est un moyen peu coûteux de générer de vrais nombres aléatoires = non.

Toute propriété implémentée QRNG ne produira pas de nombres pseudo aléatoires.

L'informatique quantique aidera-t-elle à accélérer la convergence de la chaîne de Markov Monte-Carlo (MCMC) ou garantira-t-elle des limites supérieures sur le temps de convergence?

Je vais laisser quelqu'un d'autre faire un essai là-dessus pour l'instant.

Y aura-t-il des algorithmes quantiques pour d'autres estimateurs basés sur l'échantillonnage?

Probablement.

Veuillez modifier et améliorer cette réponse Wiki.