Domanda

Mi chiedevo se esiste una classe di complessità per problemi che possono essere risolti in modo efficiente da un computer quantistico in modo tale da dare sempre la risposta giusta? Ad esempio, l'algoritmo Deutsch-Josza non fallisce mai. Un altro modo di chiedere sarebbe: esiste una classe (chiamalo Q) in modo tale che Q sia a P cosa è BPP?

Immagino che anche la domanda abbia senso anche: esiste una classe per i problemi che possono essere risolti in modo efficiente da un computer con accesso alla casualità e non commettere mai un errore? (Sospetto che questo sia semplicemente uguale a P?)

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top