.svg)
Pourquoi y a-t-il autant d'algorithmes de tri ?
Wikipedia répertorie 43 algorithmes de tri différents. Tri rapide, tri par fusion, tri par coquille, tri par bulle, tri par pigeonnier, tri par étalement, tri par perle, tri par Stooge, et bien d'autres encore.
Pourquoi autant ?
Parce que différents algorithmes de tri sont utiles dans différentes circonstances.
- Certains d'entre eux (la sorte de bulle) sont simples à mettre en œuvre et donc utiles pour l'enseignement.
- Certains (tri par fusion, tri par tas) ont une limite relativement basse quant au nombre d'opérations qu'ils doivent effectuer dans le pire des cas. S'ils doivent trier N éléments, ils n'auront jamais besoin de plus de O(N log N) . Note : voir ici pour une définition de O()
- Certains (tri par insertion, tri cubique) ont un faible nombre d'opérations "dans le meilleur des cas", ce qui signifie qu'ils se terminent rapidement si la liste est déjà triée. Pour N éléments, leur nombre d'opérations dans le meilleur des cas sera O(N).
- Certains (tri par tas) ont besoin de très peu de mémoire
- Certains (comme les perles) ne fonctionnent qu'avec des nombres entiers positifs.
- D'autres... enfin, vous voyez ce que je veux dire.
Un ingénieur qui souhaite utiliser un algorithme de tri ferait bien de réfléchir aux caractéristiques des données à trier, aux contraintes du processeur, à la disponibilité de processeurs parallèles et à bien d'autres contraintes. Bien que certains algorithmes soient plus populaires que d'autres, il n'existe pas d'algorithme unique qui soit le meilleur dans toutes les circonstances.
Il en va de même pour les algorithmes quantiques.
Il n'existe pas d'implémentation unique de la préparation d'état qui soit toujours la meilleure. Certaines utilisent moins de qubits. Certaines sont plus précises. D'autres ont une profondeur plus faible. Le choix de la meilleure préparation d'état dépend donc du système que vous utilisez, mais aussi de ce qui se passe ailleurs : ce que vous faites en plus de la préparation d'état. La meilleure mise en œuvre n'est pas seulement décidée au niveau du bloc fonctionnel, mais aussi au niveau du système.
Même les additionneurs quantiques simples peuvent avoir plusieurs implémentations. Vous pouvez construire un simple additionneur ondulé ou effectuer de l'arithmétique quantique avec la transformée de Fourier quantique (QFT).
C'est pourquoi les meilleurs cadres de travail pour la génération de circuits quantiques proposeront plusieurs options - et feront peut-être eux-mêmes un choix optimal - au lieu de vous obliger à utiliser à chaque fois une seule implémentation codée en dur.
Wikipedia répertorie 43 algorithmes de tri différents. Tri rapide, tri par fusion, tri par coquille, tri par bulle, tri par pigeonnier, tri par étalement, tri par perle, tri par Stooge, et bien d'autres encore.
Pourquoi autant ?
Parce que différents algorithmes de tri sont utiles dans différentes circonstances.
- Certains d'entre eux (la sorte de bulle) sont simples à mettre en œuvre et donc utiles pour l'enseignement.
- Certains (tri par fusion, tri par tas) ont une limite relativement basse quant au nombre d'opérations qu'ils doivent effectuer dans le pire des cas. S'ils doivent trier N éléments, ils n'auront jamais besoin de plus de O(N log N) . Note : voir ici pour une définition de O()
- Certains (tri par insertion, tri cubique) ont un faible nombre d'opérations "dans le meilleur des cas", ce qui signifie qu'ils se terminent rapidement si la liste est déjà triée. Pour N éléments, leur nombre d'opérations dans le meilleur des cas sera O(N).
- Certains (tri par tas) ont besoin de très peu de mémoire
- Certains (comme les perles) ne fonctionnent qu'avec des nombres entiers positifs.
- D'autres... enfin, vous voyez ce que je veux dire.
Un ingénieur qui souhaite utiliser un algorithme de tri ferait bien de réfléchir aux caractéristiques des données à trier, aux contraintes du processeur, à la disponibilité de processeurs parallèles et à bien d'autres contraintes. Bien que certains algorithmes soient plus populaires que d'autres, il n'existe pas d'algorithme unique qui soit le meilleur dans toutes les circonstances.
Il en va de même pour les algorithmes quantiques.
Il n'existe pas d'implémentation unique de la préparation d'état qui soit toujours la meilleure. Certaines utilisent moins de qubits. Certaines sont plus précises. D'autres ont une profondeur plus faible. Le choix de la meilleure préparation d'état dépend donc du système que vous utilisez, mais aussi de ce qui se passe ailleurs : ce que vous faites en plus de la préparation d'état. La meilleure mise en œuvre n'est pas seulement décidée au niveau du bloc fonctionnel, mais aussi au niveau du système.
Même les additionneurs quantiques simples peuvent avoir plusieurs implémentations. Vous pouvez construire un simple additionneur ondulé ou effectuer de l'arithmétique quantique avec la transformée de Fourier quantique (QFT).
C'est pourquoi les meilleurs cadres de travail pour la génération de circuits quantiques proposeront plusieurs options - et feront peut-être eux-mêmes un choix optimal - au lieu de vous obliger à utiliser à chaque fois une seule implémentation codée en dur.
A propos de "The Qubit Guy's Podcast" (Le podcast du gars de Qubit)
Animé par The Qubit Guy (Yuval Boger, notre directeur marketing), le podcast accueille des leaders d'opinion de l'informatique quantique pour discuter de questions commerciales et techniques qui ont un impact sur l'écosystème de l'informatique quantique. Nos invités fournissent des informations intéressantes sur les logiciels et algorithmes d'ordinateurs quantiques, le matériel informatique quantique, les applications clés de l'informatique quantique, les études de marché de l'industrie quantique et bien plus encore.
Si vous souhaitez proposer un invité pour le podcast, veuillez nous contacter.
