Quelle est la complexité temporelle (et non la complexité des requêtes) de l'algorithme de Grover? Il me semble clair qu'il s'agit de car il existe des itérations et chaque itération nécessite l'utilisation de l'opération de réflexion qui à son tour prend du temps utilisant n'importe quel ensemble...
Dans le calcul quantique et l'information quantique de Nielsen et Chuang, ils disent que de nombreux algorithmes basés sur les transformées de Fourier quantiques reposent sur la propriété d'invariance de Coset des transformées de Fourier et suggèrent que les propriétés d'invariance d'autres...
Dans son article de 1995 Algorithmes à temps polynomial pour la factorisation principale et les logarithmes discrets sur un ordinateur quantique , Peter W. Shor discute d'une amélioration de la partie recherche d'ordres de son algorithme de factorisation. Les sorties algorithme standard , un...
Il est bien connu que les ordinateurs quantiques sont strictement plus puissants que leurs homologues classiques en termes de complexité des requêtes . Existe-t-il d'autres modèles (naturels ou artificiels) qui se situent strictement entre le quantique et le classique en termes de complexité des...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Par curiosité, si le calcul classique concerne les matrices de permutation et l'informatique quantique concerne les matrices unitaires (dont les matrices de permutation sont un sous-groupe), y aura-t-il un paradigme de calcul au-delà des matrices
Je suis physicien dans l'âme et je pense donc que l'informatique quantique à sens unique est géniale. En particulier, l'informatique quantique basée sur la mesure de l'état des graphes (MBQC) a été un très bon développement dans la recherche sur l'informatique quantique, à l'origine de Raussendorf...
Quelles universités ont un solide programme d'informatique quantique et proposent un certain type de cours d'informatique quantique / d'information / de recherche? Le but ici est de rassembler une liste utile pour ceux qui envisagent des études supérieures dans ces domaines, et non de discuter de...
Récemment, Watrous et al ont prouvé que QIP (3) = PSPACE un résultat remarquable. Ce fut pour moi un résultat surprenant pour le moins et cela m'a fait réfléchir ... Je me demandais si les ordinateurs quantiques pouvaient être simulés efficacement par les ordinateurs classiques. Serait-ce...
Le calcul quantique est un domaine de recherche actif qui vise à tirer parti de la physique quantique (par exemple l'intrication quantique) pour faire progresser les capacités d'efficacité des ordinateurs (ne modifie pas la thèse de Church-Turing ). Quelles sont les expériences les plus importantes...
Une chose que les ordinateurs quantiques peuvent faire (peut-être même avec seulement des circuits quantiques BPP + log-depth) est d'échantillonner approximativement la transformée de Fourier d'une fonction booléenne évaluée en P.±1±1\pm 1 Ici et ci-dessous quand je parle d'échantillonner la...
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...
La méthode de l'adversaire négatif ( ) est un SDP qui caractérise la complexité des requêtes quantiques. Il s'agit d'une généralisation de la méthode de l'adversaire largement utilisée ( ), et surmonte les deux obstacles qui ont entravé la méthode de l'adversaire:A D V±UNEréV±ADV^\pmA D VUNEréVADV...
(également demandé ici , pas de réponses) Un expanseur quantique est une distribution sur le groupe unitaire avec la propriété que: a) , b) , où \ mu_H est la mesure de Haar. Si , au lieu des distributions sur unitaries nous considérons les distributions sur les matrices de permutation, il est...
Comme cela est bien connu, la PARITÉ ne peut pas être effectuée dans des circuits de profondeur constante de taille poly, et en fait, les circuits const-dept nécessitent un nombre de portes EXP. Qu'en est-il des circuits QUANTUM? a) La PARITE peut-elle être effectuée avec un circuit quantique qui a...
Le calcul quantique limité dans le temps est évidemment très intéressant. Qu'en est-il du calcul quantique limité dans l'espace? Je connais de nombreux résultats intéressants pour le calcul quantique avec des limites d'espace sublogarithmiques et divers types de modèles d'automates quantiques. D'un...
Que dois-je lire pour comprendre ce problème? La puissance des circuits quantiques de faible profondeur. Est-ce que ? En d'autres termes, la partie "quantique" de tout algorithme quantique peut-elle être compressée à la profondeur du polylogue (n), à condition que nous soyons prêts à effectuer un...
Dans "Quantum Computation and Quantum Information" de Mike et Ike, l'algorithme de Grover est expliqué en détail. Cependant, dans le livre, et dans toutes les explications que j'ai trouvées en ligne pour l'algorithme de Grover, il ne semble pas y avoir de mention de la façon dont l'Oracle de Grover...
Le problème suivant apparaît dans la liste d'Aaronson Dix demi-grands défis pour la théorie de l'informatique quantique . Est-ce que BQP=BPPBQNCBQP=BPPBQNC\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} En d'autres termes, la partie "quantique" de n'importe quel algorithme quantique peut-elle être...
La classe de complexité BQP correspond à des sous-programmes quantiques polynomiaux temporels prenant des entrées classiques et crachant une sortie classique probabiliste. Le conseil quantique le modifie pour inclure des copies de certains états de conseil quantique prédéterminés mais avec des...