Shor algoritması: Revizyonlar arasındaki fark

Vikipedi, özgür ansiklopedi
Etkileşimli olarak geçmişe göz at
[kontrol edilmiş revizyon][kontrol edilmiş revizyon]
← Önceki sürümle aradaki farkSonraki sürümle aradaki fark →
İçerik silindi İçerik eklendi
GörselVikimetin
k Superyetkin Shor'un algoritması sayfasını Shor algoritması sayfasına taşıdı
Ildeguz (mesaj | katkılar)
Beyaz liste
3.098 değişiklik
Değişiklik özeti yok
1. satır: 1. satır:
{{eksik}}
{{eksik}}
'''Shor algoritması''' 1994'te [[Amerikalı]] [[matematikçi]] [[Peter W. Shor]] tarafından geliştirilmiş bir [[algoritma]]dır. Bu algoritma [[kuantum bilgisayarları]]nda çok büyük sayıları kolaylıkla [[asal çarpan]]larına ayırabilmektedir. Shor algoritması bu özelliğiyle [[kriptoloji]] tarihinin dönüm noktalarından biri olarak kabul edilmektedir.<ref>Börteçin Ege, "Kuantum mekaniğinden kuantum bilgisayarlarına"</ref>
'''Shor algoritması''' 1994'te [[Amerikalı]] [[matematikçi]] [[Peter W. Shor]] tarafından geliştirilmiş bir [[algoritma]]dır. Bu algoritma [[kuantum bilgisayarları]]nda çok büyük sayıları kolaylıkla [[asal çarpan]]larına ayırabilmektedir. Shor algoritması bu özelliğiyle [[kriptoloji]] tarihinin dönüm noktalarından biri olarak kabul edilmektedir.<ref>Börteçin Ege, "Kuantum mekaniğinden kuantum bilgisayarlarına"</ref>
bir kuantum bilgisayarı,''N'' tamsayısını çarpanlara, Shor'un algoritması ile [[polinom zaman]]da ayırır (alınan zaman is polynomial in log ''N'' içindeki polinomdur,bu girişinbüyüklüğüdür).<ref>See also [[Pseudo-polynomial time]].</ref> Specifically it takes time {{math|[[Big O notation|O]]((log ''N'')<sup>3</sup>)}}, bu tamsayıyı çarpanlaştırma problemini göstermenin etkin çözümü bir kuantum bilgisayar olabilir ve böylece [[karmaşıklık sınıfı]] '''[[BQP]]''' içindedir.Bu en etkin bilinen klasik çarpanlama algoritmasından daha hızlıdır, the [[Genel sayı alanı elek]], bu [[alt-üstel zaman]]içinde çalışır — yukarda {{math|O(e<sup>1.9 (log N)<sup>1/3</sup> (log log N)<sup>2/3</sup></sup>)}}.<ref>[http://mathworld.wolfram.com/NumberFieldSieve.html MathWorld: Number Field Sieve]</ref> Shor'un etkin algoritması etkisi [[kuantum Fourier dönüşümü]]nün ve [[exponentiation by squaring|kareleştirme ]] tarafından [[modüler üstel]]dir .

Eğer bir kuantum bilgisayar [[kubit]]lerin bir sayısı yeterli ise [[gürültü]]ye yenik düşmeden işletilebilir ve diğer kuantum girişim fenomeneni, Shor'un algoritması kullanılarak [[açık-anahtarlı şifreleme]] şeması kırılabilir örneğin geniş ölçüde [[RSA (algorithm)|RSA]] şeması kullanıldığu gibi. RSA çok sayıda çarpanlara ayırmanın hesaplama açısından olanaksız olduğu varsayımına dayanmaktadır.Şu ana kadar bilindiği gibi, Bu varsayım klasik (non-kuantum) bilgisayarlar için geçerlidir; hiçbir klasik algoritma polinom zamanda faktör olduğu bilinmektedir. Ancak, Shor'un algoritma büyük bir kuantum bilgisayarı oluşturarak RSA yenmek mümkün olabilir bu yüzden çarpanlama, ideal bir kuantum bilgisayar üzerinde etkili olduğunu göstermektedir.Ayrıca kuantum bilgisayarların tasarımı ve inşası için ve yeni kuantum bilgisayar algoritmaları çalışma için güçlü bir motivasyon oldu.Ayrıca [[post-kuantum kriptografi]] topluca, kuantum bilgisayarların güvenli yeni kriptosistemlerde araştırmayı kolaylaştırdı.

In 2001de, Shor'un algoritma was demonstrated by bir grup at IBM , who factored 15 into 3&nbsp;×&nbsp;5,bir kuantum bilgisayar ile 7 [[kubit]]in bir uygulmasında kullanılır.<ref name="VSBYSC01">{{Citation |last=Vandersypen |first=Lieven M. K. |last2=Steffen |first2=Matthias |last3=Breyta |first3=Gregory |last4=Yannoni |first4=Costantino S. |last5=Sherwood |first5=Mark H. |last6=Chuang |first6=Isaac L. |lastauthoramp=yes |year=2001 |title=Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance |journal=[[Nature (journal)|Nature]] |volume=414 |issue=6866 |pages=883–887 |doi=10.1038/414883a |pmid=11780055 |arxiv = quant-ph/0112176 |bibcode = 2001Natur.414..883V |url=http://cryptome.org/shor-nature.pdf |format=PDF}}</ref>
Ancak, bazı şüpheler IBM'in deneyi kuantum hesaplamanın gerçek bir gösteri olup olmadığı gibi gündeme getirilmesinden beri gözlenen hiçbir[[quantum entanglement|dolaşıklık]] yoktur.<ref name="BCJLPS99">{{Citation |last=Braunstein |first=S. L. |last2=Caves |first2=C. M. |last3=Jozsa |first3=R. |last4=Linden |first4=N. |last5=Popescu |first5=S. |last6=Schack |first6=R. |lastauthoramp= |year=1999 |title=Separability of Very Noisy Mixed States and Implications for NMR Quantum Computing |journal=Phys. Rev. Lett |volume=83 |issue=5 |pages=1054–1057 |doi=10.1103/PhysRevLett.83.1054 |bibcode=1999PhRvL..83.1054B|arxiv = quant-ph/9811018 }}</ref>
IBM'in uygulanmasından bu yana, çeşitli gruplar fotonik qubits kullanarak Shor'un algoritmasını hayata geçirdik, bu dolanma vurgulanması gözlenmiştir.<ref name="LBYP07">{{Citation |last=Lu |first=Chao-Yang |last2=Browne |first2=Daniel E. |last3=Yang |first3=Tao |last4=Pan |lastauthoramp=yes |year=2007 |title=Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits |journal=[[Physical Review Letters]] |volume=99 |issue=25 |page=250504 |doi=10.1103/PhysRevLett.99.250504 |first4=Jian-Wei |bibcode=2007PhRvL..99y0504L|arxiv = 0705.1684 }}</ref><ref name="LWLBJGW07">{{Citation |last=Lanyon |first=B. P. |last2=Weinhold |first2=T. J. |last3=Langford |first3=N. K. |last4=Barbieri |first4=M. |last5=James |first5=D. F. V. |last6=Gilchrist |first6=A. |last7=White |first7=A. G. |lastauthoramp=yes |year=2007 |title=Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement |journal=Physical Review Letters |volume=99 |issue=25 |page=250505 |doi=10.1103/PhysRevLett.99.250505 |bibcode=2007PhRvL..99y0505L|arxiv = 0705.1398 }}</ref> In 2012, the factorization of 15 was repeated.<ref>http://arxiv.org/pdf/1202.5707v1.pdf - Computing prime factors with a Josephson phase qubit quantum processor</ref> Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer.<ref>{{cite journal|last=Martín-López|first=Enrique|coauthors=Enrique Martín-López, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou & Jeremy L. O'Brien|title=Experimental realization of Shor's quantum factoring algorithm using qubit recycling|journal=Nature Photonics|date=12 October 2012|url=http://www.nature.com/nphoton/journal/vaop/ncurrent/full/nphoton.2012.259.html|accessdate=October 23, 2012}}</ref> In April 2012, the factorization of 143 is achieved. [http://phys.org/news/2012-04-largest-factored-quantum-algorithm.html]


== Kaynakça ==
== Kaynakça ==

Sayfanın 17.56, 12 Ocak 2014 tarihindeki hâli

Shor algoritması 1994'te Amerikalı matematikçi Peter W. Shor tarafından geliştirilmiş bir algoritmadır. Bu algoritma kuantum bilgisayarlarında çok büyük sayıları kolaylıkla asal çarpanlarına ayırabilmektedir. Shor algoritması bu özelliğiyle kriptoloji tarihinin dönüm noktalarından biri olarak kabul edilmektedir.[1] bir kuantum bilgisayarı,N tamsayısını çarpanlara, Shor'un algoritması ile polinom zamanda ayırır (alınan zaman is polynomial in log N içindeki polinomdur,bu girişinbüyüklüğüdür).[2] Specifically it takes time O((log N)3), bu tamsayıyı çarpanlaştırma problemini göstermenin etkin çözümü bir kuantum bilgisayar olabilir ve böylece karmaşıklık sınıfı BQP içindedir.Bu en etkin bilinen klasik çarpanlama algoritmasından daha hızlıdır, the Genel sayı alanı elek, bu alt-üstel zamaniçinde çalışır — yukarda O(e1.9 (log N)1/3 (log log N)2/3).[3] Shor'un etkin algoritması etkisi kuantum Fourier dönüşümünün ve kareleştirme tarafından modüler üsteldir .

Eğer bir kuantum bilgisayar kubitlerin bir sayısı yeterli ise gürültüye yenik düşmeden işletilebilir ve diğer kuantum girişim fenomeneni, Shor'un algoritması kullanılarak açık-anahtarlı şifreleme şeması kırılabilir örneğin geniş ölçüde RSA şeması kullanıldığu gibi. RSA çok sayıda çarpanlara ayırmanın hesaplama açısından olanaksız olduğu varsayımına dayanmaktadır.Şu ana kadar bilindiği gibi, Bu varsayım klasik (non-kuantum) bilgisayarlar için geçerlidir; hiçbir klasik algoritma polinom zamanda faktör olduğu bilinmektedir. Ancak, Shor'un algoritma büyük bir kuantum bilgisayarı oluşturarak RSA yenmek mümkün olabilir bu yüzden çarpanlama, ideal bir kuantum bilgisayar üzerinde etkili olduğunu göstermektedir.Ayrıca kuantum bilgisayarların tasarımı ve inşası için ve yeni kuantum bilgisayar algoritmaları çalışma için güçlü bir motivasyon oldu.Ayrıca post-kuantum kriptografi topluca, kuantum bilgisayarların güvenli yeni kriptosistemlerde araştırmayı kolaylaştırdı.

In 2001de, Shor'un algoritma was demonstrated by bir grup at IBM , who factored 15 into 3 × 5,bir kuantum bilgisayar ile 7 kubitin bir uygulmasında kullanılır.[4] Ancak, bazı şüpheler IBM'in deneyi kuantum hesaplamanın gerçek bir gösteri olup olmadığı gibi gündeme getirilmesinden beri gözlenen hiçbirdolaşıklık yoktur.[5] IBM'in uygulanmasından bu yana, çeşitli gruplar fotonik qubits kullanarak Shor'un algoritmasını hayata geçirdik, bu dolanma vurgulanması gözlenmiştir.[6][7] In 2012, the factorization of 15 was repeated.[8] Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer.[9] In April 2012, the factorization of 143 is achieved. [1]

Kaynakça

  1. ^ Börteçin Ege, "Kuantum mekaniğinden kuantum bilgisayarlarına"
  2. ^ See also Pseudo-polynomial time.
  3. ^ MathWorld: Number Field Sieve
  4. ^ Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H.; Chuang, Isaac L. (2001), "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance" (PDF), Nature, 414 (6866), ss. 883–887, arXiv:quant-ph/0112176 $2, Bibcode:2001Natur.414..883V, doi:10.1038/414883a, PMID 11780055  Kaynak kaldırılmış |lastauthoramp= parametresini kullanıyor (yardım)
  5. ^ Braunstein, S. L.; Caves, C. M.; Jozsa, R.; Linden, N.; Popescu, S.; Schack, R. (1999), "Separability of Very Noisy Mixed States and Implications for NMR Quantum Computing", Phys. Rev. Lett, 83 (5), ss. 1054–1057, arXiv:quant-ph/9811018 $2, Bibcode:1999PhRvL..83.1054B, doi:10.1103/PhysRevLett.83.1054 
  6. ^ Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao; Pan, Jian-Wei (2007), "Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits", Physical Review Letters, 99 (25), s. 250504, arXiv:0705.1684 $2, Bibcode:2007PhRvL..99y0504L, doi:10.1103/PhysRevLett.99.250504  Kaynak kaldırılmış |lastauthoramp= parametresini kullanıyor (yardım)
  7. ^ Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A.; White, A. G. (2007), "Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement", Physical Review Letters, 99 (25), s. 250505, arXiv:0705.1398 $2, Bibcode:2007PhRvL..99y0505L, doi:10.1103/PhysRevLett.99.250505  Kaynak kaldırılmış |lastauthoramp= parametresini kullanıyor (yardım)
  8. ^ http://arxiv.org/pdf/1202.5707v1.pdf - Computing prime factors with a Josephson phase qubit quantum processor
  9. ^ Martín-López, Enrique (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. Erişim tarihi: October 23, 2012.  Bilinmeyen parametre |coauthors= görmezden gelindi (yardım)
"https://tr.wikipedia.org/w/index.php?title=Shor_algoritması&oldid=14075355" sayfasından alınmıştır