Algoritmo BQP para dos problemas de bisección de gráficos y sus implicaciones en NP

8

Leo el periodico

que se publica en la revista Springer Quantum Information Processing. El artículo parece afirmar que proporciona un algoritmo BQP para los problemas NP-duros de bisección mínima y bisección máxima.

NPBQPN P B Q PNPBQPNPBQP

Estoy perplejo porque me parece que el análisis de complejidad del artículo se refiere a la complejidad de la consulta, no a la complejidad del tiempo. En otras palabras, no está claro si el algoritmo está en BQP. Por otro lado, las implicaciones del documento deberían haber sido claras para cualquier revisor en computación cuántica, por lo que espero que los revisores realmente verifiquen todos los detalles del documento para confirmar el resultado; de lo contrario, no se publicaría.

¿El algoritmo en el documento está realmente en BQP? ¿El documento realmente implica que NP BQP?

neófito
fuente
2
Afaik, este artículo no es muy conocido en la comunidad de la computación cuántica. Es algo sospechoso que no haya sido incluido en el Zoológico de Algoritmo Cuántico . También estoy bastante confundido al ver el periódico en ese diario.
Juan Bermejo Vega
44
He visto algunas sugerencias de que el algoritmo realiza la selección posterior (y, por lo tanto, no es sorprendente ya que @ScottAaronson mostró PostBQP = PP). Por ejemplo, aquí algorítmicassertions.com / quantum/2015/08/01/ … y aquí scottaaronson.com/blog/?p=2408#comment-743305 .
Sasho Nikolov

Respuestas: