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

Algorithmes quantiques, cycles hamiltoniens et la k-coloration des graphes

Mohamed Sghiar

Published Apr 4, 2016• 3 citations
OpenAlex

Abstract

I will prove the existence of the Feynman quantum algorithm, polynomial and of the order $ \mathcal{ O } (n ^ 3 ) $ which inform us about the presence of the Hamiltonian cycles in a graph with cardinality n and in this case allows us to find them completely. And I will also prove the existence of the Pauli quantum algorithm with the order $\mathcal { O } (n ^ 3) $ which enable us to know whether the k-coloring graph is possible and make us this coloration if it is possible.

Related papers

Generalized quantum walks for quantum algorithmics

Olga Lopez Acevedo, François Dunlop, École doctorale Sciences et ingénierie, Cergy-Pontoise, Val d'Oise

Nous avons étudié les algorithmes quantiques dans le but de calculer le permanent d'une matrice avec une machine quantique. Après avoir construit quelques algorithmes, nous nous sommes interessés aux équivalents quantiques des marches aléatoires. Ces marches peuvent être à la base de nouveaux algorithmes quantiques. Nous avons commencé par généraliser le modèle existant et classifier les marches sur des graphes de Cayley de groupes simples. Nous avons étudié des marches sur l'hypercube et le réseau simple à une et deux directions. Pour ces graphes nous avons calculé analytiquement la fonction d'onde et exploré numériquement le temps d'arrivée et la variance. Nous avons de plus élargi deux théorèmes existants concernant l'existence des marches scalaires et la limite faible. Ces résultats nous permettent d'envisager de compléter la classification des marches pour des graphes plus complexes dans le but d'obtenir des informations structurales sur les sous-algorithmes quantiques possibles.

•Jan 1, 2005•0 citations

Distributed randomized and quantum algorithms for cycle detection in networks

Maël Luce

Algorithmes randomisés et quantiques pour la détection de cycle dans les réseaux distribués Détecter la présence de sous-structures spécifiques (e.g. de cycles de longueur donnée) est un problème standard dans les réseaux d'algorithmique distribuée. Cette thèse se concentre sur la détection distribuée de cycles de longueur paire, c'est-à-dire décider si le réseau contient un cycle de longueur 2k comme sous-graphe, pour tout k\geq 2. Cette collection de problèmes (un pour chaque k) est étudiée à la fois en algorithmique distribuée randomisée et quantique, dans les variants correspondant du modèle \CONGEST. Dans le modèle randomisé, la meilleure borne inférieure connue pour décider C_{2k}-freeness dans le modèle \CONGEST est \tilde Omega(\sqrt n) rondes, et, avant notre travail, la meilleure borne supérieure générale pour le problème s'appliquant à tout k\geq 2 était \tilde O(n^{1-\nicefrac{1}{\theta(k^2)}}) rondes [Eden et al., 2022]. Un algorithme plus rapide existait cependant, mais seulement pour les petites valeurs de k, à savoir pour 2\leq k\leq 5, avec une complexité en rondes de O(n^{1-\nicefrac{1}{k}}) [Censor-Hillel et al., 2020]. Ce dernier algorithme se base sur une technique originale que nous appelons la technique \emph{Local Threshold}. Nous démontrons que la technique Local Threshold ne peut être étendue pour détecter efficacement les 2k-cycles pour k\geq 6 dans le modèle \CONGEST randomisé. Néanmoins, nous démontrons qu'elle peut tout de même être utilisée pour décider l'absence de certaines \emph{familles} de cycles de longueur paire. Par exemple, en utilisant cette technique, nous démontrons que \{C_{12},C_{14}\}-freeness peut être décidé en O(n^{1-\nicefrac{1}{7}) rondes. D'une façon similaire, la technique Local Threshold peut aussi décider \{C_{4\ell}\mid 1\leq \ell \leq k\}-freeness (resp. \{C_{4\ell+2} \mid 1\leq \ell \leq k\}-freeness) en O(n^{1-\nicefrac{1}{2k}}) (resp. O(n^{1-\nicefrac{1}{(2k+1)}})) rondes. Une des deux principales contributions de cette thèse est l'élaboration de la technique \emph{Global Threshold}, pour détecter les 2k-cycles en O(n^{1-\nicefrac{1}{k}}) rondes pour tout k\geq 2. Cette technique consiste grossièrement à fusionner toutes les sous-routines de recherche utilisée dans la technique Local Threshold en une seule recherche, pour laquelle un seuil peut être fixé pour chaque valeur de k\geq 2. La seconde contribution technique de cette thèse est la quantization de notre algorithme randomisé pour décider C_{2k}-freeness. Nous démontrons, grâce à une nouvelle technique distribuée d'amplification quantique Monte-Carlo, que pour tout k\geq 2, C_{2k}-freeness peut être décidé en \tilde O(n^{\nicefrac{1}{2}-\nicefrac{1}{2k}}) rondes. Similairement, pour tout k\geq 1, C_{2k+1}-freeness peut être décidé par un algorithme quantique s'exécutant en \tilde O(\sqrt n) rondes dans le modèle \CONGEST, améliorant ainsi quadratiquement la complexité de la détection de cycles de longueur impaire plus strictement plus grande que 3, comparé au cadre randomisé. Nous établissons également des bornes inférieures, à savoir \tilde\Omega(\sqrt{n}) pour détecter les cycles de longueur paire strictement plus grande que 3, s'alignant sur notre borne supérieure, et \tilde\Omega(n^{\nicefrac{1}{4}}) pour la détection de cycle de longueur paire.

•Dec 17, 2024•0 citations

Approximate Quantum 3-Colorings of Graphs and the Quantum Max 3-Cut Problem

Samuel J. Harris

arXiv:2412.19405•Communications in Mathematical Physics•Apr 4, 2026•0 citations

Marches quantiques généralisées pour l'algorithmique quantique

López Acevedo, Olga Lucía

Nous avons etudie les algorithmes quantiques dans le but de calculer le permanent d'une matrice avec une machine quantique. Apres avoir construit quelques algorithmes, nous nous sommes interesses aux equivalents quantiques des marches aleatoires. Ces marches peuvent etre a la base de nouveaux algorithmes quantiques. Nous avons commence par generaliser le modele existant et classifier les marches sur des graphes de Cayley de groupes simples. Nous avons etudie des marches sur l'hypercube et le reseau simple a une et deux directions. Pour ces graphes nous avons calcule analytiquement la fonction d'onde et explore numeriquement le temps d'arrivee et la variance. Nous avons de plus elargi deux theoremes existants concernant l'existence des marches scalaires et la limite faible. Ces resultats nous permettent d'envisager de completer la classification des marches pour des graphes plus complexes dans le but d'obtenir des informations structurales sur les sous-algorithmes quantiques possibles.

•Jan 1, 2005•0 citations

On the Complexity of Finding Cycles in Periodic Functions Using the Quantum Turing Machine

Takashi Mihara

IEICE Transactions on Information and Systems•May 25, 1996•0 citations

Exponential-Time Quantum Algorithms for Graph Coloring Problems

Kazuya Shimizu, Ryuhei Mori

Lecture notes in computer science•Jan 1, 2020•8 citations
I will prove the existence of the Feynman quantum algorithm, polynomial and of the order O(n3)\mathcal{ O } (n ^ 3 )O(n3) which inform us about the presence of the Hamiltonian cycles in a graph with cardinality n and in this case allows us to find them completely. And I will also prove the existence of the Pauli quantum algorithm with the order O(n3)\mathcal { O } (n ^ 3) O(n3) which enable us to know whether the k-coloring graph is possible and make us this coloration if it is possible.
Nous avons étudié les algorithmes quantiques dans le but de calculer le permanent d'une matrice avec une machine quantique. Après avoir construit quelques algorithmes, nous nous sommes interessés aux équivalents quantiques des marches aléatoires. Ces marches peuvent être à la base de nouveaux algorithmes quantiques. Nous avons commencé par généraliser le modèle existant et classifier les marches sur des graphes de Cayley de groupes simples. Nous avons étudié des marches sur l'hypercube et le réseau simple à une et deux directions. Pour ces graphes nous avons calculé analytiquement la fonction d'onde et exploré numériquement le temps d'arrivée et la variance. Nous avons de plus élargi deux théorèmes existants concernant l'existence des marches scalaires et la limite faible. Ces résultats nous permettent d'envisager de compléter la classification des marches pour des graphes plus complexes dans le but d'obtenir des informations structurales sur les sous-algorithmes quantiques possibles.
Algorithmes randomisés et quantiques pour la détection de cycle dans les réseaux distribués Détecter la présence de sous-structures spécifiques (e.g. de cycles de longueur donnée) est un problème standard dans les réseaux d'algorithmique distribuée. Cette thèse se concentre sur la détection distribuée de cycles de longueur paire, c'est-à-dire décider si le réseau contient un cycle de longueur 2k comme sous-graphe, pour tout k\geq 2. Cette collection de problèmes (un pour chaque k) est étudiée à la fois en algorithmique distribuée randomisée et quantique, dans les variants correspondant du modèle \CONGEST. Dans le modèle randomisé, la meilleure borne inférieure connue pour décider C_{2k}-freeness dans le modèle \CONGEST est \tilde Omega(\sqrt n) rondes, et, avant notre travail, la meilleure borne supérieure générale pour le problème s'appliquant à tout k\geq 2 était \tilde O(n^{1-\nicefrac{1}{\theta(k^2)}}) rondes [Eden et al., 2022]. Un algorithme plus rapide existait cependant, mais seulement pour les petites valeurs de k, à savoir pour 2\leq k\leq 5, avec une complexité en rondes de O(n^{1-\nicefrac{1}{k}}) [Censor-Hillel et al., 2020]. Ce dernier algorithme se base sur une technique originale que nous appelons la technique \emph{Local Threshold}. Nous démontrons que la technique Local Threshold ne peut être étendue pour détecter efficacement les 2k-cycles pour k\geq 6 dans le modèle \CONGEST randomisé. Néanmoins, nous démontrons qu'elle peut tout de même être utilisée pour décider l'absence de certaines \emph{familles} de cycles de longueur paire. Par exemple, en utilisant cette technique, nous démontrons que \{C_{12},C_{14}\}-freeness peut être décidé en O(n^{1-\nicefrac{1}{7}) rondes. D'une façon similaire, la technique Local Threshold peut aussi décider \{C_{4\ell}\mid 1\leq \ell \leq k\}-freeness (resp. \{C_{4\ell+2} \mid 1\leq \ell \leq k\}-freeness) en O(n^{1-\nicefrac{1}{2k}}) (resp. O(n^{1-\nicefrac{1}{(2k+1)}})) rondes. Une des deux principales contributions de cette thèse est l'élaboration de la technique \emph{Global Threshold}, pour détecter les 2k-cycles en O(n^{1-\nicefrac{1}{k}}) rondes pour tout k\geq 2. Cette technique consiste grossièrement à fusionner toutes les sous-routines de recherche utilisée dans la technique Local Threshold en une seule recherche, pour laquelle un seuil peut être fixé pour chaque valeur de k\geq 2. La seconde contribution technique de cette thèse est la quantization de notre algorithme randomisé pour décider C_{2k}-freeness. Nous démontrons, grâce à une nouvelle technique distribuée d'amplification quantique Monte-Carlo, que pour tout k\geq 2, C_{2k}-freeness peut être décidé en \tilde O(n^{\nicefrac{1}{2}-\nicefrac{1}{2k}}) rondes. Similairement, pour tout k\geq 1, C_{2k+1}-freeness peut être décidé par un algorithme quantique s'exécutant en \tilde O(\sqrt n) rondes dans le modèle \CONGEST, améliorant ainsi quadratiquement la complexité de la détection de cycles de longueur impaire plus strictement plus grande que 3, comparé au cadre randomisé. Nous établissons également des bornes inférieures, à savoir \tilde\Omega(\sqrt{n}) pour détecter les cycles de longueur paire strictement plus grande que 3, s'alignant sur notre borne supérieure, et \tilde\Omega(n^{\nicefrac{1}{4}}) pour la détection de cycle de longueur paire.
Nous avons etudie les algorithmes quantiques dans le but de calculer le permanent d'une matrice avec une machine quantique. Apres avoir construit quelques algorithmes, nous nous sommes interesses aux equivalents quantiques des marches aleatoires. Ces marches peuvent etre a la base de nouveaux algorithmes quantiques. Nous avons commence par generaliser le modele existant et classifier les marches sur des graphes de Cayley de groupes simples. Nous avons etudie des marches sur l'hypercube et le reseau simple a une et deux directions. Pour ces graphes nous avons calcule analytiquement la fonction d'onde et explore numeriquement le temps d'arrivee et la variance. Nous avons de plus elargi deux theoremes existants concernant l'existence des marches scalaires et la limite faible. Ces resultats nous permettent d'envisager de completer la classification des marches pour des graphes plus complexes dans le but d'obtenir des informations structurales sur les sous-algorithmes quantiques possibles.