Kokie yra atviri klausimai, susiję su BQP ir NP ryšiu, ir ką tai reikštų sudėtingumo teorijai, jei būtų įrodyta, kad BQP yra griežtai didesnis už P?
Ryšys tarp BQP (ribotos klaidos kvantinio polinomo laiko) ir NP (nondeterministinio daugianario laiko) yra sudėtingumo teorijos tema. BQP yra sprendimų problemų klasė, kurią kvantinis kompiuteris gali išspręsti polinominiu laiku su ribojančia paklaidos tikimybe, o NP yra sprendimų problemų klasė, kurią gali patikrinti nedeterministinė Tiuringo mašina polinominiu laiku. Išnagrinėti ryšį tarp šių dviejų klasių ir suprasti, kad BQP yra griežtai didesnis nei P (klasikiniame kompiuteryje daugianario laiku išsprendžiamų problemų klasė), yra svarbūs atviri kvantinio sudėtingumo teorijos klausimai.
Vienas atviras klausimas, susijęs su BQP ir NP ryšiu, yra tai, ar BQP yra NP, ar tai griežtai didesnė klasė. Jei BQP yra NP, tai reikštų, kad problemos, kurias galima efektyviai išspręsti kvantiniame kompiuteryje, taip pat gali būti efektyviai patikrintos klasikiniame kompiuteryje. Kita vertus, jei įrodyta, kad BQP yra griežtai didesnis nei P, tai reikštų, kad yra problemų, kurias galima efektyviai išspręsti kvantiniame kompiuteryje, bet ne klasikiniame kompiuteryje. Tai turėtų reikšmingų pasekmių sudėtingumo teorijai, nes suteiktų įrodymų, kad kvantiniai kompiuteriai tam tikras problemas gali išspręsti efektyviau nei klasikiniai kompiuteriai.
Kitas atviras klausimas – ar egzistuoja BQP pilnos problemos. Sakoma, kad problema yra užbaigta BQP, jei ji tokia pat sunki, kaip ir bet kuri BQP problema. Kitaip tariant, jei yra BQP užbaigta problema, tada kiekviena BQP problema gali būti sumažinta iki jos daugianario laiku. BQP užbaigtų problemų egzistavimas sudarytų pagrindą suprasti kvantinių algoritmų sudėtingumą ir jų ryšį su klasikiniais algoritmais. Tačiau šiuo metu nežinoma, ar yra problemų, susijusių su BQP.
Be to, klausimas, ar BQP yra lygus P ar NP, vis dar neišspręstas. Jei BQP yra lygus P, tai reikštų, kad kvantiniai kompiuteriai nesuteikia jokio skaičiavimo pranašumo, palyginti su klasikiniais kompiuteriais sprendžiant sprendimų problemas. Jei BQP yra lygus NP, tai reikštų, kad kvantiniai kompiuteriai gali efektyviai išspręsti problemas, kurias sunku patikrinti klasikiniame kompiuteryje. Šio klausimo sprendimas turėtų didelių pasekmių mūsų supratimui apie kvantinio skaičiavimo galią ir apribojimus.
Norėdami iliustruoti galimą poveikį, kai įrodoma, kad BQP yra griežtai didesnis už P, panagrinėkime didelių skaičių faktoringo problemą. Šiuo metu geriausiai žinomas klasikinis didelių skaičių faktoringo algoritmas – „General Number Field Sieve“ – turi subeksponentinį veikimo laiką. Priešingai, Šoro algoritmas, kvantinis algoritmas, gali apskaičiuoti didelius skaičius daugianario laiku kvantiniame kompiuteryje. Jei būtų įrodyta, kad BQP yra griežtai didesnis nei P, tai patvirtintų, kad Šoro algoritmas iš tikrųjų yra efektyvesnis už bet kurį klasikinį algoritmą, skirtą didelių skaičių faktoringo skaičiui. Tai turėtų reikšmingų pasekmių kriptografijai, nes daugelis šifravimo schemų priklauso nuo didelių skaičių faktoringo sudėtingumo.
Ryšys tarp BQP ir NP yra aktyvi kvantinio sudėtingumo teorijos tyrimų sritis. Atviri klausimai apima tai, ar BQP yra NP, ar yra BQP užbaigtų problemų ir ar BQP yra lygus P arba NP. Išsprendus šiuos klausimus, mūsų supratimas apie kvantinio skaičiavimo galią ir apribojimus būtų gilesnis ir tai turėtų įtakos įvairioms sritims, įskaitant kriptografiją.
Kiti naujausi klausimai ir atsakymai apie BQP:
- Kokie įrodymai rodo, kad BQP gali būti galingesnis už klasikinį daugianario laiką, ir kokie yra problemų, kurios, kaip manoma, yra BQP, bet ne BPP, pavyzdžiai?
- Kaip galime padidinti tikimybę gauti teisingą atsakymą BQP algoritmuose ir kokią klaidų tikimybę galima pasiekti?
- Kaip apibrėžti, kad kalba L būtų BQP, ir kokie yra reikalavimai kvantinei grandinei, sprendžiančiai BQP problemą?
- Kas yra sudėtingumo klasė BQP ir kaip ji susijusi su klasikinėmis sudėtingumo klasėmis P ir BPP?