Séance de cours

Le problème hamiltonien local

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 traite du problème local Hamiltonien, en mettant l'accent sur le concept de problèmes QMA-Complete et la complexité de la vérification des calculs quantiques. Il couvre le circuit de délégation, la localité, 3-SAT, les petites valeurs propres, et le contexte historique du problème datant des années 1970.

Source officielle

Proximité ontologique

Informatique théorique

Theory of computation: Théorie de la complexité (informatique théorique)

Concepts associés (32)

Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Electron acceptor

An electron acceptor is a chemical entity that accepts electrons transferred to it from another compound. It is an oxidizing agent that, by virtue of its accepting electrons, is itself reduced in the process. Electron acceptors are sometimes mistakenly called electron receptors. The electron accepting power of an acceptor molecule is measured by its electron affinity (A) which is the energy released when filling the lowest unoccupied molecular orbital (LUMO).

Qubit

En informatique quantique, un qubit ou qu-bit (quantum + bit ; prononcé ), parfois écrit qbit, est un système quantique à deux niveaux, qui représente la plus petite unité de stockage d'information quantique. Ces deux niveaux, notés et selon le formalisme de Dirac, représentent chacun un état de base du qubit et en font donc l'analogue quantique du bit. Grâce à la propriété de superposition quantique, un qubit stocke une information qualitativement différente de celle d'un bit.

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.

Afficher plus

Séances de cours associées (64)

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.

Circuits quantiques : modèle et calcul

Couvre les circuits quantiques, le modèle de calcul, l'inclusion unitaire, la simulation, la précision, les qubits et les aspects globaux.

Estimation de la phase quantique

Explique l'algorithme de l'estimation de la phase quantique (QPE) et sa complexité à l'aide de deux registres et de portes SWAP.

Informatique quantique distribuée

Explore la complexité de la communication et les modèles de calcul quantique dans Distributed Quantum Computing.

Délégation quantique de calcul

Explore les qubits entièrement classiques, l'informatique quantique aveugle et la vérifiabilité dans les protocoles de délégation quantique.

Afficher plus

Concepts associés (32)

Classe de complexité

Computational complexity

Electron acceptor

Qubit

Théorie de la complexité (informatique théorique)

Afficher plus