Shor algoritması

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 log N içindeki polinomdur, bu girişin büyüklüğüdür).^[2] özel olarak alınan zaman O((log N)³), 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, elek Genel sayı alanı, bu alt-üstel zamaniçinde çalışır — yukarda O(e^{1.9 (log N)1/3 (log log N)2/3}).^[3] Shor'un etkin algoritmasının etkisi kuantum Fourier dönüşümünün ve kareleştirme tarafından modüler üstelidir.

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ığı 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ı.

2001de, Shor'un algoritması IBM'de bir grup tarafından gösterilmişti, 15'in çarpanları içinde 3 × 5,bir kuantum bilgisayar ile 7 kubit bir uygulama 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çbir dolaşı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,15'in çarpanları tekrarlandı.^[8] Ayrıca 2012'de, bir kuantum bilgisayar ile büyük sayı çarpanlı için 21'in çarpanları kaydı elde edildi.^[9] Nisan 2012'de, 143'ün çarpanları elde edildi.

Yöntem

Bizm problemin çözümünü deniyoruz:verilen bir tek bileşik sayı $N$, bir tamsayı ${\displaystyle d}$,buluyoruz kesinlikle ${\displaystyle 1}$ ve $N$ arasındadır, bu $N$'e bölünür. Biz $N$'in tek değerleri ile ilgileniyoruz çünkü $N$'in herhangi çift değeri önemsiz ${\displaystyle 2}$ sayısı olarak bir asal çarpan vardır. Biz emin olmak için asallık testi algoritması kullanabiliriz bu $N$ aslında bileşiktir.

Ayrıca,algoritmanın çalışması için, $N$ bir asalın gücü olmaması gerekir. Bu kare alma ile test edilebilir, kübik, ...,${\displaystyle k\leq \log _{2}(N)}$ için ${\displaystyle k}$-$N$'in kökü , ve hiçbiri kontrol edilmemiş bir tamsayıdır. (aslında bu ${\displaystyle N=M^{k}}$ hariç ${\displaystyle M}$ tamsayısı için ve ${\displaystyle k>1}$.)

Dolayısıyla $N$ bir asalın bir kuvveti değildir, o iki eşasal'ın çarpımı ${\displaystyle 1}$'den büyük sayıdır.Bu bir Çinli kalan teoreminin sonucudur, ${\displaystyle 1}$ sayısının modül $N$'de en az dört ayrı kökü var,ikisi ${\displaystyle 1}$ ve ${\displaystyle -1}$.Algoritmanın amacı birin bir $b$ kare kökünü bulmadır , ${\displaystyle 1}$ sonra diğeri ve ${\displaystyle -1}$; böylece bir $b$ $N$'in çarpanlarına ayırmasına yol açacak,kuadratik elek içinde diğer çarpanlama algoritmaları gibi

sırayla, bir $b$ bulunuyor bir öğeyi bulmak için azaltılmıştır.çift periyodun $a$ ile belirli bir ek özellik(Aşağıda açıklandığı gibi, bu klasik parçanın Aşama 6'daki durum tutmaz olması gereklidir). kuantum algoritma rastgele seçilen elementlerin periyodu için $a$ kullanılır, sıralı-bulgu bir klasik bilgisayarın zor bir problemidir.

Shor'un algoritması iki bölümden oluşur:

1. sıralı bulgunun sorununa çarpım sorununu klasik bir bilgisayarda indirgeme yapılabilir .
2. sıralı bulma sorununu çözmek için bir kuantum algoritma.

Klasik parçası

Şablon:Ordered list

Örneğin: ${\displaystyle N=15,a=2,r=4}$, gcd(4 ± 1, N).

Kaynakça

1. Börteçin Ege, "Kuantum mekaniğinden kuantum bilgisayarlarına"
2. Ayrıca bak yalancı-polinom zaman.
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): 883–887, arXiv:quant-ph/0112176, Bibcode 2001Natur.414..883V, DOI:10.1038/414883a, PMID 11780055, http://cryptome.org/shor-nature.pdf 
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): 1054–1057, arXiv:quant-ph/9811018, 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): 250504, arXiv:0705.1684, Bibcode 2007PhRvL..99y0504L, DOI:10.1103/PhysRevLett.99.250504 
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): 250505, arXiv:0705.1398, Bibcode 2007PhRvL..99y0505L, DOI:10.1103/PhysRevLett.99.250505 
8. http://arxiv.org/pdf/1202.5707v1.pdf - Computing prime factors with a Josephson phase qubit quantum processor
9. Martín-López, Enrique; Enrique Martín-López, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou & Jeremy L. O'Brien (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. http://www.nature.com/nphoton/journal/vaop/ncurrent/full/nphoton.2012.259.html. Erişim tarihi: October 23, 2012.