Séance de cours

Algorithme d'optimisation approximative quantique

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours présente l'Algorithme d'optimisation approximative quantique (QAOA) comme une méthode pour résoudre les problèmes d'optimisation combinatoire à l'aide d'ordinateurs quantiques. L'instructeur explique les principes qui sous-tendent la QAOA et son application aux problèmes de satisfabilité booléenne (SAT). La séance de cours couvre la formulation de problèmes d'optimisation dans un cadre quantique, en mettant l'accent sur le problème Ising Spin-glass et les problèmes K-SAT. Différents exemples et algorithmes sont discutés pour illustrer l'efficacité de la QAOA dans la résolution de problèmes complexes d'optimisation.

Source officielle

Concepts associés (23)

Problème SAT

vignette|Une instance du Sudoku peut être transformée en une formule de logique propositionnelle à satisfaire. Une assignation des variables propositionnelles donne une grille complétée. En informatique théorique, le problème SAT ou problème de satisfaisabilité booléenne est le problème de décision, qui, étant donné une formule de logique propositionnelle, détermine s'il existe une assignation des variables propositionnelles qui rend la formule vraie. Ce problème est important en théorie de la complexité.

Problème 2-SAT

En informatique théorique, le problème 2-SAT est un problème de décision. C'est une restriction du problème SAT qui peut être résolu en temps polynomial, alors que le problème général est NP complet. Le problème 2-SAT consiste à décider si une formule booléenne en forme normale conjonctive, dont toutes les clauses sont de taille 2, est satisfaisable. De telles formules sont appelées 2-CNF ou formules de Krom. On considère des formules en forme normale conjonctive, c'est-à-dire que ce sont des ET de OU de littéraux (un littéral est une variable ou la négation d'une variable).

Informatique quantique

L'informatique quantique est le sous-domaine de l'informatique qui traite des calculateurs quantiques et des associés. La notion s'oppose à celle d'informatique dite « classique » n'utilisant que des phénomènes de physique classique, notamment de l'électricité (exemple du transistor) ou de mécanique classique (exemple historique de la machine analytique). En effet, l'informatique quantique utilise également des phénomènes de la mécanique quantique, à savoir l'intrication quantique et la superposition.

Superconducting quantum computing

Superconducting quantum computing is a branch of solid state quantum computing that implements superconducting electronic circuits using superconducting qubits as artificial atoms, or quantum dots. For superconducting qubits, the two logic states are the ground state and the excited state, denoted respectively. Research in superconducting quantum computing is conducted by companies such as Google, IBM, IMEC, BBN Technologies, Rigetti, and Intel. Many recently developed QPUs (quantum processing units, or quantum chips) utilize superconducting architecture.

Problème P ≟ NP

vignette|400px|Représentation visuelle des deux configurations possibles. Le problème P ≟ NP est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général. L'Institut de mathématiques Clay a inclus ce problème dans sa liste des sept problèmes du prix du millénaire, et offre à ce titre un million de dollars à quiconque sera en mesure de démontrer P = NP ou P ≠ NP ou de démontrer que ce n'est pas démontrable.

Afficher plus

Séances de cours associées (64)

Algorithme d'optimisation approximative quantique

Explore l'Algorithme Quantum Approximate Optimization et son application pour résoudre les problèmes d'optimisation efficacement en utilisant l'évolution quantique adiabatique.

Optimisation quantitative adiabatique : problèmes combinatoires

Explore Quantum Optimisation approximative Algorithme pour résoudre efficacement les problèmes combinatoires.

Algorithmes NISQ et VQE

Explore les algorithmes NISQ, en mettant l'accent sur la méthode VQE et les techniques d'atténuation des erreurs.

Avantage quantique computationnel : Progrès récents et prochaines étapes

Explore les progrès récents dans le calcul quantique de l'avantage et discute des défis dans l'atteinte de la suprématie quantique.

Résoudre les jeux de parité dans la pratique

Explore les aspects pratiques de la résolution des jeux de parité, y compris les stratégies gagnantes, les algorithmes, la complexité, le déterminisme et les approches heuristiques.

Afficher plus

Concepts associés (23)

Problème SAT

Problème 2-SAT

Informatique quantique

Superconducting quantum computing

Problème P ≟ NP

Afficher plus