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

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

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

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

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

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

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

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

 ส่วนลดรูปปัญหา 
หาคาบซ้ำ ๆ (r) ที่เกิดจากผลของฟังก์ชัน:
 
นั่นคือ ลำดับ  ของ  ใน  ที่เป็นจำนวนเต็มบวกที่น้อยที่สุดสำหรับ 
ถ้า ar-1 หารด้วย N ลงตัว และ r เป็นเลขคู่ แยกตัวประกอบของ a r-1 ได้เป็น ar/2-1 กับ ar/2+1
หรม. ของ ar/2 ± 1 กับ N คือตัวประกอบที่เราสนใจของ N

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

สร้างหน่วยความจำของควอนตัมคอมพิวเตอร์ขึ้น2ส่วน
ส่วนแรกใช้เก็บจำนวนเต็ม x ที่มีค่าตั้งแต่ 0 ถึง q - 1 โดยที่ q เป็นเลขยกกำลังของ 2 ที่ 
ใช้เก็บผลลัพธ์ฟังก์ชัน  ซึ่งเป็นไปได้ตั้งแต่ 0 ถึง N −1 โดยจำนวนเต็มที่เก็บไว้ในหน่วยความจำแต่ละส่วนจะแทนด้วยฐาน (base) แต่ละตัวของหน่วยความจำ และสถานะของหน่วยความจำจะเป็นผลรวม (superposition) ของฐานต่าง ๆ ซึ่งมีแอมพลิจูด (amplitude) เท่ากันทุกฐาน
เช่น ถ้า N=15 q จะมีค่าเป็น 2^8 ซึ่งมากกว่า 15^2 แต่น้อยกว่า 2*15^2 จะได้ x มีค่าตั้งแต่ 0-255 ซึ่งต้องใช้หน่วยความจำส่วนแรกขนาด 8 คิวบิต เพื่อเก็บตัวเลข 256 ตัว คือ
 ฐาน 00000000 แทนเลข 0
 ฐาน 00000001 แทนเลข 1
 ฐาน 00000010 แทนเลข 2
 ฐาน 00000011 แทนเลข 3
 ฐาน 11111111 แทนเลข 255
และหน่วยความจำส่วนที่สองต้องใช้ 4 คิวบิตเพื่อเก็บเลข 0 ถึง 14
ตอนเริ่มต้นนั้นหน่วยความจำของควอนตัมคอมพิวเตอร์จะอยู่ในสถานะ
 
เมื่อ เป็นฐานที่แทนจำนวนเต็ม x

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

ทำการวัดสถานะของหน่วยความจำส่วนที่สองซึ่งเก็บผลลัพธ์ไว้ การวัดนี้จะทำให้ฟังก์ชันคลื่นของหน่วยความจำเกิดการยุบรวมกัน เหลือเพียงฐานที่ทำให้เกิดผลลัพธ์ที่วัดได้ ถ้าวัดสถานะของผลลัพธ์ได้เป็น k จะเหลือเพียงฐาน
 
เมื่อ:b คือจำนวนเต็มที่น้อยที่สุดที่ 
 r คือคาบของ 
 n คือจำนวนเต็มที่มากที่สุดที่น้อยกว่า (q−b) /r
หลังทำการวัดแล้วจะได้สถานะของหน่วยความจำเป็น
 
เมื่อ A คือเซตของ x ซึ่ง ให้  และ A คือจำนวนสมาชิกของเซตดังกล่าว

แปลงหน่วยความจำส่วนแรกด้วยการแปลงฟูริเยร์ไม่ต่อเนื่อง
 
ซึ่งทำให้แอมพลิจูดของฐานซึ่งแทนจำนวนที่เป็นจำนวนเท่าของ q/r สูงขึ้นเป็นพีค เมื่อทำการวัดสถานะของหน่วยความจำส่วนแรก จึงมีความน่าจะเป็นสูงที่สุดที่จะได้ค่าเป็นจำนวนดังกล่าว จากค่าที่วัดได้ดังกล่าวคำนวณค่า n/r จนได้คาบrตามลำดับ

 ประวัติของขั้นตอนวิธีของชอร์ 
แนวคิดที่จะใช้การคำนวณต่าง ๆ บนอุปกรณ์ที่อยู่ทำงานด้วยพื้นฐานของกลศาสตร์ควอนตัมเริ่มมีการนำเสนอมาตั้งแค่ทศวรรษที่ 1970 จากทั้งนักคอมพิวเตอร์ และนักฟิสิกส์หลายคน โดยแนวคิดนี้เริ่มต้นมาจากการที่พวกเขาทั้งหลายได้เริ่มไตร่ตรองถึงขีดจำกัดในการคำนวณ เนื่องมาจากกฎของมัวร์ (Moore’s law) ซึ่งจะทำให้ขนาดวงจรบนชิพซิลิกอนนั้นมีขนาดเล็กลงไปเรื่อย ๆ จนถึงขนาด 2-3 อะตอม ซึ่งถ้าหากมีขนาดเล็กขนาดนั้นก็จะทำให้อะตอมแสดงคุณสมบัติของควอนตัมออกมาในวงจร จึงเกิดแนวคิดเกี่ยวกับคอมพิวเตอร์ชนิดใหม่ที่จะทำงานบนพื้นฐานของกฎทางกลศาสตร์ควอนตัม

ในปี 1982 เฟย์แมน ได้เสนอว่า มีความเป็นไปได้ที่ควอนตัมคอมพิวเตอร์จะทำงานได้เร็วกว่าคอมพิวเตอร์ดั้งเดิมที่มีประสิทธิภาพเป็นฟังก์ชันเลขชี้กำลัง และเครื่องจักรทัวริง (Turing machine) นั้นไม่สามารถจำลองระบบทางควอนตัมได้ หากไม่ใช้ขั้นตอนเป็นฟังก์ชันเลขชี้กำลังของหน่วยย่อยในระบบ นอกจากนี้ เฟย์แมน ยังได้แนะไว้ว่า หากใช้เครื่องมือที่มีพฤติกรรมแบบควอนตัมในตัวเองแล้ว จะสามารถทำการจำลองระบบทางควอนตัมได้โดยไม่ต้องใช้ขั้นตอนเป็นเอ็กโพเนนเชียล ซึ่งจะทำให้นักวิทยาศาสตร์สามารถทำการทดลองทางกลศาสตร์ควอนตัมบนควอนตัมคอมพิวเตอร์ได้

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

แต่ความพยายามในการหาวิธีประยุกต์ใช้ควอนตัมคอมพิวเตอร์นี้ ยังไม่ประสบผลสำเร็จจนกระทั่ง ปีเตอร์ ชอร์ นักวิจัยของเอทีแอนด์ที (AT&T) ได้เสนอวิธีการแก้ปัญหาการแยกตัวประกอบด้วยควอนตัมคอมพิวเตอร์ในปี 1994 โดย ชอร์ แสดงให้เห็นว่าจะต้องรวมตัวดำเนินการทางคณิตศาสตร์ที่ออกแบบมาเฉพาะกับควอนตัมคอมพิวเตอร์นั้นเข้าด้วยกันอย่างไร จึงจะสามารถทำการแยกตัวประกอบของจำนวนขนาดใหญ่ได้ จากจุดนี้เองทำให้ควอนตัมคอมพิวเตอร์ได้เปลี่ยนจากคำถามในวงการวิชาการ มาเป็นความสนใจของโลกที่จะสร้างควอนตัมคอมพิวเตอร์ขึ้นมาจริง ๆ

จนกระทั่งในปี 2001 ลีเว็น วานเดอร์ไซเพ็น นักวิจัยของไอบีเอ็ม และคณะ ได้ใช้ควอนตัมคอมพิวเตอร์แบบ เอ็นเอ็มอาร์ (NMR) ขนาด 7 คิวบิต แก้ปัญหาการแยกตัวประกอบด้วยขั้นตอนวิธีของชอร์ โดยทำการแยกตัวประกอบของ 15 ได้เป็นผลสำเร็จ

 ลำดับเหตุการณ์ในการคิดค้นขั้นตอนวิธีของชอร์ 
ตั้งแต่อดีตจนถึงปัจจุบัน ขั้นตอนวิธีของชอร์ได้มีการพัฒนาในการคิดค้น การออกแบบวงจร และ
การประยุกต์ใช้จริงตามลำดับ ดังนี้
 ปี 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