Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Enhanced Grover's algorithm solutions for active user detection in wireless networks

Muhammad Idham Habibie

Published Dec 14, 2023• 0 citations
Publisher

Abstract

Solutions améliorées de l'algorithme de Grover pour la détection d'utilisateurs actifs dans les résaux sans fil 5G comprend des fonctionnalités telles que Ultra-fiables à faible latence (URLLC) et Massives entre machines (mMTC) pour minimiser les délais et connecter de nombreux appareils. Cela nécessite un schéma Détection des utilisateurs Actifs (AUD), nécessitant une détection en temps réel par Base Station (BS). Maximum de Vraisemblance (ML) est le plus performant pour AUD mais il est complexe. Pour simplifier, des alternatives comme CCR et ZF ont été introduites mais ne peuvent égaler les performances de ML. Pour y remédier, nous explorons l’algorithme de Grover, connu pour ses capacités de superposition (travail avec 0 et 1), superposition (travailler avec 0 et 1 en même temps). Cependant, l’algorithme de Grover, lorsqu’il est contraint par la fonction f(x) = δ, n’est pas aussi performant que ML ; il est plus proche de CCR et de ZF. Pour atteindre les performances de ML, l’algorithme de Grover doit être modifié pour trouver la distance minimale, comme ML la distance minimale, comme le fait ML. Nous proposons un nouvel algorithme, à savoir Algorithme Amélioré de Recherche de Minimum par Itération (IIMSA), visant à améliorer les algorithmes existants Boyer-Brassard-Høyer-Tapp (BBHT) et Durr-Hoyer Algorithm (DHA), qui sont les méthodes prometteuses pour trouver le minimum à l’aide de l’algorithme de Grover afin de réduire leur complexité tout en maintenant des performances élevées. L’idée est d’utiliser n’importe quel nombre aléatoire de solutions plutôt que d’effectuer L itérations aléatoires comme le suggère DHA. Nous incorporons également des méthodes classiques telles que ZF et CCR pour améliorer leurs performances et réduire la complexité. Nous adaptons également l’algorithme de Grover dans le contexte de AUD dans cette thèse. Nous présentons également un algorithme de Grover amélioré inspiré d’une solution hybride quantique qui exploite à la fois des éléments quantiques et classiques, solution hybride quantique qui exploite à la fois des éléments quantiques et classiques. L’objectif principal est d’augmenter la probabilité de succès Ps et de réduire la complexité de l’algorithme original de Grover de l’algorithme de Grover original. Le concept consiste à utiliser moins d’itérations de Grover que le nombre optimal, dénommé Ps. que le nombre optimal, noté Lopt, et de le combiner avec la probabilité de succès classique. Nous pensons que cette approche a le potentiel de modifier le comportement de la complexité et d’obtenir une probabilité de succès élevé et d’atteindre une probabilité de succès élevée.

DOI
10.70675/d6d3e7acz4e21z465azb300zfc39183aef32

Related papers

Adaptation de l’algorithme quantique de Grover à la détection multi-utilisateurs dans un système OCDMA

Muhammad Idham Habibie, Jihad Hamie, Claire Goursaud

Pour prendre en charge les transmissions multiples dans une fibre optique, plusieurs techniques ont été étudiées, comme l’accès multiple par répartition en code (OCDMA). En particulier, les systèmes OCDMA incohérents sont appréciés pour leur simplicité. Cependant, ils souffrent de l’interférence d’accès multiple (MAI), qui dégrade les performances. Afin de faire face à cette MAI, plusieurs détecteurs ont été étudiés. Parmi eux, le Maximum Likelihood (ML) est le meilleur. Mais il est très coûteux, car il nécessite tester toutes les possibilités avant de prendre une décision. Cependant, grâce aux récentes avancées de l’informatique quantique, ce problème de complexité peut être contourné. En effet, les algorithmes quantiques, tels que Grover, exploitent les états de superposition dans le domaine quantique et permettent d’accélérer le calcul. Ainsi, dans cet article, nous proposons d’adapter l’algorithme quantique de Grover dans le contexte de la détection multi-utilisateurs, dans un système OCDMA utilisant des codesnon-orthogonaux. Nous présentons un moyen d’adapter le signal bruité reçu aux contraintes définies par l’algorithme de Grover, et évaluons ensuite la probabilité de succès du récepteur quantique. Nous montrons les avantages de notre proposition par rapport au détecteur classique et au détecteur ML optimal.

•Aug 28, 2023•0 citations

Comparaison des performances des algorithmes classiques et quantiques pour la détection dans un système NOMA

Muhammad Idham Habibie, Jihad Hamie, Claire Goursaud

-L'un des freins des systèmes NOMA (Non orthogonal Multiple access) est la complexité de détection des utilisateurs actifs (AUD: Active User Detection). Nous proposons dans cet article d'utiliser une version adaptée de l'algorithme quantique de Grover pour la détection des utilisateurs actifs afin de tirer partie de l'accélération apportée par la superposition d'états dans les architectures quantiques, Notre version adaptée de l'algorithme de Grover est comparée aux deux récepteurs classiques de référence : le récepteur optimal du maximum de vraisemblance (ML: Maximum Likelihood) et le récepteur basique d'intercorrelation conventionnel (CCR: Conventional Correlation Receiver). La probabilité de détection des utilisateurs actifs est évaluée en fonction du SNR (Signal to Noise Ratio) du signal reçu, où les résultats obtenus prouvent que notre algorithme de Grover adapté est très prometteur sous un faible niveau de bruit.

•Sep 5, 2022•0 citations

Towards efficient quantum algorithms for optimization and sampling

Dániel Szilágyi

Vers des algorithmes quantiques efficaces pour l'optimisation et l'échantillonnage Récemment, avec l'avènement du big data et de l'apprentissage machine à grande échelle, il y a eu une demande croissante pour des algorithmes quantiques qui seraient plus directement applicables à des problèmes pertinents en pratique. Dans cette thèse, nous présentons trois algorithmes qui visent à nous rapprocher de cet objectif. Premièrement, nous développons un algorithme quantique pour l'optimisation cornettique, une classe de problèmes d'optimisation qui se situe entre les programmes linéaires et semi-définis en termes d'expressivité et de facilité de résolution. Ces problèmes sont le plus souvent résolus avec l'aide d'une méthode de point intérieur, dont la complexité est principalement imposée par le coût de la résolution d'une série de systèmes linéaires. Dans notre algorithme, nous résolvons ces systèmes linéaires de manière approximative à l'aide d'un algorithme quantique, et nous prouvons que la méthode des points intérieurs qui en résulte converge vers la solution correcte en un même nombre d'itérations. Nous donnons des preuves numériques que l'algorithme fournit des accélérations de bout en bout dans certaines applications de faible précision telles que les machines à vecteurs de support et l'optimisation de portefeuille financier. L'algorithme des systèmes linéaires quantiques que nous utilisons est le résultat d'une longue ligne de recherche engendrée par l'algorithme de système linéaire quantique de Harrow, Hassidim et Lloyd. Bien qu'il ait été prouvé qu'il est asymptotiquement optimal, le circuit correspondant compliqué et nécessite un prétraitement classique. La deuxième contribution de cette thèse est un algorithme quantique amélioré pour les systèmes linéaires, basé sur la méthode classique optimale de l'itération de Chebyshev. Enfin, nous observons que les algorithmes susmentionnés ont la propriété commune d'approximer l'unique vraie solution du problème donné. En général, la conception de tels algorithmes quantiques est difficile, car souvent la seule façon de récupérer (une approximation de) la vraie solution est d'exécuter l'algorithme plusieurs fois (soit naïvement, soit par amplification d'amplitude) et de calculer certaines statistiques (par exemple la moyenne) des sorties mesurées. Si les ordinateurs quantiques donnent intrinsèquement accès à l'échantillonnage de leurs sorties, pourrions-nous les exploiter pour accélérer les problèmes d'échantillonnage classiques? De manière surprenante, il s'avère que l'échantillonnage gaussien n'est pas un problème complètement résolu, même sur les ordinateurs classiques. Notre troisième contribution est un algorithme de Monte Carlo Hamiltonien classique pour l'échantillonnage gaussien dans le modèle d'interrogation du premier ordre. Nous surmontons et contournons plusieurs limites inférieures en prenant des étapes longues et aléatoires pour intégrer le hamiltonien au cœur de l'algorithme.

•Oct 20, 2022•0 citations

Adiabatic quantum computation

Jérémie Roland, Nicolas J. Cerf

Le développement de la Théorie du Calcul Quantique provient de l'idée qu'un ordinateur est avant tout un système physique, de sorte que ce sont les lois de la Nature elles-mêmes qui constituent une limite ultime sur ce qui peut être calculé ou non. L'intérêt pour cette discipline fut stimulé par la découverte par Peter Shor d'un algorithme quantique rapide pour factoriser un nombre, alors qu'actuellement un tel algorithme n'est pas connu en Théorie du Calcul Classique. Un autre résultat important fut la construction par Lov Grover d'un algorithme capable de retrouver un élément dans une base de donnée non-structurée avec un gain de complexité quadratique par rapport à tout algorithme classique. Alors que ces algorithmes quantiques sont exprimés dans le modèle ``standard' du Calcul Quantique, où le registre évolue de manière discrète dans le temps sous l'application successive de portes quantiques, un nouveau type d'algorithme a été récemment introduit, où le registre évolue continûment dans le temps sous l'action d'un Hamiltonien. Ainsi, l'idée à la base du Calcul Quantique Adiabatique, proposée par Edward Farhi et ses collaborateurs, est d'utiliser un outil traditionnel de la Mécanique Quantique, à savoir le Théorème Adiabatique, pour concevoir des algorithmes quantiques où le registre évolue sous l'influence d'un Hamiltonien variant très lentement, assurant une évolution adiabatique du système. Dans cette thèse, nous montrons tout d'abord comment reproduire le gain quadratique de l'algorithme de Grover au moyen d'un algorithme quantique adiabatique. Ensuite, nous montrons qu'il est possible de traduire ce nouvel algorithme adiabatique, ainsi qu'un autre algorithme de recherche à évolution Hamiltonienne, dans le formalisme des circuits quantiques, de sorte que l'on obtient ainsi trois algorithmes quantiques de recherche très proches dans leur principe. Par la suite, nous utilisons ces résultats pour construire un algorithme adiabatique pour résoudre des problèmes avec structure, utilisant une technique, dite de ``nesting', développée auparavant dans le cadre d'algorithmes quantiques de type circuit. Enfin, nous analysons la résistance au bruit de ces algorithmes adiabatiques, en introduisant un modèle de bruit utilisant la théorie des matrices aléatoires et en étudiant son effet par la théorie des perturbations.

•Sep 28, 2004•1 citation

Quantum algorithms for NOMA systems

Romain Piron

Algorithmes quantiques dédiés aux systèmes NOMA Le nombre croissant d'appareils connectés dans les réseaux sans fil de cinquième génération (5G) nécessite le développement de nouveaux protocoles d'accès afin de gérer efficacement les ressources limitées disponibles, notamment grâce à l'utilisation de schémas d'accès multiple non orthogonaux (NOMA). Dans ce contexte, des solutions algorithmiques pour la récupération de données sont essentielles pour répondre aux exigences strictes en matière de latence tout en assurant le déploiement d'un nombre massif d'appareils. Alors que les solutions conventionnelles impliquent souvent un compromis entre performance et complexité computationnelle, l'émergence de nouveaux paradigmes de calcul - tels que l'informatique quantique - offre la possibilité de dépasser ces limitations. Cette thèse explore l'application de l'informatique quantique au problème de la détection d'activité dans les réseaux sans fil. Nous commençons par formuler une représentation quantique fidèle du problème, conforme à la fois aux axiomes de la mécanique quantique et aux contraintes technologiques du matériel quantique actuel. Nous apportons également des éclairages physiques sur les systèmes quantiques distribués et illustrons, à travers des simulations numériques, les défis liés à la mise en œuvre de protocoles d'intrication évolutifs entre qubits spatialement séparés. Ensuite, nous adoptons la perspective des réseaux sans fil afin d'optimiser les algorithmes implémentés pour le problème de détection d'activité. À cette fin, des simulations numériques d'annealing quantique sont réalisées. Nous proposons une stratégie de planification générique pour le processus d'annealing et menons une étude afin d'identifier les paramètres les plus critiques pour la convergence des algorithmes quantiques.

•Oct 16, 2025•0 citations

Quantum Computing for Operations Research : A special approach for Project Scheduling

Luis Fernando Pérez Armas

Informatique quantique pour la recherche opérationnelle : une approche spéciale pour ordonnancement de projet Le calcul quantique, avec son potentiel profond, a suscité une attention significative ; cependant, son intégration dans la Recherche Opérationnelle (RO) reste naissante. Cette dissertation tente de combler cette lacune en introduisant des algorithmes innovants ancrés dans les principes du calcul quantique pour s'attaquer aux problèmes d'optimisation discrets. La première partie se concentre sur les fondamentaux du calcul quantique et analyse l'algorithme de Grover. Peut-être l'algorithme quantique le plus important, qui est renommé pour son accélération quadratique dans les recherches non structurées. En tirant parti de l'algorithme de Grover, l'étude présente une procédure qui résout efficacement le problème du sac à dos binaire, surmontant des défis souvent négligés dans la littérature sur le calcul quantique.Dans la seconde partie, la thèse affine la performance des algorithmes développés dans le premier chapitre, introduisant deux procédures novatrices : un algorithme hybride de branchement et de bornage et un algorithme d'ascension aléatoire. Ces procédures se révèlent capables d'égaler la performance des algorithmes classiques leaders sur 66000 instances du problème du sac à dos binaire. Notablement, elles étendent leur applicabilité aux problèmes d'optimisation discrets manquant de structures claires, démontrant le potentiel des approches inspirées par le quantique.Dans la troisième partie, l'exploration s'étend à l'examen des limites des algorithmes quantiques existants dans la résolution des problèmes d'optimisation discrets. L'étude évalue de manière critique les algorithmes de comptage quantique, ainsi que les variantes de l'algorithme de Grover telles que la recherche quantique imbriquée, les marches quantiques, et l'algorithme d'amplification d'amplitude, révélant des instances où les contreparties classiques peuvent dominer.Dans la quatrième partie de cette dissertation, nous explorons une avenue prometteuse du calcul quantique pour résoudre des problèmes complexes d'optimisation combinatoire, appelée recuit quantique, et nous l'utilisons spécifiquement pour résoudre le Problème d'Ordonnancement de Projets avec Contraintes de Ressources (RCPSP). Formulant le RCPSP à la fois comme un problème d'Optimisation Binaire Quadratique non contrainte (QUBO) et un modèle Hamiltonien d'Ising, l'étude emploie l'annealeur quantique D-Wave Advantage 6.3 disponible commercialement, appliqué aux instances RCPSP du générateur aléatoire RANGEN1. Les évaluations comparatives contre les solveurs classiques et les algorithmes métaheuristiques affirment le potentiel du recuit quantique, particulièrement pour les instances RCPSP de taille petite à moyenne. Le paysage diversifié de solutions qu'il offre fait du recuit quantique un candidat convaincant pour des algorithmes d'optimisation hybrides, promettant d'améliorer la qualité des solutions.Cette thèse exhaustive contribue à la compréhension théorique et aux applications pratiques du calcul quantique en Recherche Opérationnelle, démontrant son potentiel à révolutionner les méthodologies de résolution de problèmes.Le chapitre cinq de cette thèse explore une nouvelle bibliothèque open-source Python dédiée à l'ordonnancement de projets appelée cheche-pm, qui incorpore et rend disponibles des méthodes d'ordonnancement issues de la littérature pour résoudre le RCPSP et ses variantes. Cette bibliothèque se concentre sur l'apport d'une collection complète de méthodes d'ordonnancement à la fois aux praticiens et aux chercheurs. L'utilisation de cette bibliothèque a été cruciale pour le développement du quatrième chapitre de cette thèse.Enfin, le chapitre six explore l'utilisation d'une implémentation hybride quantique et classique du recuit quantique pour résoudre un cas spécial du problème semi-affectation quadratique QSAP, dans le contexte

•Apr 16, 2024•0 citations
Solutions améliorées de l'algorithme de Grover pour la détection d'utilisateurs actifs dans les résaux sans fil 5G comprend des fonctionnalités telles que Ultra-fiables à faible latence (URLLC) et Massives entre machines (mMTC) pour minimiser les délais et connecter de nombreux appareils. Cela nécessite un schéma Détection des utilisateurs Actifs (AUD), nécessitant une détection en temps réel par Base Station (BS). Maximum de Vraisemblance (ML) est le plus performant pour AUD mais il est complexe. Pour simplifier, des alternatives comme CCR et ZF ont été introduites mais ne peuvent égaler les performances de ML. Pour y remédier, nous explorons l’algorithme de Grover, connu pour ses capacités de superposition (travail avec 0 et 1), superposition (travailler avec 0 et 1 en même temps). Cependant, l’algorithme de Grover, lorsqu’il est contraint par la fonction f(x) = δ, n’est pas aussi performant que ML ; il est plus proche de CCR et de ZF. Pour atteindre les performances de ML, l’algorithme de Grover doit être modifié pour trouver la distance minimale, comme ML la distance minimale, comme le fait ML. Nous proposons un nouvel algorithme, à savoir Algorithme Amélioré de Recherche de Minimum par Itération (IIMSA), visant à améliorer les algorithmes existants Boyer-Brassard-Høyer-Tapp (BBHT) et Durr-Hoyer Algorithm (DHA), qui sont les méthodes prometteuses pour trouver le minimum à l’aide de l’algorithme de Grover afin de réduire leur complexité tout en maintenant des performances élevées. L’idée est d’utiliser n’importe quel nombre aléatoire de solutions plutôt que d’effectuer L itérations aléatoires comme le suggère DHA. Nous incorporons également des méthodes classiques telles que ZF et CCR pour améliorer leurs performances et réduire la complexité. Nous adaptons également l’algorithme de Grover dans le contexte de AUD dans cette thèse. Nous présentons également un algorithme de Grover amélioré inspiré d’une solution hybride quantique qui exploite à la fois des éléments quantiques et classiques, solution hybride quantique qui exploite à la fois des éléments quantiques et classiques. L’objectif principal est d’augmenter la probabilité de succès Ps et de réduire la complexité de l’algorithme original de Grover de l’algorithme de Grover original. Le concept consiste à utiliser moins d’itérations de Grover que le nombre optimal, dénommé Ps. que le nombre optimal, noté Lopt, et de le combiner avec la probabilité de succès classique. Nous pensons que cette approche a le potentiel de modifier le comportement de la complexité et d’obtenir une probabilité de succès élevé et d’atteindre une probabilité de succès élevée.
Pour prendre en charge les transmissions multiples dans une fibre optique, plusieurs techniques ont été étudiées, comme l’accès multiple par répartition en code (OCDMA). En particulier, les systèmes OCDMA incohérents sont appréciés pour leur simplicité. Cependant, ils souffrent de l’interférence d’accès multiple (MAI), qui dégrade les performances. Afin de faire face à cette MAI, plusieurs détecteurs ont été étudiés. Parmi eux, le Maximum Likelihood (ML) est le meilleur. Mais il est très coûteux, car il nécessite tester toutes les possibilités avant de prendre une décision. Cependant, grâce aux récentes avancées de l’informatique quantique, ce problème de complexité peut être contourné. En effet, les algorithmes quantiques, tels que Grover, exploitent les états de superposition dans le domaine quantique et permettent d’accélérer le calcul. Ainsi, dans cet article, nous proposons d’adapter l’algorithme quantique de Grover dans le contexte de la détection multi-utilisateurs, dans un système OCDMA utilisant des codesnon-orthogonaux. Nous présentons un moyen d’adapter le signal bruité reçu aux contraintes définies par l’algorithme de Grover, et évaluons ensuite la probabilité de succès du récepteur quantique. Nous montrons les avantages de notre proposition par rapport au détecteur classique et au détecteur ML optimal.
-L'un des freins des systèmes NOMA (Non orthogonal Multiple access) est la complexité de détection des utilisateurs actifs (AUD: Active User Detection). Nous proposons dans cet article d'utiliser une version adaptée de l'algorithme quantique de Grover pour la détection des utilisateurs actifs afin de tirer partie de l'accélération apportée par la superposition d'états dans les architectures quantiques, Notre version adaptée de l'algorithme de Grover est comparée aux deux récepteurs classiques de référence : le récepteur optimal du maximum de vraisemblance (ML: Maximum Likelihood) et le récepteur basique d'intercorrelation conventionnel (CCR: Conventional Correlation Receiver). La probabilité de détection des utilisateurs actifs est évaluée en fonction du SNR (Signal to Noise Ratio) du signal reçu, où les résultats obtenus prouvent que notre algorithme de Grover adapté est très prometteur sous un faible niveau de bruit.
Vers des algorithmes quantiques efficaces pour l'optimisation et l'échantillonnage Récemment, avec l'avènement du big data et de l'apprentissage machine à grande échelle, il y a eu une demande croissante pour des algorithmes quantiques qui seraient plus directement applicables à des problèmes pertinents en pratique. Dans cette thèse, nous présentons trois algorithmes qui visent à nous rapprocher de cet objectif. Premièrement, nous développons un algorithme quantique pour l'optimisation cornettique, une classe de problèmes d'optimisation qui se situe entre les programmes linéaires et semi-définis en termes d'expressivité et de facilité de résolution. Ces problèmes sont le plus souvent résolus avec l'aide d'une méthode de point intérieur, dont la complexité est principalement imposée par le coût de la résolution d'une série de systèmes linéaires. Dans notre algorithme, nous résolvons ces systèmes linéaires de manière approximative à l'aide d'un algorithme quantique, et nous prouvons que la méthode des points intérieurs qui en résulte converge vers la solution correcte en un même nombre d'itérations. Nous donnons des preuves numériques que l'algorithme fournit des accélérations de bout en bout dans certaines applications de faible précision telles que les machines à vecteurs de support et l'optimisation de portefeuille financier. L'algorithme des systèmes linéaires quantiques que nous utilisons est le résultat d'une longue ligne de recherche engendrée par l'algorithme de système linéaire quantique de Harrow, Hassidim et Lloyd. Bien qu'il ait été prouvé qu'il est asymptotiquement optimal, le circuit correspondant compliqué et nécessite un prétraitement classique. La deuxième contribution de cette thèse est un algorithme quantique amélioré pour les systèmes linéaires, basé sur la méthode classique optimale de l'itération de Chebyshev. Enfin, nous observons que les algorithmes susmentionnés ont la propriété commune d'approximer l'unique vraie solution du problème donné. En général, la conception de tels algorithmes quantiques est difficile, car souvent la seule façon de récupérer (une approximation de) la vraie solution est d'exécuter l'algorithme plusieurs fois (soit naïvement, soit par amplification d'amplitude) et de calculer certaines statistiques (par exemple la moyenne) des sorties mesurées. Si les ordinateurs quantiques donnent intrinsèquement accès à l'échantillonnage de leurs sorties, pourrions-nous les exploiter pour accélérer les problèmes d'échantillonnage classiques? De manière surprenante, il s'avère que l'échantillonnage gaussien n'est pas un problème complètement résolu, même sur les ordinateurs classiques. Notre troisième contribution est un algorithme de Monte Carlo Hamiltonien classique pour l'échantillonnage gaussien dans le modèle d'interrogation du premier ordre. Nous surmontons et contournons plusieurs limites inférieures en prenant des étapes longues et aléatoires pour intégrer le hamiltonien au cœur de l'algorithme.
Le développement de la Théorie du Calcul Quantique provient de l'idée qu'un ordinateur est avant tout un système physique, de sorte que ce sont les lois de la Nature elles-mêmes qui constituent une limite ultime sur ce qui peut être calculé ou non. L'intérêt pour cette discipline fut stimulé par la découverte par Peter Shor d'un algorithme quantique rapide pour factoriser un nombre, alors qu'actuellement un tel algorithme n'est pas connu en Théorie du Calcul Classique. Un autre résultat important fut la construction par Lov Grover d'un algorithme capable de retrouver un élément dans une base de donnée non-structurée avec un gain de complexité quadratique par rapport à tout algorithme classique. Alors que ces algorithmes quantiques sont exprimés dans le modèle ``standard' du Calcul Quantique, où le registre évolue de manière discrète dans le temps sous l'application successive de portes quantiques, un nouveau type d'algorithme a été récemment introduit, où le registre évolue continûment dans le temps sous l'action d'un Hamiltonien. Ainsi, l'idée à la base du Calcul Quantique Adiabatique, proposée par Edward Farhi et ses collaborateurs, est d'utiliser un outil traditionnel de la Mécanique Quantique, à savoir le Théorème Adiabatique, pour concevoir des algorithmes quantiques où le registre évolue sous l'influence d'un Hamiltonien variant très lentement, assurant une évolution adiabatique du système. Dans cette thèse, nous montrons tout d'abord comment reproduire le gain quadratique de l'algorithme de Grover au moyen d'un algorithme quantique adiabatique. Ensuite, nous montrons qu'il est possible de traduire ce nouvel algorithme adiabatique, ainsi qu'un autre algorithme de recherche à évolution Hamiltonienne, dans le formalisme des circuits quantiques, de sorte que l'on obtient ainsi trois algorithmes quantiques de recherche très proches dans leur principe. Par la suite, nous utilisons ces résultats pour construire un algorithme adiabatique pour résoudre des problèmes avec structure, utilisant une technique, dite de ``nesting', développée auparavant dans le cadre d'algorithmes quantiques de type circuit. Enfin, nous analysons la résistance au bruit de ces algorithmes adiabatiques, en introduisant un modèle de bruit utilisant la théorie des matrices aléatoires et en étudiant son effet par la théorie des perturbations.
Algorithmes quantiques dédiés aux systèmes NOMA Le nombre croissant d'appareils connectés dans les réseaux sans fil de cinquième génération (5G) nécessite le développement de nouveaux protocoles d'accès afin de gérer efficacement les ressources limitées disponibles, notamment grâce à l'utilisation de schémas d'accès multiple non orthogonaux (NOMA). Dans ce contexte, des solutions algorithmiques pour la récupération de données sont essentielles pour répondre aux exigences strictes en matière de latence tout en assurant le déploiement d'un nombre massif d'appareils. Alors que les solutions conventionnelles impliquent souvent un compromis entre performance et complexité computationnelle, l'émergence de nouveaux paradigmes de calcul - tels que l'informatique quantique - offre la possibilité de dépasser ces limitations. Cette thèse explore l'application de l'informatique quantique au problème de la détection d'activité dans les réseaux sans fil. Nous commençons par formuler une représentation quantique fidèle du problème, conforme à la fois aux axiomes de la mécanique quantique et aux contraintes technologiques du matériel quantique actuel. Nous apportons également des éclairages physiques sur les systèmes quantiques distribués et illustrons, à travers des simulations numériques, les défis liés à la mise en œuvre de protocoles d'intrication évolutifs entre qubits spatialement séparés. Ensuite, nous adoptons la perspective des réseaux sans fil afin d'optimiser les algorithmes implémentés pour le problème de détection d'activité. À cette fin, des simulations numériques d'annealing quantique sont réalisées. Nous proposons une stratégie de planification générique pour le processus d'annealing et menons une étude afin d'identifier les paramètres les plus critiques pour la convergence des algorithmes quantiques.
Informatique quantique pour la recherche opérationnelle : une approche spéciale pour ordonnancement de projet Le calcul quantique, avec son potentiel profond, a suscité une attention significative ; cependant, son intégration dans la Recherche Opérationnelle (RO) reste naissante. Cette dissertation tente de combler cette lacune en introduisant des algorithmes innovants ancrés dans les principes du calcul quantique pour s'attaquer aux problèmes d'optimisation discrets. La première partie se concentre sur les fondamentaux du calcul quantique et analyse l'algorithme de Grover. Peut-être l'algorithme quantique le plus important, qui est renommé pour son accélération quadratique dans les recherches non structurées. En tirant parti de l'algorithme de Grover, l'étude présente une procédure qui résout efficacement le problème du sac à dos binaire, surmontant des défis souvent négligés dans la littérature sur le calcul quantique.Dans la seconde partie, la thèse affine la performance des algorithmes développés dans le premier chapitre, introduisant deux procédures novatrices : un algorithme hybride de branchement et de bornage et un algorithme d'ascension aléatoire. Ces procédures se révèlent capables d'égaler la performance des algorithmes classiques leaders sur 66000 instances du problème du sac à dos binaire. Notablement, elles étendent leur applicabilité aux problèmes d'optimisation discrets manquant de structures claires, démontrant le potentiel des approches inspirées par le quantique.Dans la troisième partie, l'exploration s'étend à l'examen des limites des algorithmes quantiques existants dans la résolution des problèmes d'optimisation discrets. L'étude évalue de manière critique les algorithmes de comptage quantique, ainsi que les variantes de l'algorithme de Grover telles que la recherche quantique imbriquée, les marches quantiques, et l'algorithme d'amplification d'amplitude, révélant des instances où les contreparties classiques peuvent dominer.Dans la quatrième partie de cette dissertation, nous explorons une avenue prometteuse du calcul quantique pour résoudre des problèmes complexes d'optimisation combinatoire, appelée recuit quantique, et nous l'utilisons spécifiquement pour résoudre le Problème d'Ordonnancement de Projets avec Contraintes de Ressources (RCPSP). Formulant le RCPSP à la fois comme un problème d'Optimisation Binaire Quadratique non contrainte (QUBO) et un modèle Hamiltonien d'Ising, l'étude emploie l'annealeur quantique D-Wave Advantage 6.3 disponible commercialement, appliqué aux instances RCPSP du générateur aléatoire RANGEN1. Les évaluations comparatives contre les solveurs classiques et les algorithmes métaheuristiques affirment le potentiel du recuit quantique, particulièrement pour les instances RCPSP de taille petite à moyenne. Le paysage diversifié de solutions qu'il offre fait du recuit quantique un candidat convaincant pour des algorithmes d'optimisation hybrides, promettant d'améliorer la qualité des solutions.Cette thèse exhaustive contribue à la compréhension théorique et aux applications pratiques du calcul quantique en Recherche Opérationnelle, démontrant son potentiel à révolutionner les méthodologies de résolution de problèmes.Le chapitre cinq de cette thèse explore une nouvelle bibliothèque open-source Python dédiée à l'ordonnancement de projets appelée cheche-pm, qui incorpore et rend disponibles des méthodes d'ordonnancement issues de la littérature pour résoudre le RCPSP et ses variantes. Cette bibliothèque se concentre sur l'apport d'une collection complète de méthodes d'ordonnancement à la fois aux praticiens et aux chercheurs. L'utilisation de cette bibliothèque a été cruciale pour le développement du quatrième chapitre de cette thèse.Enfin, le chapitre six explore l'utilisation d'une implémentation hybride quantique et classique du recuit quantique pour résoudre un cas spécial du problème semi-affectation quadratique QSAP, dans le contexte