C'è una classe di complessità QPP?

Question

La Classe di complessità PP non è considerata trattabile, poiché la probabilità di successo può essere arbitrariamente vicina al 50% dall'alto in quanto le istanze del problema diventano più grandi, in modo che (ad esempio se questo approccio sia esponenziale) un numero infabile di ripetizioni puòessere richiesto prima di avere un significativo probabilità di input soddisfacenti di soddisfazione con sicurezza da quelli non soddisfacenti.Tuttavia, PP è un'interessante classe di complessità da studiare a sé stante.

Esiste una classe di complessità ben definita simile "QPP" di problemi che un computer quantico ha una probabilità superiore al 50% di risolvere correttamente in tempo polinomiale?Capisco che se è così, questa classe di problemi non sarebbe fattibile su un computer quantico, ma ci sono inclusioni non circiali con le classi di complessità più "tradizionali" comprovata o sospettate?Quanto "Big" pensiamo che la classe QPP sia?

Answer 1

Yamakami ha mostrato nel loro documento Analisi delle funzioni quantiche che l'analogico quantisticodi PP è lo stesso di PP classico.Questo è menzionato nel Articolo di wikipedia su pp.