คุยกับผู้ใช้:Cheeknaew

อย่าลืมดูหน้า วิกิพีเดีย:ศาลาชุมชน/อภิปราย/บทความวิทยาการคอมพิวเตอร์ ด้วยนะครับ --taweethaも 10:04, 17 กันยายน 2554 (ICT)

ยินดีต้อนรับคุณ Cheeknaew สู่วิกิพีเดียภาษาไทย

เขียนอะไร ?

เขียนได้ทุกอย่างถ้า • มีความสำคัญ • ไม่ละเมิดลิขสิทธิ์ • ไม่โฆษณาหรือมีสิ่งอื่นที่ไม่เหมาะสม • เป็นกลาง • ใช้ภาษาและการจัดรูปแบบเป็นสารานุกรม • ไม่มีอยู่เดิมในวิกิพีเดียหรือช่วยปรับปรุงสิ่งที่มีอยู่ให้ดีขึ้น

เขียนอย่างไร ?

ใช้ภาษามาร์กอัปของวิกิ เป็นภาษาอย่างง่ายที่ช่วยในการจัดรูปแบบเอกสารรวมถึงจัดหมวดหมู่ ท่านสามารถเรียนรู้ได้อย่างรวดเร็ว

ชุมชนวิกิพีเดียคืออะไร ?

• เราคืออาสาสมัครที่ทำงานร่วมกันเพื่อแบ่งปันความรู้สู่สาธารณชน • ชาววิกิพีเดียมักบอกเล่าเรื่องราวของตนเองและพูดคุยกันผ่านหน้าผู้ใช้ • เราร่วมมือกันในโครงการต่างๆ และออกเสียงอย่างเป็นประชาธิปไตยในการตัดสินใจที่สำคัญ เช่น การคัดเลือกบทความคัดสรรและบทความคุณภาพ • เรามีนโยบายและแนวปฏิบัติเป็นกรอบกติกามารยาทในการอยู่ร่วมกัน

เริ่มต้นอย่างรวดเร็ว

• ถ้ายังไม่ทราบว่าจะทำอะไรกรุณาดูหน้านี้ • ถ้ามีเรื่องที่อยากเขียนแล้วโปรดดูบทความที่ใกล้เคียงกัน ทั้งในวิกิพีเดียภาษาไทยและวิกิพีเดียภาษาอังกฤษ ท่านสามารถคัดลอกโค้ดของบทความดังกล่าวมาเป็นโครงบทความที่ท่านต้องการสร้าง เรียนรู้วิธีการตั้งชื่อบทความและการจัดรูปแบบจากบทความต้นแบบ

ข้อควรระวัง

• ทุกหน้าในวิกิพีเดียมีไว้เพื่อการพัฒนาสารานุกรม ห้ามใช้ทำอย่างอื่น • ทุกคนสามารถเข้าถึงประวัติการแก้ไขของทุกหน้าได้ • บทความของท่านอาจถูกติดป้ายมากกว่าหนึ่งป้ายหรือถูกลบข้อมูลออกไม่ว่าบางส่วนหรือทั้งหมด อย่ากลัว แต่ก่อนกดบันทึกทุกครั้งพึงระลึกว่างานจะถูกแก้ไขได้ทันที • โปรดเชื่อว่าผู้อื่นมีเจตนาดีและพูดคุยกันเพื่อยุติความขัดแย้ง • เมื่อพูดคุยในหน้าสำหรับแสดงความคิดเห็น กรุณาลงชื่อด้วยปุ่ม

ซึ่งเมื่อบันทึกแล้ว --~~~~ จะกลายเป็นชื่อผู้ใช้และวันเวลาเอง • อย่าลืมเขียนคำอธิบายอย่างย่อก่อนบันทึกเพื่อให้ให้ง่ายต่อการแก้ไขร่วมกันของชาววิกิพีเดีย

หากท่านมีข้อสงสัยเพิ่มเติม กรุณาดูโรงเรียนเตรียมพร้อมวิกิ ขอขอบพระคุณล่วงหน้าในความร่วมมือของท่านในการพัฒนาวิกิพีเดียอย่างต่อเนื่อง
Hello Pulomlovetan! Welcome to Thai Wikipedia. If you are not a Thai speaker, you can ask a question in our Guestbook. Have a nice day!

--taweethaも 23:31, 17 กันยายน 2554 (ICT)

ขั้นตอนวิธีของชอร์ ตั้งชื่อตามนักคณิตศาสตร์ชื่อปีเตอร์ ชอร์ที่คิดขึ้นในปีค.ศ.1994 โดยขั้นตอนวิธีนี้เป็นขั้นตอนวิธีควอนตัม(ขั้นตอนวิธีที่ทำงานบนควอนตัมคอมพิวเตอร์)ที่ใช้ในการแยกตัวประกอบของจำนวนเต็ม ซึ่งโดยทั่วไปแล้วใช้ในการแก้ปัญหา:ให้จำนวนเต็ม N แล้วให้หาตัวประกอบเฉพาะของ N

ในควอนตัมคอมพิวเตอร์นั้น การแยกตัวประกอบด้วยขั้นตอนวิธีของชอร์จะใช้เวลาในการทำงานไม่เกินฟังก์ชันพหุนาม (Polynomial) ของขนาดข้อมูล โดยจะใช้เวลาเป็น O((log N)3) ซึ่งแสดงให้เห็นว่าเป็นการแก้ปัญหาการแยกตัวประกอบของจำนวนเต็มที่มีประสิทธิภาพในควอนตัมคอมพิวเตอร์ วิธีนี้จัดเป็นวิธีที่เร็วกว่าหลายๆวิธีที่มีประสิทธิภาพที่รู้จักกันทั่วๆไปทีมักจะใช้เวลาเป็นฟังชันเลขชี้กำลัง (Exponential) ขนาดของข้อมูล

ให้ควอนตัมคอมพิวเตอร์มีจำนวนคิวบิตที่เพียงพอ ขั้นตอนวิธีของชอร์จะสามารถถอดรหัสประเภทระบบเข้ารหัสแบบกุญแจอสมมาตรได้ ยกตัวอย่างเช่น รหัสลับRSA โดยRSAนั้นตั้งอยู่บนสมมติฐานที่ว่าการคำนวณหาตัวประกอบของเลขที่มีจำนวนมากๆนั้นเป็นไปไม่ได้ เท่าที่รู้กันสมมติฐานนี้ใช้ได้สำหรับคอมพิวเตอร์ทั่วไป และไม่มีขั้นตอนวิธีใดที่จะทำงานในเวลาไม่เกินฟังก์ชันพหุนาม อย่างไรก็ตามขั้นตอนวิธีของชอร์แสดงให้เห็นถึงวิธีการแยกตัวประกอบที่มีประสิทธิภาพในควอนตัมคอมพิวเตอร์ เพื่อให้ควอนตัมคอมพิวเตอร์มีขนาดที่ใหญ่พอที่จะถอดรหัสRSAได้ จึงสร้างแรงจูงใจอย่างมากในการออกแบบและการสร้างควอนตัมคอมพิวเตอร์ และสำหรับศึกษาแบบวิธีการบนควอนตัมคอมพิวเตอร์ใหม่ๆ ในขณะที่ก็มีการให้การสนับสนุนการวิจัยระบบการเข้ารหัสแบบใหม่เพื่อสร้างความปลอดภัยจากควอนตัมคอมพิวเตอร์ เรียกว่าวิทยาการเข้ารหัสลับหลังควอนตัม(post-quantum cryptography)

กระบวนการของขั้นตอนวิธีของชอร์

ปัญหาที่เราต้องการจะหาคำตอบคือ: ให้ $N$ เป็นจำนวนประกอบที่เป็นเลขคี่ ให้หาจำนวนเต็ม d ที่อยู่ระหว่าง 1และ $N$ และ หาร $N$ ลงตัว เราสนใจ $N$ ที่มีค่าเป็นจำนวนคี่เนื่องจากถ้าเป็นจำนวนคู่จะมี “2” เป็นตัวประกอบเฉพาะอยู่แล้ว โดยเราสามารถใช้การทดสอบจำนวนเฉพาะเพื่อหาว่า $N$ นั้นเป็นจำนวนประกอบหรือไม่

นอกจากนั้นแล้ว เรายังต้องการ $N$ ที่ไม่ใช่เลขยกกำลังของจำนวนเฉพาะ เราสามารถทดสอบโดยใช้รากที่2, รากที่4, ..... ,รากที่ k ของ N โดยที่ $k\leq \log _{2}(N)$ และต้องตรวจสอบว่าไม่มีจำนวนใดในนั้นที่เป็นจำนวนเต็ม

เนื่องจาก $N$ ไม่ใช่เลขยกกำลังของจำนวนเฉพาะ คำตอบต้องเป็นผลลัพธ์ของจำนวนเฉพาะสองตัวที่มีค่ามากกว่า 1 จากทฤษฎีบทเศษเหลือของจีน โดยจุดมุ่งหมายของอัลกอริทึ่มนี้คือการหาตัวประกอบของNที่มีค่าไม่เป็น 1 และ -1

ในการแยกตัวประกอบโดยใช้ขั้นตอนวิธีของชอร์นั้นประกอบด้วย2ส่วนคือ

ส่วนลดรูปปัญหา โดยส่วนนี้จะใช้ลดรูปปัญหาจากปัญหาการแยกตัวประกอบเป็นปัญหาในการหาลำดับ ซึ่งส่วนนี้จะสามารถทำได้ในคอมพิวเตอร์ทั่วไป
ส่วนแบบวิธีการควอนตัมที่ใช้ในการแก้ปัญหาในการหาลำดับ

ส่วนลดรูปปัญหา

หาคาบซ้ำๆ(r)ที่เกิดจากผลของฟังก์ชัน:
$f(x)=a^{x}\ {\mbox{mod}}\ N$
นั่นคือ ลำดับ $r$ ของ $a$ ใน $(\mathbb {Z} _{N})^{\times }$ ที่เป็นจำนวนเต็มบวกที่น้อยที่สุดสำหรับ $f(x+r)=f(x)$
ถ้า a^r-1 หารด้วย N ลงตัว และ r เป็นเลขคู่ แยกตัวประกอบของ a ^r-1 ได้เป็น a^r/2-1 กับ a^r/2+1
หรม.ของa^r/2 ± 1 กับ N คือตัวประกอบที่เราสนใจของN

ส่วนควอนตัม: ใช้หาคาบที่เกิดจากฟังก์ชัน

สร้างหน่วยความจำของควอนตัมคอมพิวเตอร์ขึ้น2ส่วน
1. ส่วนแรกใช้เก็บจำนวนเต็มxที่มีค่าตั้งแต่0ถึงq-1 โดยที่qเป็นเลขยกกำลังของ2 ที่ $N^{2}\leq q<2N^{2}$
2. ใช้เก็บผลลัพธ์ฟังก์ชัน $f(x)=a^{x}\ {\mbox{mod}}\ N$ ซึ่งเป็นไปได้ตั้งแต่ 0 ถึง N −1 โดยจำนวนเต็มที่เก็บไว้ในหน่วยความจำแต่ละส่วนจะแทนด้วยฐาน (base)แต่ละตัวของหน่วยความจำ และสถานะของหน่วยความจำจะเป็นผลรวม(superposition) ของฐานต่างๆซึ่งมีแอมพลิจูด (amplitude) เท่ากันทุกฐาน
เช่น ถ้าN=15 qจะมีค่าเป็น2^8ซึ่งมากกว่า 152 แต่น้อยกว่า 2*152 จะได้ x มีค่าตั้งแต่ 0-255 ซึ่งต้องซึ่งต้องใช้หน่วยความจำส่วนแรกขนาด 8 คิวบิต เพื่อเก็บตัวเลข 256 ตัว คือ
- ฐาน 00000000 แทนเลข 0
- ฐาน 00000001 แทนเลข 1
- ฐาน 00000010 แทนเลข 2
- ฐาน 00000011 แทนเลข 3
- ฐาน 11111111 แทนเลข 255
และหน่วยความจำส่วนที่สองต้องใช้ 4 คิวบิตเพื่อเก็บเลข 0 ถึง 14
ตอนเริ่มต้นนั้นหน่วยความจำของควอนตัมคอมพิวเตอร์จะอยู่ในสถานะ
$q^{-1/2}\sum _{x=0}^{q-1}\left|x\right\rangle \left|0\right\rangle$
เมื่อ $\left|x\right\rangle$ เป็นฐานที่แทนจำนวนเต็ม x
คำนวณค่าของฟังก์ชัน $f(x)=a^{x}\ {\mbox{mod}}\ N$ จากค่า x ในหน่วยความจำส่วนแรกแล้วเก็บผลลัพธ์ไว้ในส่วนที่สอง ซึ่งจะให้สถานะของหน่วยความจำเป็น
$q^{-1/2}\sum _{x=0}^{q-1}\left|x\right\rangle \left|f(x)\right\rangle$
เนื่องจากคุณสมบัติที่ทำงานหลายๆอย่างขนานกันไปได้ของควอนตัมคอมพิวเตอร์ จึงสามารถคำนวณค่า $f(x)=a^{x}\ {\mbox{mod}}\ N$ ของจำนวนx ต่างๆ ได้พร้อมๆกันในคราวเดียว ทำให้สามารถทำงานได้รวดเร็วกว่าคอมพิวเตอร์ปกติซึ่งต้องคำนวณทีละตัว
ทำการวัดสถานะของหน่วยความจำส่วนที่สองซึ่งเก็บผลลัพธ์ไว้ การวัดนี้จะทำให้ฟังก์ชันคลื่นของหน่วยความจำเกิดการยุบรวมกัน เหลือเพียงฐานที่ทำให้เกิดผลลัพธ์ที่วัดได้ ถ้าวัดสถานะของผลลัพธ์ได้เป็น k จะเหลือเพียงฐาน
$x=b,b+r,b+2r,b+3r,...,b+nr$
เมื่อ:b คือจำนวนเต็มที่น้อยที่สุดที่ $f(b)=a^{b}\ {\mbox{mod}}\ N=k$
r คือคาบของ $f(x)$

n คือจำนวนเต็มที่มากที่สุดที่น้อยกว่า (q−b)/r
หลังทำการวัดแล้วจะได้สถานะของหน่วยความจำเป็น
$||A||^{-1/2}\sum _{x'=x'\in A}\left|x',k\right\rangle$
เมื่อ A คือเซตของ x ซึ่ง ให้ $a^{x}\ {\mbox{mod}}\ N=k$ และ A คือจำนวนสมาชิกของเซตดังกล่าว
แปลงหน่วยความจำส่วนแรกด้วยการแปลงฟูริเยร์ไม่ต่อเนื่อง
$\left|x\right\rangle \rightarrow q^{1/2}\sum _{c=0}^{q-1}e^{2\pi ixc/q}\left|c\right\rangle$
ซึ่งทำให้แอมพลิจูดของฐานซึ่งแทนจำนวนที่เป็นจำนวนเท่าของ q/r สูงขึ้นเป็นพีค เมื่อทำการวัดสถานะของหน่วยความจำส่วนแรก จึงมีความน่าจะเป็นสูงที่สุดที่จะได้ค่าเป็นจำนวนดังกล่าว จากค่าที่วัดได้ดังกล่าวคำนวณค่า n/r จนได้คาบrตามลำดับ

ลำดับเหตุการณ์ในการคิดค้นขั้นตอนวิธีของชอร์

ตั้งแต่อดีตจนถึงปัจจุบัน ขั้นตอนวิธีของชอร์ได้มีการพัฒนาในการคิดค้น การออกแบบวงจร และ การประยุกต์ใช้จริงตามลำดับ ดังนี้

ปี 1982 ริชาร์ด เฟย์แมนเสนอว่าควอนตัมคอมพิวเตอร์สามารถจำลองระบบทางควอนตัมได้ด้วยขั้นตอนที่ไม่เป็นฟังก์ชันเลขชี้กำลัง

ปี 1985 เดวิด ดอยซ์เสนอว่าควอนตัมคอมพิวเตอร์สามารถจำลองระบบทางฟิสิกส์ใดๆได้อย่างสมบูรณ์แบบ

ปี 1994 ปีเตอร์ ชอร์เสนอขั้นตอนวิธีสำหรับแยกตัวประกอบด้วยควอนตัมคอมพิวเตอร์

ปี 1996 เวนดรัลและคณะ ออกแบบวงจรควอนตัมอย่างง่ายสำหรับ ขั้นตอนวิธีของชอร์ ใช้หน่วยความจำประมาณ 5L คิวบิต เมื่อ L เป็นขนาดของอินพุต และใช้เวลาไม่เกินL3

ปี 1998 กอสเซ็ตต์ออกแบบวงจรควอนตัมสำหรับ ขั้นตอนวิธีของชอร์ ให้ทำงานได้อย่างรวดเร็วไม่เกิน Llog L และใช้หน่วยความจำไม่เกิน L2 คิวบิต

ปี 1998 ซาลกาออกแบบวงจรควอนตัมสำหรับ ขั้นตอนวิธีของชอร์ ที่ใช้หน่วยความจำ 50Lคิวบิต และใช้เวลาทำงานประมาณ 217 L2

ปี 2001 ลีเว็น วานเดอร์ไซเพ็น นักวิจัยของไอบีเอ็มและคณะ ได้ใช้ควอนตัมคอมพิวเตอร์แบบ NMR ขนาด 7 คิวบิต แยกตัวประกอบของ 15 ด้วย ขั้นตอนวิธีของชอร์

ปี 2003 บิวเรการ์ดออกแบบวงจรควอนตัมสำหรับ ขั้นตอนวิธีของชอร์ ที่ใช้หน่วยความจำน้อยที่สุดเพียง 2L คิวบิต แตใ่ช้เวลาในการทำงานประมาณ 32L3

ปี 2005 จูฮา วาติไอเน็นและคณะใช้โจเซ็ปสันชาร์จคิวบิก(Josephson charge qubit)แยกตัวประกอบของ 21

ปี 2005 ออสติน ฟาวเลอร์ แห่งมหาวิทยาลัยเมลเบิร์น ประเทศออสเตรเลีย และคณะได้ประดิษฐ์วงจรควอนตัมคอมพิวเตอร์เพื่อแยกตัวประกอบด้วยขั้นตอนวิธีของชอร์ ที่ใช้หน่วยความจำ 2L + 4 คิวบิต และใชเ้วลาทำงานเป็น 32L3

อ้างอิง

Ekert, Artur and Jozsa, Richard. 1996. “Quantum Computation and Shor’s Factoring Algorithm.” Review of Modern Physics, Vol. 68, No. 3,July 1996; p.733.
Fowler, Austen et al. 2005. “Implementation of Shor’s Algorithm on a Linear Nearest Neighbour Qubit Array.” quant-ph/0402196
Hayward, Matthew. 2005. “Quantum Computing and Shor’s Algorithm.” [Online] AvailabeURL: http://alumni.imsa.edu/~matth/quant/299/paper/index.html (5 เมษายน 2549)
Singh, Simon. 1999. The Code Book: the Evolution of Secrecy from Mary Queen of Scots to Quantum Cryptography. 1st ed.
Shor, P. W., 1994, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA); p.124.
Vandersypen, Lieven and others. 2001. “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance.” Nature, Vol. 414, December 2001; p.883.
Vartiainen, Juha et al. “Implementing Shor’s algorithm on Josephson Charge Qubits.”. quant-ph/0308171
www.kmitl.ac.th/dslabs/ksripima/readme/49/technical...49/watan.pdf

อ่านเพิ่มเติม

Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge University Press {{citation}}: ไม่รู้จักพารามิเตอร์ |lastauthoramp= ถูกละเว้น แนะนำ (|name-list-style=) (help).
Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 019857049X
"Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). Scott Aaronson suggests the following 12 references as further reading (out of "the 10^{10⁵⁰⁰⁰} quantum algorithm tutorials that are already on the web."):
Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput., 26 (5): 1484–1509, arXiv:quant-ph/9508027v2, Bibcode:1999SIAMR..41..303S, doi:10.1137/S0036144598347011. Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
Quantum Computing and Shor's Algorithm, Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original 2750 line LaTeX document, also available as a 61 page PDF or postscript document.
Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294-2, dated 4 Oct 2004, 7 page postscript document.
Chapter 6 Quantum Computation, 91 page postscript document, Caltech, Preskill, PH229.
Quantum computation: a tutorial by Samuel L. Braunstein.
The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
A now-circular reference via the Wikipedia copy of this article; clearly Aaronson's link originally reached the February 20, 2007 version.
III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm, Lecture notes on Quantum computation, Cornell University, Physics 481-681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
arXiv quant-ph/0303175 Shor's Algorithm for Factoring Large Integers. C. Lavor, L.R.U. Manssur, R. Portugal. Submitted on 29 Mar 2003. This work is a tutorial on Shor's factoring algorithm by means of a worked out example. Some basic concepts of Quantum Mechanics and quantum circuits are reviewed. It is intended for non-specialists which have basic knowledge on undergraduate Linear Algebra. 25 pages, 14 figures, introductory review.
arXiv quant-ph/0010034 Shor's Quantum Factoring Algorithm, Samuel J. Lomonaco, Jr, Submitted October 9, 2000, This paper is a written version of a one hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Comments welcome!, Sanjeev Arora and Boaz Barak, Princeton University.
A Step Toward Quantum Computing: Entangling 10 Billion Particles, from "Discover Magazine", Dated January 19, 2011.