înregistrare Logare
Puncte:4
avatar Crypto

Puteți ignora cu adevărat numărul de pași de procesare cuantică necesari pentru algoritmul lui Shor?

drapel gs
Mikko Rantalainen

Răspunsuri la întrebare Lungimea cheii RSA față de algoritmul lui Shor sugerează că de ex. Criptarea RSA pe 2048 de biți ar fi ruptă trivial cu un computer cuantic de 4099 qubiți folosind algoritmul lui Shor (cea mai cunoscută implementare a algoritmului care necesită 2n+3 qubiți).

Este asta cu adevărat adevărat? Dacă am înțeles corect, numărul de porți (operații logic cuantice) necesare ar fi în jur de log(2^2048)^2Ãlog(log(2^2048))Ãlog(log(log(2^2048) )) care este de aproximativ 2,9×10â·. Având în vedere că nici măcar computerele clasice nu pot executa operații cu porți de 2,9×10” folosind o singură bucată de date de intrare, într-adevăr nu are sens să presupunem că un număr atât de mare de porți ar putea fi operate de computerul cuantic în mod non-trivial. timp.

Aș presupune că, pentru ca computerul cuantic să execute un pas, executând algoritmul lui Shor, ar trebui să treacă (logic) o intrare prin toate acele porți care ar fi analoge cu computerul clasic care execută suficient cod de computer pentru a trece o intrare de 2048 de biți prin 2,9×10â. · porţi.Deoarece informația nu poate călători mai repede decât viteza luminii și porțile au dimensiuni diferite de zero, acest lucru nu se poate întâmpla în timp trivial. Și dacă folosiți fotoni pentru qubiți în computerul cuantic, lungimea de undă stabilește probabil dimensiunile minime pentru o poartă, indiferent de abilitățile de fabricație.

Și dacă aveți nevoie de o corecție a erorilor între porți, aceasta va necesita spațiu suplimentar și, prin urmare, va crește și latența.

În plus, dacă am înțeles corect, pentru a factoriza efectiv numere mari cu algoritmul lui Shor, trebuie să utilizați un computer clasic pentru a genera o estimare aleatorie, iar algoritmul lui Shor va folosi apoi acea presupunere pentru a putea emite datele necesare pentru a calcula factorii. De câte presupuneri, în medie, ai avea nevoie de fapt pentru factorizarea numerelor utilizate în RSA pe 2048 de biți?

Au existat cercetări despre potențialul timp de rulare practic al unui mare computer cuantic fizic care încearcă să execute algoritmul lui Shor pentru factorizarea numerelor mari? Susține asta într-adevăr interpretarea că pur și simplu puteți ignora timpul de procesare, indiferent de mărimea numerelor?

78
0 + 0
drapel us
Sam Ginrich
După înțelegerea mea, putem rezolva probleme cu aproximativ 50 de q-biți, nici măcar o chestiune de timp de rulare. Dacă căutați „problema de măsurare” în schimbul de fizică, ați putea concluziona că chiar și definiția problemei este pe pisica lui Schrödinger.
0
Răspunde
drapel jp
user253751
„nici măcar computerele clasice nu pot executa operațiuni cu porți de 2,9×10â· folosind o singură bucată de date de intrare”? Ce? Da, ei pot! În câteva milisecunde!
0
Răspunde
drapel jp
user253751
Poate că primul computer cuantic care va face acest lucru nu va fi foarte rapid, așa că poate că va dura o săptămână sau o lună sau un an în loc de câteva milisecunde. Este încă mult mai rapid decât „pentru totdeauna”
0
Răspunde
drapel gs
Mikko Rantalainen
@user253751 Sunt de acord că computerele moderne pot executa operațiuni care lucrează cu porți de 2,9×10â· într-un timp foarte scurt, executând suficiente instrucțiuni în serie. Acest lucru urmează direct, deoarece procesoarele moderne pot rula până la 5×10â¹ instrucțiuni pe secundă per nucleu. Am vrut să spun că nu există instrucțiuni SIMD care să poată rula cu o poartă atât de mare (tranzistor) ca o singură operație, ceea ce înseamnă că execuția în serie a operațiunilor individuale va fi un factor limitator important.
0
Răspunde
Puncte:3
poncho avatar Crypto
drapel my
poncho

Aș presupune că, pentru ca computerul cuantic să execute un pas, executând algoritmul lui Shor, ar trebui să treacă (logic) o intrare prin toate acele porți

Înțelegi greșit ceea ce se măsoară prin „operațiunile de poartă”. Calculatorul cuantic nu ar fi avut 2,9 $ \ori 10^7 $ porți (și toate datele sunt setate prin acel set de porți în mod repetat).

În schimb, computerul cuantic ar trebui să realizeze un total de 2,9 $ \ori 10^7 $ operațiuni de poartă; evident, nu este nevoie să le executăm pe toate simultan (și de fapt, cu Shor, nu putem, atât din cauza teoremei fără clonare interzice generarea de copii ale Qubits pentru a le trimite către porți independente, cât și din motivul mai pragmatic că intrările unor operaţii de poartă depind de operaţiile anterioare de poartă).

Cât despre cum acestea 2,9 $ \ori 10^7 $ Operațiunile de poartă sunt mapate la porțile hardware, ei bine, este destul de puțin probabil să avem 2,9 $ \ori 10^7 $ porți fizice; este posibil ca unele porți hardware să fie reutilizate de mai multe ori în timpul calculului (la fel ca, atunci când un computer clasic efectuează o operație RSA, aceleași porți sunt reutilizate pentru a implementa diferitele operații de multiplicare modulară).

Și dacă aveți nevoie de o corecție a erorilor între porți, aceasta va necesita spațiu suplimentar și, prin urmare, va crește și latența.

Da stim; cel 2,9 $ \ori 10^7 $ figura de mai sus reflectă qubiții logici; care s-ar traduce într-un număr mai mare de qubiți fizici - mărimea creșterii ar depinde de codul de corectare a erorilor cuantice utilizat (care ar depinde, printre altele, de rata de eroare reală a operațiunilor de qubit fizic).

De câte presupuneri, în medie, ai avea nevoie de fapt pentru factorizarea numerelor utilizate în RSA pe 2048 de biți?

Cu probabilitate extrem de mare, unu. Calculatorul cuantic găsește ordinea $g$ modulo $n$, adică valoarea $x$ Unde $g^x \equiv 1 \bmod n$. Cu excepția cazului în care ordinul de $g$ cu privire la ambele $p$ și $q$ (factorii primi) este anormal de mic (ceea ce poate fi demonstrat că se întâmplă doar cu o probabilitate mică dacă $g$ a fost selectat aleatoriu), acea valoare a $x$ poate fi folosit pentru a factoriza rapid.

0 + 0
drapel gs
Mikko Rantalainen
Informații grozave! Toate acestea ar putea fi rezumate după cum urmează? Având în vedere un computer cuantic cu 4099 qubiți, cheia RSA de 2048 de biți poate fi spartă cu operațiuni de poartă de 2,9 $ \times 10^7 $ și asta stabilește timpul total de calcul necesar. Timpul efectiv de perete necesar este definit de viteza medie efectivă a ceasului de instrucțiuni a acestui computer pentru a executa acele operațiuni.
0
Răspunde
drapel gs
Mikko Rantalainen
Conform https://quantumcomputing.stackexchange.com/a/2404/18991, se pare că computerele cuantice ar putea rula în jur de 5 milioane de operațiuni pe secundă, astfel încât timpul total de calcul necesar ar fi de aproximativ 6 secunde! Deci, dacă numărul de qubiți poate fi de fapt crescut la mii fără a încetini operațiunile individuale, atunci viteza de execuție ar trebui să fie suficient de bună pentru a nu fi factorul limitator în practică.
1
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.