Indice
9 relazioni: Algoritmo di Bernstein-Vazirani, Algoritmo di Deutsch-Jozsa, Algoritmo di fattorizzazione di Shor, BPP (complessità), Classe di complessità, Complessità temporale, Lista delle classi di complessità, Problema di Simon, ZPP (complessità).
Algoritmo di Bernstein-Vazirani
L'algoritmo di Bernstein–Vazirani, che risolve il problema di Bernstein–Vazirani è un algoritmo quantistico inventato da Ethan Bernstein e Umesh Vazirani nel 1992.
Vedere BQP (complessità) e Algoritmo di Bernstein-Vazirani
Algoritmo di Deutsch-Jozsa
L'algoritmo di Deutsch-Jozsa è un algoritmo quantistico deterministico proposto da David Deutsch e Richard Jozsa nel 1992 e successivamente migliorato da Richard Cleve, Artur Ekert, Chiara Macchiavello, e Michele Mosca nel 1998.
Vedere BQP (complessità) e Algoritmo di Deutsch-Jozsa
Algoritmo di fattorizzazione di Shor
L'algoritmo di fattorizzazione di Shor è un algoritmo ideato da Peter Shor nel 1994 per risolvere il problema della fattorizzazione dei numeri interi in numeri primi.
Vedere BQP (complessità) e Algoritmo di fattorizzazione di Shor
BPP (complessità)
Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta.
Vedere BQP (complessità) e BPP (complessità)
Classe di complessità
Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità. Un esempio tipico di definizione di classe di complessità ha la forma: Ad esempio, la classe NP è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, mentre la classe P è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale.
Vedere BQP (complessità) e Classe di complessità
Complessità temporale
In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226.
Vedere BQP (complessità) e Complessità temporale
Lista delle classi di complessità
Questa pagina contiene la lista delle classi di complessità, insiemi concernenti la teoria della complessità computazionale. Nell'articolo computazione compare una mappa delle relazioni di inclusione dimostrabili per le classi di complessità.
Vedere BQP (complessità) e Lista delle classi di complessità
Problema di Simon
Nella teoria della complessità computazionale e nella computazione quantistica, il problema di Simon è un problema computazionale che può essere risolto in maniera esponenzialmente più veloce su un computer quantistico rispetto a un computer classico (o tradizionale).
Vedere BQP (complessità) e Problema di Simon
ZPP (complessità)
Nella teoria della complessità computazionale, ZPP (Zero-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore zero") è la classe di complessità dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà.