¿Hay una clase de complejidad QPP?

Question

La clase de complejidad PP no se considera con sentido intermedio, ya que la probabilidad de éxito puede obtener arbitrariamente cerca del 50% desde arriba a medida que las instancias problemáticas sean más grandes, por lo que (por ejemplo, si este enfoque es exponencialmente rápido) un número involuntario de repeticiones puedeSer requerido antes de que tengamos una probabilidad significativa significativa de distinguir con confianza los insumos satisfactorios de los no satisfactorios.Sin embargo, PP es una clase de complejidad interesante para estudiar por derecho propio.

¿Hay una clase de complejidad bien definida similar "QPP" de los problemas que una computadora cuántica tiene una probabilidad de mayor al 50% de resolver correctamente en el tiempo polinomial?Entiendo que, si es así, esta clase de problemas no sería factible en una computadora cuántica, ¡pero son alguna inclusión no trivial con las clases de complejidad más "tradicionales" probadas o sospechosas?¿Qué tan "grande" creemos que la clase QPP es?

Answer 1

yamakami mostró en su papel Análisis de funciones cuánticas que el análogo cuánticode PP es el mismo que el PP clásico.Esto se menciona en la Artículo de Wikipedia en PP.