BQP-Algorithmus für zwei Graphhalbierungsprobleme und seine Auswirkungen auf NP

Ich habe die Zeitung gelesen

• Ahmed Younes, " Ein Quantenpolynom- Zeitalgorithmus mit begrenztem Fehler für zwei Graphhalbierungsprobleme ", 2015. doi: 10.1007 / s11128-015-1069-y

welches in Springers Zeitschrift Quantum Information Processing veröffentlicht wird. Das Papier scheint zu behaupten, dass es einen BQP-Algorithmus für die NP-harten Probleme der Min-Halbierung und Max-Halbierung bereitstellt.

Wenn das stimmt, soll dies bedeuten , dass , die sehr überraschend sein würden , weil es , dass gemeinsame Vermutung ist N P ⊈ B Q P . Es gibt sogar ein Ergebnis, das relativ zu einem zufälligen Orakel N P ⊈ B Q P mit der Wahrscheinlichkeit 1 ist.$NP\subseteq BQP$$NP\not\subseteq BQP$$NP\nsubseteq BQP$

• Charles H. Bennett, Ethan Bernstein, Gilles Brassard und Umesh Vazirani, " Stärken und Schwächen des Quantencomputers ", 1997. doi: 10.1137 / S0097539796300933

Ich bin verwirrt, weil es mir so scheint, als ob die Komplexitätsanalyse des Papiers die Komplexität von Abfragen und nicht die Komplexität von Zeit betrifft. Mit anderen Worten, es ist nicht klar, dass sich der Algorithmus in BQP befindet. Auf der anderen Seite sollten die Auswirkungen des Papiers jedem Rezensenten im Bereich Quantencomputer klar sein, daher gehe ich davon aus, dass die Rezensenten wirklich alle Details des Papiers überprüft haben, um das Ergebnis zu bestätigen, da es sonst nicht veröffentlicht würde.

Ist der Algorithmus in der Arbeit wirklich in BQP? Bedeutet das Papier wirklich, dass NP BQP?$\subseteq$

• Ahmed Younes, Jonathan E. Rowe, " A Polynomzeit Bounded-Fehler Quantum - Algorithmus für Boolesche Erfüllbarkeit ", 2015

Ein weiteres Papier mit der gleichen Idee von Ahmed Younes und Jonathan E. Rowe, Ein Polynomial Time Bounded-Error Quantum Algorithm for Boolean Satisfiability . Der Algorithmus ist keine Polynomzeit.