Žinių pagrindai

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į.

QMA suteikia polinominio laiko kvantiniam tikrintojui liudytoją, sudarytą iš polinominio skaičiaus kubitų: „taip“ atvejais priimamas bent vienas liudytojas, o „ne“ atvejais atmetami visi liudytojai, esant aprėžtam pilnumo ir patikimumo skirtumui.

Bostanci, Huang ir Vaikuntanathan 2026 m. rankraštyje konstruojamas klasikinis orakulas O, kuriam QMA^O nėra QCMA^O poaibis, o BQP^O/qpoly nėra BQP^O/poly poaibis, naudojant kodų sankirtos uždavinį su stipriomis atkūrimo iš sąrašų savybėmis.

Kaip nustatyta per 2026 m. spalio 10 d. peržiūrą, 2026 atskyrimo naudojant klasikinį orakulą rezultatas atskiria kvantinius ir klasikinius liudytojus reliatyvizuotame modelyje, tačiau šis rezultatas neišsprendžia įprastų QMA ir QCMA klasių santykio klausimo.

Diskrečiajame be atminties dviejų siuntėjų MAC kanale su nepriklausomais pranešimais pralaidumo sritis yra spartų, kurias riboja I(X1;Y|X2,Q), I(X2;Y|X1,Q) ir I(X1,X2;Y|Q), uždarinys, imant skirstinius p(q)p(x1|q)p(x2|q)p(y|x1,x2).

Fiziškai degraduotame be atminties transliavimo kanale X→Y1→Y2 nepriklausomų privačių pranešimų spartos pasiekiamos superpoziciniu kodavimu, kai R2≤I(U;Y2) ir R1≤I(X;Y1|U), sujungiant sritis visiems p(u,x) skirstiniams.

Diskrečiajame be atminties kanale su retransliatoriumi, aprašomame skirstiniu p(y2,y3|x1,x2), decode-forward strategija pasiekia didžiausią min{I(X1,X2;Y3),I(X1;Y2|X2)} reikšmę, imant p(x1,x2) skirstinius.

Taikant decode-forward, retransliatorius turi atkurti pranešimą arba jo sluoksnį prieš persiųsdamas bendradarbiavimo kodinius žodžius; silpnas šaltinio ir retransliatoriaus ryšys gali riboti šios strategijos spartą.

Kai poros (X,Y) yra nepriklausomos ir vienodai pasiskirsčiusios (iid), o X ir Y koreliuoti, X stebinčio koduotuvo ir Y stebinčio dekoderio spartos ir iškraipymo funkcija yra min[I(X;U)−I(Y;U)], esant U−X−Y ir atkūrimui x-hat(U,Y), tenkinančiam iškraipymo ribą.

Dviejų naudotojų kanaluose su trukdžiais du pranešimai turi būti dekoduojami atitinkamuose jų imtuvuose pagal jungtinį dėsnį p(y1,y2|x1,x2).

Interaktyvus įrodymas leidžia polinominiu laiku veikiančiam atsitiktinumą naudojančiam tikrintojui keistis pranešimais su skaičiavimo ištekliais neapribotu įrodinėtoju.

Lygybė IP=PSPACE taikoma polinominiu laiku atliekamam atsitiktiniam tikrinimui, kai sąveikų skaičius polinominis, o įrodinėtojas neapribotas.

Nulinis žinojimas reikalauja efektyvaus simuliatoriaus, kuris be liudijimo (witness) atkuria tikrintojui leidžiamą matyti informaciją pagal nurodytą tikslų, statistinį arba skaičiavimu grindžiamą neatskiriamumą.

PCP teorema išreiškia NP=PCP(O(log n),O(1)): polinominiu laiku veikiantis tikrintojas naudoja logaritminį atsitiktinių bitų skaičių ir užklausia pastovų vietų skaičių polinominio ilgio įrodyme; pilnumas lygus vienetui, o klaidingo priėmimo tikimybė apribota, pavyzdžiui, viena antrąja.

Įrodymų asistentas patikrina, ar termas įrodo formalų teiginį pagal nurodytas aksiomas ir branduolio taisykles.

2026 m. rugpjūčio 5 d. atnaujintame ir spalio 10 d. patikrintame NIST projekto puslapyje FIPS 203 ML-KEM, FIPS 204 ML-DSA ir FIPS 205 SLH-DSA nurodyti kaip galutiniai standartai, paskelbti 2024 m. rugpjūčio 13 d.

FIPS 203 ML-KEM naudoja modulių LWE pagrįstą viešojo rakto struktūrą ir rakto inkapsuliavimo transformaciją, kuria siekiama IND-CCA2 saugumo.

FIPS 204 ML-DSA standartizuoja iš Dilithium kilusią modulių gardelėmis pagrįstą parašo konstrukciją; ML-DSA-44/65/87 atitinka saugumo kategorijas 2/3/5.

SLH-DSA yra būsenos nesauganti maiša pagrįsta parašo konstrukcija, o ML-DSA naudoja modulių gardelių struktūrą.

Migracijos inventoriuje reikia nustatyti ilgai konfidencialiais išliekančius duomenis, atskirti raktų sudarymą nuo parašų ir nurodyti protokolų bei sertifikatų formatus ir priklausomybes nuo parametrų bei redakcijų.

Dvejetainiam simetriniam kanalui, kurio simbolio apvertimo tikimybė yra 0<p<1/2, esant fiksuotai tikslinei bloko klaidos tikimybei 0<epsilon<1, geriausia sparta turi normaliąją aproksimaciją C−sqrt(V/n) Q-inverse(epsilon)+O(log(n)/n).

Nepriklausomai kartojant baigtinės abėcėlės jungtinį skirstinį p(x,y), koduotuvas, stebintis X, ir dekoderis, turintis Y, gali atkurti X su į nulį artėjančia bloko klaidos tikimybe, kai sparta viršija H(X|Y); mažesnė sparta neįmanoma.

Nepriklausomam ir vienodai pasiskirsčiusiam šaltiniui, kurio skirstinys yra p(x), ir nurodytam iškraipymui d(x,x-hat), R(D) minimizuoja abipusę informaciją pagal atkūrimo skirstinio pasirinkimą, laikantis iškraipymo matematinio vidurkio ribos D.

Arıkan transformacija rekursyviai paverčia dvejetainės įvesties kanalą be atminties sintetiniais kanalais, kurių patikimumai poliarizuojasi.

Stacionariam baigtinės abėcėlės procesui bloko entropija vienam simboliui artėja prie entropijos spartos; dėl koreliacijų ji gali būti mažesnė už atskiro simbolio entropiją.

Neatskiriamumo eksperimente efektyvus priešininkas pasirenka vienodo ilgio pranešimus ir gauna vieno iš jų šifrą; pranešimą parenka paslėptas atsitiktinis bitas.

Adaptyvus saugumas nuo pasirinkto šifro atakų leidžia iššifravimo užklausas prieš iššūkį ir po jo, tačiau pagal eksperimento taisykles neleidžiama užklausti paties iššūkio šifro.

Egzistencinis nepadirbamumas pasirinkto pranešimo atakos sąlygomis reikalauja, kad efektyvus priešininkas, turintis žymų generavimo orakulą, negalėtų su didesne nei nykstamai maža tikimybe sukurti galiojančios žymos naujam pranešimui.

EUF-CMA parašų saugumo eksperimente priešininkui suteikiamas viešasis tikrinimo raktas ir pasirašymo orakulas, tada tikrinama, ar jis gali sukurti galiojantį anksčiau nepasirašyto pranešimo parašą.

Redukcija paverčia sėkmingą schemos puolėją nurodytos prielaidos puolėju, aiškiai susiedama laiką, užklausų skaičių ir sėkmės tikimybę.