Le BQP n'est-il que temps? Est-ce significatif?

La classe de complexité BQP (temps polynomial quantique à erreur bornée) semble être définie uniquement en considérant le facteur temps. Est-ce toujours significatif? Existe-t-il des algorithmes où le temps de calcul évolue de manière polynomiale avec la taille d'entrée, mais d'autres ressources telles que l'échelle de la mémoire de manière exponentielle?

Le BQP est défini en fonction de la taille du circuit , c'est-à-dire du nombre total de portes. Cela signifie qu'il intègre:

• Nombre de qubits - car nous pouvons ignorer tous les qubits qui ne sont pas traités par une porte. Ce sera polynomialement lié à la taille d'entrée, et souvent un polynôme modeste (par exemple, l'algorithme de Shor n'implique qu'un nombre de qubits qui est un facteur constant multiplié par la taille d'entrée).
• Profondeur du circuit (ou «temps») - car le calcul peut prendre le plus de temps si nous effectuons une porte après l'autre, sans effectuer aucune opération en parallèle.
• Communication avec les systèmes de contrôle - parce que les portes en cours d'exécution sont prises à partir d'un ensemble de portes finies, et même si nous autorisons des mesures intermédiaires, la quantité de communication requise pour indiquer le résultat de la mesure et la quantité de calcul requise pour déterminer ce qui sera fait ensuite est généralement une constante pour chaque opération.
• Interactions entre systèmes quantiques - même si nous considérons une architecture qui n'a pas d'interactions tout-à-tout ou quoi que ce soit proche, nous pouvons simuler avoir cette connectivité en effectuant des opérations SWAP explicites, qui peuvent elles-mêmes être décomposées en un nombre constant de deux -opérations de qubit. Cela pourrait nous donner un surcoût polynomial notable qui influe sur la façon dont un algorithme est pratique pour une architecture donnée, mais cela ne cache pas une quantité exponentielle de travail.
• Énergie - encore une fois parce que les circuits sont décomposés en un ensemble de portes fini, il n'y a aucun moyen évident d'obtenir une accélération apparente en "faisant les portes plus rapidement" ou en cachant le travail dans une interaction exotique, si notre limite est en termes de le nombre d'opérations effectuées à partir d'un ensemble d'opérations assez basique. Cette considération est plus importante dans l'informatique quantique adiabatique: nous ne pouvons pas essayer d'éviter de petits écarts simplement en amplifiant tout le paysage énergétique autant que nous le voulons - ce qui signifie que nous devons prendre plus de temps pour faire le calcul à la place, correspondant dans l'image du circuit à un circuit avec plus de portes.

En effet, compter le nombre de portes d'un ensemble de taille constante capture de nombreuses choses dont vous pourriez vous inquiéter en tant que ressources pratiques: cela laisse très peu d'espace pour cacher tout ce qui est secrètement très cher.

$O(1)$

$O(1)$

Je pense qu'il est plus clair que le comptage des opérations élémentaires est une mesure fondamentale et importante du nombre de ressources requises par un algorithme, car nous pouvons toujours décider du nombre de ressources dont chaque opération élémentaire a besoin.

Alors que dans la définition de BQP et pour les algorithmes quantiques, nous considérons la complexité du circuit au lieu de la `` complexité de fonctionnement '', la complexité du circuit peut à nouveau être définie en termes d'opérations sur les machines de Turing, donc le même raisonnement s'applique.