Límit de Bremermann

De Viquipèdia
Salta a la navegació Salta a la cerca

El límit de Bremermann és la màxima velocitat de calculabilitat computacional dins un sistema, en l’univers material; deriva de l’equivalència massa-energia d'Einstein i del principi d'incertesa de Heisenberg.[1][2] Aquest valor és important a l’hora de dissenyar algoritmes criptogràfics, ja que es pot utilitzar per determinar la mida mínima de claus de xifrat o valors de hash necessaris per crear un algorisme que mai no es pugui esquerdar per una cerca de força bruta. Fou formulat per primer cop el 1962 pel matemàtic i biofísic germano-estatunidenc Hans Joachim Bremermann, de qui rep el nom.[1][2]

Per exemple, un ordinador amb la massa de tota la Terra que opera al límit de Bremermann podria realitzar aproximadament 1075 càlculs matemàtics per segon. Si se suposa que es pot provar una clau criptogràfica amb una única operació, es podria esquerdar una clau típica de 128 bits en menys de 10 a 36 segons. Tanmateix, una clau de 256 bits (que ja s'està utilitzant en alguns sistemes) trigarà uns dos minuts a esquerdar-se. Utilitzar una clau de 512 bits augmentaria el temps d’esquerdament fins a aproximar-se als 1072 anys, sense augmentar el temps de xifrat en més d’un factor constant (segons els algorismes de xifrat utilitzats).

El límit s'ha analitzat més endavant en la literatura posterior com la taxa màxima a la qual un sistema amb distribució d'energia pot evolucionar cap a un estat ortogonal i, per tant, distingible per un altre, [3][4] En particular, Margolus i Levitin han demostrat que un sistema quàntic amb energia mitjana E triga almenys un temps evolucionar cap a un estat ortogonal.[5] Tanmateix, s’ha demostrat que l’accés a la memòria quàntica permet, en principi, algoritmes computacionals que requereixen una quantitat de energia / temps arbitràriament petita per un pas elemental de càlcul.[6][7]

Vegeu també[modifica]

Referències[modifica]

  1. 1,0 1,1 (anglès) Hans Joachim Bremermann. «Optimization Through Evolution and Recombination» (en anglès). Robert J. Bradbury, 1962. [Consulta: 19 novembre 2012].
  2. 2,0 2,1 Bremermann, H.J. (1965) Quantum noise and information. 5th Berkeley Symposium on Mathematical Statistics and Probability; Univ. of California Press, Berkeley, California.
  3. Aharonov, Y.; Bohm, D. «Time in the Quantum Theory and the Uncertainty Relation for Time and Energy». Physical Review, 122, 5, 1961, pàg. 1649–1658. Bibcode: 1961PhRv..122.1649A. DOI: 10.1103/PhysRev.122.1649.
  4. Lloyd, Seth «Ultimate physical limits to computation». Nature, 406, 6799, 2000, pàg. 1047–1054. arXiv: quant-ph/9908043. Bibcode: 2000Natur.406.1047L. DOI: 10.1038/35023282. PMID: 10984064.
  5. Margolus, N.; Levitin, L. B. «The maximum speed of dynamical evolution». Physica D: Nonlinear Phenomena, 120, 1–2, setembre 1998, pàg. 188–195. arXiv: quant-ph/9710043. Bibcode: 1998PhyD..120..188M. DOI: 10.1016/S0167-2789(98)00054-2.
  6. Jordan, Stephen P. «Fast quantum computation at arbitrarily low energy». Phys. Rev. A, 95, 3, 2017, pàg. 032305. arXiv: 1701.01175. Bibcode: 2017PhRvA..95c2305J. DOI: 10.1103/PhysRevA.95.032305.
  7. Sinitsyn, Nikolai A. «Is there a quantum limit on speed of computation?». Physics Letters A, 382, 7, 2018, pàg. 477–481. arXiv: 1701.05550. Bibcode: 2018PhLA..382..477S. DOI: 10.1016/j.physleta.2017.12.042.


Enllaços externs[modifica]