BQP ir išvadų apie sudėtingumo klases ribos
Tyrimų kontekstas
postgraduate concept · established · Patikros data 2026-10-10
BQP sudaro sprendimo uždaviniai, sprendžiami uniformiomis polinominio dydžio kvantinėmis grandinėmis su aprėžta paklaida, naudojant nurodytą baigtinį vartų modelį ir klasikinę įvestį bei išvestį.
Esminės žinios
BQP sudaro sprendimo uždaviniai, sprendžiami uniformiomis polinominio dydžio kvantinėmis grandinėmis su aprėžta paklaida, naudojant nurodytą baigtinį vartų modelį ir klasikinę įvestį bei išvestį. Standartinis patikimumo didinimas keičia pastovią paklaidą be eksponentinių išteklių. BPP yra BQP poaibis, o BQP yra PP, taigi ir PSPACE, poaibis. Šios įtrauktys nereiškia griežto klasių atskyrimo, o atskyrimas užklausų orakulo modelyje neišsprendžia įprasto nereliatyvizuoto klasių santykio klausimo.
Sąlygos ir taikymo ribos
- Uniformumas neleidžia slėpti savavališkų atsakymų neuniformiose grandinėse; tikslumo ir pažado uždavinių konvencijos nurodytos aiškiai.
- Sudėtingumas yra asimptotinis įvesties ilgio atžvilgiu ir skiriasi nuo dabartinės aparatinės įrangos galimybių spręsti vieno konkretaus dydžio uždavinį.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Autorius patikrino šį anglišką teiginį, pateiktą lygtį, jei tokia yra, ir nurodytas hipotezes pagal šias šaltinių vietas: §IV BQP, išteklių ir orakulo modelis, §V QMA pažadai ir 2-lokaliojo hamiltoniano teorema 8; istorinė apžvalga; įvadas, teoremos 1.1–1.2 ir formali orakulo bei sąrašo atkūrimo konstrukcija; nereliatyvizuota riba. Patikra apsiriboja užfiksuotais teiginiais; neteigiama, kad atliktas išsamus įrodymo atkūrimas, programinis įrodymo pakartojimas ar užtikrinta visos literatūros aprėptis.
2026-10-10 · Autoriaus atlikta šaltinio teksto, teiginio, lygties ir taikymo srities patikra; grafo sąsajų aprėptis nustatyta kiekvienai atskirai. Prieš užbaigiant šaką būtina atskira nepriklausoma turinio, šaltinių ir inventoriaus peržiūra.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- research-info-bqp-uniform-circuit-model
- Versija
- research.1
- Struktūruotas žinyno įrašas
- Podiplominis ir tyrimų žinynas