Algoritma BQP untuk dua masalah pembagian dua grafik dan implikasinya pada NP

Saya membaca koran

• Ahmed Younes, " Algoritma Waktu Polinomial Kuantum-Kesalahan Terbatasi untuk Dua Masalah Dua Grafik ", 2015. doi: 10.1007 / s11128-015-1069-y

yang diterbitkan dalam jurnal Springer's Quantum Information Processing. Makalah ini tampaknya mengklaim bahwa ia menyediakan algoritma BQP untuk masalah NP-keras min-bisection dan max-bisection.

Jika benar, ini harus menyiratkan bahwa , yang akan sangat mengejutkan karena dugaan umum bahwa N P ⊈ B Q P . Bahkan ada hasil yang relatif terhadap oracle acak, N P ⊈ B Q P dengan probabilitas 1.$NP\subseteq BQP$$NP\not\subseteq BQP$$NP\nsubseteq BQP$

• Charles H. Bennett, Ethan Bernstein, Gilles Brassard, dan Umesh Vazirani, " Kekuatan dan Kelemahan Komputasi Quantum ", 1997. doi: 10.1137 / S0097539796300933

Saya bingung karena menurut saya analisis kompleksitas makalah ini menyangkut kompleksitas kueri, bukan kompleksitas waktu. Dengan kata lain, tidak jelas algoritme dalam BQP. Di sisi lain, implikasi dari makalah ini harus jelas bagi setiap pengulas dalam komputasi kuantum jadi saya berharap bahwa pengulas benar-benar memeriksa semua detail makalah untuk mengkonfirmasi hasilnya jika tidak maka tidak akan dipublikasikan.

Apakah algoritma di koran benar-benar dalam BQP? Apakah makalah tersebut benar-benar menyiratkan bahwa NP BQP?$\subseteq$

• Ahmed Younes, Jonathan E. Rowe, " Algoritma Quantum-error Polinomial Terikat-Waktu untuk Kepuasan Boolean ", 2015

Makalah lain dengan ide yang sama oleh Ahmed Younes dan Jonathan E. Rowe, A Polinomial Time Bounded-error Quantum Algorithm untuk Boolean Satisfiability . Algoritma bukan waktu polinomial.