Problema indecidabilaCa o dovadă a faptului că lucrurile funcţionează diferit la scară cuantică faţă de scara clasică, fizicienii au descoperit că o problemă pe care o rezolvi uşor într-un context clasic, nu poate fi rezolvată în mod non-contradictoriu şi complet într-unul cuantic.

 

 

 

Cercetătorii cred că aceeaşi situaţie se aplică şi în cazul mai multor probleme similare care ar putea avea implicaţii în aplicaţiile computerelor cuantice şi a modelelor cuantice de tip “multi-particule”, care descriu sistemele microscopice.

 

De nerezolvat

Într-o problemă de decizie cu trei rezultate posibile, există un port deschis prin care o particulă nu va trece niciodată? Când folosim instrumente de măsură cuantice, rezultatul nu poate fi decis (este indecidabil); nu există nici un algoritm care să producă întotdeauna răspunsul corect.


O problemă de decizie se numeşte indecidabilă dacă nu poate fi construit un algoritm unic care să conducă întotdeauna spre un răspuns corect de tip da sau nu la respectiva problemă (n. tr.).


Fizicienii Jens Eisert şi Christian Gogolin de la Universitatea Free din Berlin, împreună cu  Markus P. Müller de la Institutul Perimeter al Universităţii Waterloo, Canada, au publicat un studiu într-un număr recent din Physical Review Letters. “Vom prezentă o abordare nouă în mecanica cuantică, care nu există în echivalentul ei clasic: Suntem în măsură să demonstrăm că întrebări rezonabile despre măsurătorile cuantice sunt, în mod surprinzător, indecidabile,” afirmă Eisert.

“În acelaşi timp, problema clasică corespunzătoare este decidabilă.” Problema în cazul nostru implică un instrument de măsură care generează orice rezultat, dintr-o multitudine de posibilităţi, în funcţie de rezultatul măsurării. Starea rezultată este apoi reintrodusă în instrumentul de măsură ca stare iniţială, conducând la un nou rezultat şi, tot aşa, procesul se repetă. Întrebarea care se pune este dacă există un număr finit de rezultate ale acestor măsurători care nu vor apărea niciodată. Problema ca atare este simplă - pur şi simplu se întreabă dacă anumite rezultate pot să apară în urma măsurătorilor cuantice,” afirmă Eisert. Atunci când folosim un instrument de măsură clasic, fizicienii au arătat că se poate găsi întotdeauna un algoritm care să răspundă dacă există sau nu un rezultat imposibil (cu probabilitate zero).



În contextul fizicii clasice, această problemă este decidabilă. Totuşi, atunci când facem măsurători în contextul fizicii cuantice, fizicienii au arătat că nu există un algoritm care să furnizeze întotdeauna răspunsul corect şi deci problema este indecidabilă. Oamenii de ştiinţă explică că indecidabilitatea apare datorită fenomenului de interferenţă din instrumentul de măsură, sugerând că, cel puţin în acest scenariu, indecidabilitatea pare să fie o proprietate cuantică autentică.

“Într-un anume sens, se poate spune că este indecidabil dacă anumite procese sunt permise de mecanica cuantică sau nu; o situaţie destul de surprinzătoare”, afirmă Eisert. Pentru a ajunge la această concluzie, fizicienii s-au inspirat dintr-o renumită problemă de decizie numită “problema opririi”, introdusă în 1936 de Alan Turing. Problema este aceea de a determina dacă un program care primeşte un input iniţial va ajunge în cele din urmă la un punct final, de “oprire”, sau dacă programul va continua să ruleze fără oprire. Turing a arătat că nu există un algoritm unic care să rezolve această problemă pentru toate intrările iniţiale posibile, deci problema în sine este indecidabilă. Printre implicaţiile acestei probleme a algoritmului de oprire se numără şi celebra teoremă de incompletitudine din matematică a lui Gödel.

În cadrul acestui studiu fizicienii au arătat că dacă problema măsurătorilor cuantice, care au de-a face cu rezultate imposibile, poate oricând fi rezolvată printr-un algoritm, atunci un algoritm care să rezolve fiecare situaţie posibilă a problemei opririi trebuie să existe, ori acest lucru a fost demonstrat de Turing ca imposibil.

Pe lângă faptul că acest rezultat oferă un exemplu interesant de complexitate din lumea cuantică, el ar putea fi dezvoltat pentru a arăta că probleme din alte domenii sunt de asemenea indecidabile. De exemplu, o descriere matematică similară se aplică firelor cuantice folosite în măsurătorile computerelor cuantice, sugerând că niciun algoritm nu poate identifica un şir de măsurători ale căror rezultate nu vor apărea niciodată. 

Indecidabilitatea poate, de asemenea, să apară în problemele de tip “mai multe corpuri”. În aceste cazuri, faptul că anumite probleme sunt indecidabile ar putea să ofere cercetătorilor o nouă perspectivă asupra lor. “Stabilim o nouă legătură între fizica cuantică şi ştiinţa computerelor: Unele probleme nu sunt numai dificil de decis computaţional (cum ar fi găsirea de stări fundamentale pentru anumite modele cuantice de tip “multi-particule”), dar este absolut imposibil să decidem, în principiu, cu toată puterea de calcul pe care o avem disponibilă azi şi tot timpul de rulare disponibil din lume!”, a afirmat Eisert.

“Un computer care ar încerca acest lucru ar merge pur şi simplu fără oprire. Acest lucru surprinzător dezvăluie o faţetă nouă a mecanicii cuantice, care nu era anterior cunoscută. De asemenea, acest rezultat arată că nu doar probleme academice despre maşinile Turing sunt indecidabile, ci de fapt şi problemele reale, fizice, intuitive, pot avea aceeaşi soartă.

”În viitor, cercetătorii îşi propun să cerceteze posibilitatea de a folosi indecidabilitatea ca pe o metodă de validare a ideilor noi. Acest rezultat ar putea să constituie o nouă metodă de validare foarte eficientă”, spune Eisert.

“Să spunem, dacă cineva ar găsi că este indecidabil dacă o stare este distilabilă sau nu, atunci am rezolvat o problemă celebră de existenţă a marginii corelaţiei cuantice NPT (o problemă care are implicaţii în teoria informaţiei cuantice) de o manieră foarte directă. Trebuie însă să continuăm munca începută, după care vom putea înţelege un pic mai clar ce spune de fapt acest rezultat despre mecanica cuantică ca teorie a fizicii şi ce ne spune despre natură, în sine.”



Traducere de Mihai Panoschi după classical-problem-undecidable-quantum, cu acordul editorului.

Write comments...
symbols left.
You are a guest ( Sign Up ? )
or post as a guest
Loading comment... The comment will be refreshed after 00:00.

Be the first to comment.