อัลกอริทึมของชอร์เป็นอัลกอริทึมควอนตัมสำหรับการค้นหาตัวประกอบเฉพาะของจำนวนเต็ม พัฒนาขึ้นในปี 1994 โดยปีเตอร์ ชอร์นัก คณิตศาสตร์ชาวอเมริกัน ^{[ 1 ] [ 2 ]}เป็นหนึ่งในอัลกอริทึมควอนตัมไม่กี่ตัวที่เป็นที่รู้จักซึ่งมีศักยภาพในการใช้งานที่น่าสนใจและมีหลักฐานที่ชัดเจนถึงความเร็วที่เพิ่มขึ้นแบบซูเปอร์พหุนามเมื่อเทียบกับอัลกอริทึมแบบคลาสสิก (ไม่ใช่ควอนตัม) ที่เป็นที่รู้จักดีที่สุด^{[ 3 ]}อย่างไรก็ตาม การเอาชนะคอมพิวเตอร์แบบคลาสสิกอาจต้องใช้คอมพิวเตอร์ควอนตัมที่มีคิวบิตหลายล้านตัวเนื่องจากค่าใช้จ่ายเพิ่มเติมที่เกิดจากการแก้ไขข้อผิดพลาดควอนตัม^{[ 4 ]}

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

บนคอมพิวเตอร์ควอนตัม การแยกตัวประกอบจำนวนเต็มอัลกอริทึมของ Shor ทำงานในเวลาพหุนามซึ่งหมายความว่าเวลาที่ใช้คือพหุนามใน[ ^{5 ] ต้อง}ใช้เกตควอนตัม^{ลำดับโดยใช้การคูณเร็ว [ 6 ] หรือแม้กระทั่งใช้อัลกอริทึมการคูณที่เร็วที่สุดในเชิงอะซิมโทติกที่รู้จักในปัจจุบันโดย Harvey และ van der Hoeven [} 7 ] ^{ซึ่งแสดงให้}เห็นว่าปัญหาการ^{แยกตัวประกอบ}จำนวนเต็มอยู่ในระดับความซับซ้อนBQPอัลกอริทึมของ Shor เร็วกว่าอัลกอริทึมการแยกตัวประกอบแบบคลาสสิกที่ปรับขนาดได้มากที่สุด ซึ่งก็คือ^{ตะแกรง}ฟิลด์จำนวนทั่วไปซึ่งทำงานในเวลาต่ำกว่าเลขชี้กำลัง : [ ^{8 ]}${\displaystyle N}$${\displaystyle \log N}$${\displaystyle O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)}$${\displaystyle O\!\left((\log N)^{2}(\log \log N)\right)}$${\displaystyle O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)}$

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

• โครงการRSA​
• การแลกเปลี่ยนกุญแจDiffie–Hellmanในฟิลด์จำกัด
• การแลกเปลี่ยนคีย์Diffie–Hellman เส้นโค้งวงรี^{[ 9 ]}

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

ณ ปี 2026 อัตราความผิดพลาดที่สูงของคอมพิวเตอร์ควอนตัมและจำนวนคิวบิตทางกายภาพที่มีจำกัดสำหรับการแก้ไขข้อผิดพลาดควอนตัมทำให้การสาธิตในห้องปฏิบัติการของอัลกอริทึมของชอร์ได้ผลลัพธ์ที่ถูกต้องเพียงเศษเสี้ยวของความพยายาม และประสบความสำเร็จเฉพาะกับเซมิไพรม์ ขนาดเล็ก เท่านั้น

ในปี 2001 กลุ่มวิจัยที่IBM ได้สาธิตอัลกอริทึมของ Shor โดยแยกตัวประกอบเป็นโดยใช้การใช้งาน NMRของคอมพิวเตอร์ควอนตัมที่มีคิวบิตเจ็ดตัว^{[ 10 ]}หลังจากการใช้งานของ IBM กลุ่มวิจัยอิสระสองกลุ่มได้นำอัลกอริทึมของ Shor มาใช้โดยใช้ คิวบิต แบบโฟตอนิกโดยเน้นว่า มีการสังเกต การพัวพัน ของคิวบิตหลายตัว เมื่อรันวงจรอัลกอริทึมของ Shor ^{[ 11 ] [ 12 ]}ในปี 2012 การแยกตัวประกอบของได้ถูกดำเนินการโดยใช้คิวบิตแบบโซลิดสเตต^{[ 13 ]}ต่อมาในปี 2012 การแยกตัวประกอบของก็ประสบความสำเร็จ^{[ 14 ]}ในปี 2016 การแยกตัวประกอบของได้ถูกดำเนินการอีกครั้งโดยใช้คิวบิตแบบไอออนดักจับ^{[ 15 ]}อย่างไรก็ตาม การสาธิตเหล่านี้ไม่มีอันใดที่ตรงตามข้อกำหนดของอัลกอริทึมของ Shor: พวกเขาสร้างวงจรโดยใช้ความรู้ก่อนหน้าเกี่ยวกับวิธีแก้ปัญหา และบางส่วนยังทำให้ขั้นตอนวิธีง่ายเกินไปจนเทียบเท่ากับการโยนเหรียญ^{[ 16 ]}${\displaystyle 15}$${\displaystyle 3\times 5}$${\displaystyle 15}$${\displaystyle 21}$${\displaystyle 15}$

ปัญหาที่เราพยายามแก้ไขคือ: เมื่อกำหนด จำนวนประกอบคี่มาให้จงหาตัวประกอบจำนวนเต็ม${\displaystyle N}$ ของ จำนวน นั้น

เพื่อให้บรรลุเป้าหมายนี้ อัลกอริทึมของชอร์ประกอบด้วยสองส่วน:

1. เป็นการลดรูปปัญหาการแยกตัวประกอบแบบคลาสสิกไปสู่ปัญหา การหา ลำดับการลดรูปนี้คล้ายกับการลดรูปที่ใช้สำหรับอัลกอริทึมการแยกตัวประกอบ อื่นๆ เช่นตะแกรงกำลังสอง
2. อัลกอริทึมควอนตัมสำหรับแก้ปัญหาการค้นหาลำดับ

อัลกอริทึมการแยกตัวประกอบที่สมบูรณ์นั้นเป็นไปได้ก็ต่อเมื่อเราสามารถแยกตัวประกอบจำนวนใดๆ ได้อย่างมีประสิทธิภาพให้เหลือเพียงจำนวนเต็มสองจำนวนที่มากกว่า 1 เท่านั้น เนื่องจากหากจำนวนใดจำนวนหนึ่งหรือทั้งสองจำนวนไม่ใช่จำนวนเฉพาะ อัลกอริทึมการแยกตัวประกอบก็สามารถนำไปใช้กับจำนวนเฉพาะเหล่านั้นได้เรื่อยๆ จนกว่าจะเหลือแต่จำนวนเฉพาะเท่านั้น ${\displaystyle N}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p}$${\displaystyle q}$

ข้อสังเกตพื้นฐานคือ การใช้อัลกอริทึมของยูคลิดเราสามารถคำนวณGCDระหว่างจำนวนเต็มสองจำนวนได้อย่างมีประสิทธิภาพเสมอ โดยเฉพาะอย่างยิ่ง หมายความว่าเราสามารถตรวจสอบได้อย่างมีประสิทธิภาพว่าเป็นจำนวนคู่หรือไม่ ซึ่งในกรณีนี้ 2 เป็นตัวประกอบอย่างง่ายดาย ดังนั้น เราจึงสมมติว่าเป็นจำนวนคี่สำหรับส่วนที่เหลือของการอภิปรายนี้ หลังจากนั้น เราสามารถใช้อัลกอริทึมแบบคลาสสิกที่มีประสิทธิภาพเพื่อตรวจสอบว่าเป็นกำลังของจำนวนเฉพาะ หรือ ไม่^{[ 17 ]}สำหรับกำลังของจำนวนเฉพาะ มีอัลกอริทึมการแยกตัวประกอบแบบคลาสสิกที่มีประสิทธิภาพ^{[ 18 ]}ดังนั้นส่วนที่เหลือของอัลกอริทึมควอนตัมอาจสมมติว่าไม่ใช่กำลังของจำนวนเฉพาะ ${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$

ถ้ากรณีง่ายๆ เหล่านั้นไม่ก่อให้เกิดตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์ของอัลกอริทึมจะดำเนินการจัดการกับกรณีที่เหลือ เราเลือกจำนวนเต็มแบบสุ่ม ตัวหารที่ไม่ใช่ตัวประกอบศูนย์ที่เป็นไปได้ของสามารถหาได้โดยการคำนวณซึ่งสามารถทำได้แบบคลาสสิกและมีประสิทธิภาพโดยใช้อัลกอริทึมยุคลิดถ้าการคำนวณนี้ก่อให้เกิดตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์ (หมายความว่า) อัลกอริทึมจะเสร็จสิ้น และตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์อีกตัวคือ ถ้าไม่พบตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์ แสดงว่าและตัวเลือกของเป็น จำนวนเฉพาะ สัมพัทธ์ดังนั้น จึงอยู่ในกลุ่มการคูณของจำนวนเต็มมอดูลโดยมีตัวผกผันการคูณ มอดูล ดังนั้น จึงมีลำดับการคูณมอดู ล หมายความว่า ${\displaystyle N}$${\displaystyle 2\leq a<N{.}}$${\displaystyle N}$${\displaystyle \gcd(a,N)}$${\displaystyle \gcd(a,N)\neq 1}$${\displaystyle N/\gcd(a,N)}$${\displaystyle N}$${\displaystyle a}$${\displaystyle a}$${\displaystyle N}$${\displaystyle N}$${\displaystyle a}$${\displaystyle r}$${\displaystyle N}$

${\displaystyle a^{r}\equiv 1{\bmod {N}},}$

และเป็นจำนวนเต็มบวกที่เล็กที่สุดที่สอดคล้องกับสมการนี้ ${\displaystyle r}$

ซับรูทีนควอนตัมพบ. จะเห็นได้จากความสอดคล้องที่หาร ซึ่งเขียนว่า. สามารถแยกตัวประกอบได้โดยใช้ผลต่างกำลังสอง : เนื่องจากเราได้แยกตัวประกอบนิพจน์ในลักษณะนี้แล้ว อัลกอริทึมจึงไม่ทำงานสำหรับจำนวนคี่(เพราะต้องเป็นจำนวนเต็ม) ซึ่งหมายความว่าอัลกอริทึมจะต้องเริ่มต้นใหม่ด้วยค่า ใหม่. ต่อจากนี้ไปเราจึงสามารถสมมติได้ว่าเป็นจำนวนคู่ เป็นไปไม่ได้ที่เนื่องจากจะหมายความว่า ซึ่งจะขัดแย้งกับความหมายของซึ่งก็คือ อยู่แล้วณ จุดนี้ อาจเป็นหรือไม่เป็นกรณีที่. ถ้าไม่หารแสดงว่าเราสามารถหาตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์ของ ได้เราคำนวณถ้าแสดงว่าเป็นจริง และไม่สามารถหาตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์ของ ได้จากและอัลกอริทึมต้องเริ่มต้นใหม่ด้วยค่า ใหม่มิฉะนั้น เราจะพบตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์ของโดยอีกตัวหนึ่งคือ และอัลกอริทึมก็เสร็จสิ้น สำหรับขั้นตอนนี้ การคำนวณ ก็เทียบเท่ากับการคำนวณ เช่นกันมันจะสร้างปัจจัยที่ไม่ใช่ปัจจัยธรรมดาหากปัจจัยนั้นไม่ใช่ปัจจัยธรรมดา และจะไม่สร้างปัจจัยหากปัจจัยนั้นเป็นปัจจัยธรรมดา (โดยที่) ${\displaystyle r}$${\displaystyle N}$${\displaystyle a^{r}-1}$${\displaystyle N\mid a^{r}-1}$$${\displaystyle N\mid (a^{r/2}-1)(a^{r/2}+1).}$$${\displaystyle r}$${\displaystyle a^{r/2}}$${\displaystyle a}$${\displaystyle r}$${\displaystyle N\mid a^{r/2}-1}$${\displaystyle a^{r/2}\equiv 1{\bmod {N}}}$${\displaystyle r/2}$${\displaystyle a}$${\displaystyle r}$${\displaystyle N\mid a^{r/2}+1}$${\displaystyle N}$${\displaystyle a^{r/2}+1}$${\displaystyle N}$$${\displaystyle d=\gcd(N,a^{r/2}-1).}$$${\displaystyle d=1}$${\displaystyle N\mid a^{r/2}+1}$${\displaystyle N}$${\displaystyle a}$${\displaystyle a}$${\displaystyle N}$${\displaystyle N/d}$${\displaystyle \gcd(N,a^{r/2}+1)}$${\displaystyle \gcd(N,a^{r/2}-1)}$${\displaystyle N\mid a^{r/2}+1}$

กล่าวโดยสรุป อัลกอริทึมมีดังนี้: ให้เป็นจำนวนคี่ และไม่ใช่กำลังของจำนวนเฉพาะ เราต้องการหาตัวประกอบที่ไม่ใช่จำนวนเฉพาะสองตัวของ ${\displaystyle N}$${\displaystyle N}$

1. เลือกหมายเลขสุ่ม${\displaystyle 1<a<N}$
2. คำนวณหาตัวหารร่วมมากที่สุดของและ${\displaystyle K=\gcd(a,N)}$${\displaystyle a}$${\displaystyle N}$
3. ถ้าแล้วจะเป็น ตัวประกอบ ที่ไม่ใช่ตัวประกอบศูนย์ของโดยที่ตัวประกอบอีกตัวคือและเราก็เสร็จสิ้นแล้ว${\displaystyle K\neq 1}$${\displaystyle K}$${\displaystyle N}$${\displaystyle N/K}$
4. หรืออีก วิธีหนึ่ง ให้ใช้ซับรูทีนควอนตัมเพื่อหาลำดับของ${\displaystyle r}$${\displaystyle a}$
5. ถ้าเป็นเลขคี่ ให้กลับไปที่ขั้นตอนที่ 1${\displaystyle r}$
6. คำนวณถ้าไม่ใช่จำนวนที่ไม่สำคัญ แสดงว่าตัวประกอบอีกตัวคือและเราก็เสร็จสิ้นแล้ว มิฉะนั้น ให้กลับไปที่ขั้นตอนที่ 1${\displaystyle g=\gcd(N,a^{r/2}+1)}$${\displaystyle g}$${\displaystyle N/g}$

ได้มีการแสดงให้เห็นแล้วว่าสิ่งนี้มีแนวโน้มที่จะประสบความสำเร็จหลังจากดำเนินการเพียงไม่กี่ครั้ง^{[ 2 ]}ในทางปฏิบัติ การเรียกใช้ซับรูทีนการค้นหาลำดับควอนตัมเพียงครั้งเดียวก็เพียงพอที่จะแยกตัวประกอบได้อย่างสมบูรณ์ด้วยความน่าจะเป็นที่สูงมากหากใช้การลดขั้นสูงกว่า^{[ 19 ]}${\displaystyle N}$

เป้าหมายของขั้นตอนย่อยควอนตัมของอัลกอริทึมของชอร์คือการหาลำดับของโมดู ลัส n ซึ่ง เป็น จำนวนเต็ม บวกที่เล็กที่สุดที่ทำให้ n = n โดยกำหนดจำนวนเต็มที่ ไม่มีตัวหารร่วม n เพื่อให้บรรลุเป้าหมายนี้ อัลกอริทึมของชอร์ใช้วงจรควอนตัมที่ประกอบด้วยรีจิสเตอร์สองตัว รีจิสเตอร์ตัวที่สองใช้คิวบิต โดยที่ n คือจำนวนเต็มที่เล็กที่สุดที่ทำให้n = n นั่นคือ n = n ขนาดของรีจิสเตอร์ตัวแรกกำหนดความแม่นยำของการประมาณค่าที่วงจรสร้างขึ้น สามารถแสดงได้ว่าการใช้คิวบิตให้ความแม่นยำเพียงพอที่จะหา n = n วงจรควอนตัมที่แน่นอนขึ้นอยู่กับพารามิเตอร์n และn ซึ่งกำหนดปัญหา คำอธิบายต่อไปนี้ของอัลกอริทึมใช้สัญกรณ์ bra–ketเพื่อแสดงสถานะควอนตัม และ t เพื่อแสดงผลคูณเทนเซอร์ ${\displaystyle N}$${\displaystyle 1<a<N}$${\displaystyle r}$${\displaystyle a}$${\displaystyle N}$${\displaystyle r}$${\displaystyle a^{r}\equiv 1{\pmod {N}}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle N\leq 2^{n}}$${\displaystyle n=\left\lceil {\log _{2}N}\right\rceil }$${\displaystyle 2n}$${\displaystyle r}$${\displaystyle a}$${\displaystyle N}$${\displaystyle \otimes }$

อัลกอริทึมนี้ประกอบด้วยสองขั้นตอนหลัก:

1. ใช้การประมาณค่าเฟสควอนตัมด้วยเมทริกซ์เอกภาพ ที่แสดงการดำเนินการคูณด้วย(โมดูลัส) และสถานะอินพุต(โดยที่รีจิสเตอร์ที่สองสร้างจากคิวบิต) ค่าลักษณะเฉพาะของเมทริกซ์นี้เข้ารหัสข้อมูลเกี่ยวกับคาบเวลา และสามารถมองได้ว่าสามารถเขียนได้เป็นผลรวมของเวกเตอร์ลักษณะเฉพาะ ด้วยคุณสมบัติเหล่านี้ ขั้นตอนการประมาณค่าเฟสควอนตัมจึงให้ผลลัพธ์เป็นจำนวนเต็มสุ่มในรูปแบบสำหรับค่าสุ่ม${\displaystyle U}$${\displaystyle a}$${\displaystyle N}$${\displaystyle |0\rangle ^{\otimes 2n}\otimes |1\rangle }$${\displaystyle |1\rangle }$${\displaystyle n}$${\displaystyle U}$${\displaystyle |1\rangle }$${\displaystyle {\frac {j}{r}}2^{2n}}$${\displaystyle j=0,1,...,r-1}$
2. ใช้ขั้นตอนวิธีเศษส่วนต่อเนื่องเพื่อแยกคาบเวลาจากผลการวัดที่ได้ในขั้นตอนก่อนหน้า ขั้นตอนนี้เป็นการประมวลผลเพิ่มเติม (ด้วยคอมพิวเตอร์แบบคลาสสิก) ข้อมูลการวัดที่ได้จากการวัดสถานะควอนตัมขาออก และดึงคาบเวลาออกมา${\displaystyle r}$

ความเชื่อมโยงกับการประมาณเฟสควอนตัมไม่ได้ถูกกล่าวถึงในสูตรดั้งเดิมของอัลกอริทึมของ Shor ^{[ 2 ]}แต่ได้รับการเสนอโดยAlexei Kitaevใน ภายหลัง ^{[ 20 ]}

โดยทั่วไปแล้วอัลกอริทึมการประมาณค่าเฟสควอนตัมสำหรับตัวดำเนินการเอกภาพและสถานะเฉพาะ ใดๆ ที่จะส่งสถานะอินพุตไปยังสถานะเอาต์พุตที่ใกล้เคียงกับโดยที่เป็นการซ้อนทับของจำนวนเต็มที่ใกล้เคียง กับ กล่าวอีกนัยหนึ่งคือ จะส่งสถานะเฉพาะแต่ละสถานะของไปยังสถานะที่มีข้อมูลที่ใกล้เคียงกับค่าเฉพาะที่เกี่ยวข้อง สำหรับวัตถุประสงค์ของการค้นหาลำดับควอนตัม เราใช้กลยุทธ์นี้โดยใช้ตัวดำเนินการเอกภาพที่กำหนดโดยการกระทำการกระทำของบนสถานะที่มีไม่สำคัญต่อการทำงานของอัลกอริทึม แต่จำเป็นต้องรวมไว้เพื่อให้แน่ใจว่าการแปลงโดยรวมเป็นเกตควอนตัมที่กำหนดไว้อย่างดี การสร้างวงจรสำหรับการประมาณค่าเฟสควอนตัมด้วยจำเป็นต้องสามารถสร้างเกตได้อย่างมีประสิทธิภาพซึ่งสามารถทำได้ผ่านการยกกำลังแบบโมดูลาร์ซึ่งเป็นส่วนที่ช้าที่สุดของอัลกอริทึม ${\displaystyle U}$${\displaystyle |\psi \rangle }$${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$${\displaystyle |0\rangle |\psi \rangle }$${\displaystyle |\phi \rangle |\psi \rangle }$${\displaystyle \phi }$${\displaystyle 2^{2n}\theta }$${\displaystyle |\psi _{j}\rangle }$${\displaystyle U}$$${\displaystyle U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}}$$${\displaystyle U}$${\displaystyle |k\rangle }$${\displaystyle N\leq k<2^{n}}$${\displaystyle U}$${\displaystyle U^{2^{j}}}$

ประตูที่กำหนดขึ้นนี้สอดคล้องกับเงื่อนไขซึ่งหมายความโดยทันทีว่าค่าลักษณะเฉพาะของมันคือ ราก ที่ของเอกภาพยิ่งไปกว่านั้น ค่าลักษณะเฉพาะแต่ละค่ามีเวกเตอร์ลักษณะเฉพาะในรูปแบบและเวกเตอร์ลักษณะเฉพาะเหล่านี้เป็นไปตามเงื่อนไข โดย เอกลักษณ์สุดท้ายได้มาจาก สูตร อนุกรมเรขาคณิตซึ่งหมายความว่า ${\displaystyle U^{r}=I}$${\displaystyle r}$${\displaystyle \omega _{r}^{k}=e^{2\pi ik/r}}$${\displaystyle \omega _{r}^{j}}$${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$$${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\psi _{j}\rangle &={\frac {1}{r}}\sum _{j=0}^{r-1}\sum _{k=0}^{r-1}\omega _{r}^{jk}|a^{k}\rangle \\&=|1\rangle +{\frac {1}{r}}\sum _{k=1}^{r-1}\left(\sum _{j=0}^{r-1}\omega _{r}^{jk}\right)|a^{k}\rangle =|1\rangle ,\end{aligned}}}$$${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$

การใช้การประมาณค่าเฟสควอนตัมกับสถานะอินพุตจะส่งคืนค่าจำนวนเต็มด้วยความน่าจะเป็นสูง กล่าวโดยละเอียดกว่านั้น วงจรการประมาณค่าเฟสควอนตัมจะส่งสัญญาณไปยังค่าดังกล่าวเพื่อให้การกระจายความน่าจะเป็นที่ได้มีค่าสูงสุดอยู่ที่ประมาณโดยที่ความน่าจะเป็นนี้สามารถทำให้ใกล้เคียงกับ 1 ได้อย่างไม่จำกัดโดยใช้คิวบิตเพิ่มเติม ${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$${\displaystyle 2^{2n}j/r}$${\displaystyle |0\rangle ^{\otimes 2n}|\psi _{j}\rangle }$${\displaystyle |\phi _{j}\rangle |\psi _{j}\rangle }$${\displaystyle p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}}$${\displaystyle k=2^{2n}j/r}$${\displaystyle p_{2^{2n}j/r}\geq 4/\pi ^{2}\approx 0.4053}$

เมื่อนำเหตุผลข้างต้นมาใช้กับข้อมูลป้อนเข้าการประมาณค่าเฟสควอนตัมจึงส่งผลให้เกิดวิวัฒนาการเมื่อวัดค่าในรีจิสเตอร์แรก เราจะมีโอกาสที่สมดุลในการค้นหาแต่ละค่าโดยแต่ละค่าจะให้ค่าประมาณจำนวนเต็มของซึ่งสามารถหารด้วยเพื่อให้ได้ค่าประมาณทศนิยมของ ${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle }$$${\displaystyle |0\rangle ^{\otimes 2n}|1\rangle ={\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|0\rangle ^{\otimes 2n}|\psi _{j}\rangle \to {\frac {1}{\sqrt {r}}}\sum _{j=0}^{r-1}|\phi _{j}\rangle |\psi _{j}\rangle .}$$${\displaystyle 1/r}$${\displaystyle |\phi _{j}\rangle }$${\displaystyle 2^{2n}j/r}$${\displaystyle 2^{2n}}$${\displaystyle j/r}$

จากนั้น เราใช้ อัลกอริธึม เศษส่วนต่อเนื่องเพื่อค้นหาจำนวนเต็มและโดยที่ให้ค่าประมาณเศษส่วนที่ดีที่สุดสำหรับค่าประมาณที่วัดได้จากวงจร สำหรับและเป็นจำนวนเฉพาะสัมพัทธ์และจำนวนคิวบิตในรีจิสเตอร์แรกซึ่งกำหนดความแม่นยำของค่าประมาณ รับประกันว่า เมื่อกำหนดค่าประมาณที่ดีที่สุดจากซูเปอร์โพซิชันของจะถูกวัด^{[ 2 ]} (ซึ่งสามารถทำให้เป็นไปได้มากโดยการใช้บิตพิเศษและตัดทอนเอาต์พุต) อย่างไรก็ตาม ในขณะที่และเป็นจำนวนเฉพาะสัมพัทธ์ อาจเป็นไปได้ว่าและไม่ใช่จำนวนเฉพาะสัมพัทธ์ ด้วยเหตุนี้และอาจสูญเสียปัจจัยบางอย่างที่อยู่ในและปัญหานี้สามารถแก้ไขได้โดยการเรียกใช้ซับรูทีนการค้นหาลำดับควอนตัมซ้ำเป็นจำนวนครั้งตามอำเภอใจ เพื่อสร้างรายการค่าประมาณเศษส่วนโดยที่คือจำนวนครั้งที่เรียกใช้ซับรูทีน แต่ละค่าจะมีปัจจัยที่แตกต่างกันถูกนำออกไป เนื่องจากวงจรจะ (น่าจะ) วัดค่าที่เป็นไปได้หลายค่าที่แตกต่างกันของ เพื่อกู้คืนค่าที่แท้จริงเราสามารถใช้ตัวคูณร่วมน้อยที่สุดของแต่ละค่าได้: ตัวคูณร่วมน้อยที่สุดจะเป็นลำดับของจำนวนเต็มดั้งเดิมด้วยความน่าจะเป็นสูง ในทางปฏิบัติ โดยทั่วไปแล้ว การเรียกใช้ซับรูทีนการค้นหาลำดับควอนตัมเพียงครั้งเดียวก็เพียงพอแล้ว หากมีการใช้การประมวลผลภายหลังขั้นสูงกว่า^{[ 21 ]}${\displaystyle b}$${\displaystyle c}$${\displaystyle b/c}$${\displaystyle b,c<N}$${\displaystyle b}$${\displaystyle c}$${\displaystyle 2n}$$${\displaystyle {\frac {b}{c}}={\frac {j}{r}},}$$${\displaystyle |\phi _{j}\rangle }$${\displaystyle b}$${\displaystyle c}$${\displaystyle j}$${\displaystyle r}$${\displaystyle b}$${\displaystyle c}$${\displaystyle j}$${\displaystyle r}$$${\displaystyle {\frac {b_{1}}{c_{1}}},{\frac {b_{2}}{c_{2}}},\ldots ,{\frac {b_{s}}{c_{s}}},}$$${\displaystyle s}$${\displaystyle c_{k}}$${\displaystyle j}$${\displaystyle r}$${\displaystyle c_{k}}$$${\displaystyle \operatorname {lcm} (c_{1},c_{2},\ldots ,c_{s}).}$$${\displaystyle r}$${\displaystyle a}$

การประมาณค่าเฟสจำเป็นต้องเลือกขนาดของรีจิสเตอร์ตัวแรกเพื่อกำหนดความแม่นยำของอัลกอริทึม และสำหรับซับรูทีนควอนตัมของอัลกอริทึมของ Shor จำนวนคิวบิตก็เพียงพอที่จะรับประกันได้ว่าสตริงบิตที่เหมาะสมที่สุดที่วัดได้จากการประมาณค่าเฟส (หมายถึงตำแหน่งที่เป็นการประมาณค่าเฟสที่แม่นยำที่สุดจากการประมาณค่าเฟส) จะช่วยให้สามารถกู้คืนค่าจริงของได้ ${\displaystyle 2n}$${\displaystyle |k\rangle }$${\textstyle k/2^{2n}}$${\displaystyle r}$

การวัดก่อน แต่ละครั้งในอัลกอริทึมของ Shor แสดงถึงการซ้อนทับของจำนวนเต็มที่ประมาณค่า ให้ แทนจำนวนเต็มที่เหมาะสมที่สุดในทฤษฎีบทต่อไปนี้รับประกันว่าอัลกอริทึมเศษส่วนต่อเนื่องจะสามารถกู้คืนจาก ได้: ${\displaystyle |\phi _{j}\rangle }$${\displaystyle 2^{2n}j/r}$${\displaystyle |k\rangle }$${\displaystyle |\phi _{j}\rangle }$${\displaystyle j/r}$${\displaystyle k/2^{2{n}}}$

^{[ 3 ]}เนื่องจากสตริงบิตที่เหมาะสมที่สุดจากการประมาณเฟสมีความแม่นยำเป็นบิตดังนั้นซึ่งหมายความว่าอัลกอริทึมเศษส่วนต่อเนื่องจะกู้คืนและ(หรือโดยนำตัวหารร่วมมากที่สุดออก) ${\displaystyle k}$${\displaystyle k/2^{2{n}}}$${\displaystyle j/r}$${\displaystyle 2n}$$${\displaystyle \left\vert {\frac {j}{r}}-{\frac {k}{2^{2n}}}\right\vert \leq {\frac {1}{2^{2{n}+1}}}\leq {\frac {1}{2N^{2}}}\leq {\frac {1}{2r^{2}}}}$$${\displaystyle j}$${\displaystyle r}$

ข้อจำกัดด้านเวลาในการทำงานของอัลกอริทึมของ Shor คือการยกกำลังแบบโมดูลาร์ ควอนตัม ซึ่งช้ากว่าการแปลงฟูริเยร์ควอนตัมและการประมวลผลก่อน/หลังแบบคลาสสิกมาก มีหลายแนวทางในการสร้างและปรับวงจรสำหรับการยกกำลังแบบโมดูลาร์ แนวทางที่ง่ายที่สุดและ (ในปัจจุบัน) ใช้งานได้จริงมากที่สุดคือการเลียนแบบวงจรเลขคณิตแบบดั้งเดิมด้วยเกตแบบย้อนกลับได้โดยเริ่มจากตัวบวกแบบริปเปิลแครี่การรู้ฐานและโมดูลัสของการยกกำลังช่วยให้สามารถปรับให้เหมาะสมยิ่งขึ้นได้^{[ 22 ] [ 23 ]} วงจรแบบย้อนกลับได้มักใช้ เกตในลำดับของจำนวนคิวบิต เทคนิคทางเลือกอื่น ๆ ปรับปรุงจำนวนเกตแบบเชิงเส้นกำกับโดยใช้การแปลงฟูริเยร์ควอนตัมแต่ไม่สามารถแข่งขันได้กับคิวบิตน้อยกว่า 600 ตัวเนื่องจากค่าคงที่สูง ${\displaystyle n^{3}}$${\displaystyle n}$

อัลกอริทึมของ Shor สำหรับ ปัญหา ลอการิทึมแบบไม่ต่อเนื่องและปัญหาการหาลำดับเป็นตัวอย่างหนึ่งของอัลกอริทึมที่ใช้แก้ปัญหาการหาคาบเวลา ทั้งสามอย่างนี้เป็นตัวอย่างหนึ่งของปัญหากลุ่มย่อยที่ซ่อนอยู่

กำหนดให้กลุ่ม ที่มีอันดับและตัวสร้างสมมติว่าเรารู้ว่าสำหรับบางค่าและเราต้องการคำนวณซึ่งก็คือลอการิทึมแบบไม่ต่อเนื่อง : พิจารณากลุ่มอาเบเลียนโดยที่แต่ละแฟกเตอร์สอดคล้องกับการบวกแบบมอดูลาร์ของค่าต่างๆ ทีนี้ พิจารณาฟังก์ชัน ${\displaystyle G}$${\displaystyle p}$${\displaystyle g\in G}$${\displaystyle x=g^{r}\in G}$${\displaystyle r\in \mathbb {Z} _{p}}$${\displaystyle r}$${\displaystyle r={\log _{g}}(x)}$${\displaystyle \mathbb {Z} _{p}\times \mathbb {Z} _{p}}$

${\displaystyle f\colon \mathbb {Z} _{p}\times \mathbb {Z} _{p}\to G\;;\;f(a,b)=g^{a}x^{-b}.}$

สิ่งนี้ทำให้เราได้ปัญหากลุ่มย่อยที่ซ่อนอยู่ แบบอาเบเลียน โดยที่สอดคล้องกับ โฮโมมอร์ฟิ ซึมของกลุ่มเคอร์เนลสอดคล้องกับตัวคูณของดังนั้น ถ้าเราสามารถหาเคอร์เนลได้ เราก็สามารถหาได้มีอัลกอริทึมควอนตัมสำหรับการแก้ปัญหานี้ อัลกอริทึมนี้ เช่นเดียวกับอัลกอริทึมการค้นหาตัวประกอบ เป็นผลงานของปีเตอร์ ชอร์ และทั้งสองถูกนำไปใช้โดยการสร้างการซ้อนทับผ่านการใช้เกตฮาดามาร์ด ตามด้วยการนำไปใช้เป็นการแปลงควอนตัม ตามด้วยการแปลงฟูริเยร์ควอนตัมในที่สุด^{[ 3 ]}ด้วยเหตุนี้ อัลกอริทึมควอนตัมสำหรับการคำนวณลอการิทึมแบบไม่ต่อเนื่องจึงถูกเรียกว่า "อัลกอริทึมของชอร์" ในบางครั้ง ${\displaystyle f}$${\displaystyle (r,1)}$${\displaystyle r}$${\displaystyle f}$

ปัญหาการค้นหาลำดับยังสามารถมองได้ว่าเป็นปัญหากลุ่มย่อยที่ซ่อนอยู่^{[ 3 ]}เพื่อให้เห็นสิ่งนี้ ให้พิจารณากลุ่มของจำนวนเต็มภายใต้การบวก และสำหรับค่าที่กำหนดซึ่ง: ฟังก์ชัน ${\displaystyle a\in \mathbb {Z} }$${\displaystyle a^{r}=1}$

${\displaystyle f\colon \mathbb {Z} \to \mathbb {Z} \;;\;f(x)=a^{x},\;f(x+r)=f(x).}$

สำหรับกลุ่มอาเบเลียนจำกัดใดๆจะมีอัลกอริทึมควอนตัมสำหรับการแก้ปัญหากลุ่มย่อยที่ซ่อนอยู่ภายในเวลาพหุนาม^{[ 3 ]}${\displaystyle G}$${\displaystyle G}$

• GEECMซึ่งเป็นอัลกอริธึมการแยกตัวประกอบที่กล่าวกันว่า "มักจะเร็วกว่าของ Shor มาก" ^{[ 24 ]}
• อัลกอริทึมของโกรเวอร์

• นีลเซ่น, ไมเคิล เอ.; ชวง, ไอแซค แอล. (2010). การคำนวณควอนตัมและสารสนเทศควอนตัม: ฉบับครบรอบ 10 ปี . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 978-1-107-00217-3.
• Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2006). บทนำสู่การคำนวณควอนตัม doi : 10.1093 /oso/9780198570004.001.0001 ISBN 978-0-19-857000-4.
• บทความเรื่อง "คำอธิบายสำหรับคนทั่วไป"โดยScott Aaronsonได้รับการ " รับรอง " โดย Peter Shor (Shor เขียนว่า "บทความเยี่ยมมาก Scott! นี่คือการอธิบายการคำนวณควอนตัมให้คนทั่วไปเข้าใจได้ดีที่สุดเท่าที่ผมเคยเห็นมา") มีการนำเสนออุปมาอุปไมยอื่นสำหรับทฤษฎีสนามควอนตัม (QFT) ในความคิดเห็นหนึ่ง Scott Aaronson แนะนำเอกสารอ้างอิง 12 รายการต่อไปนี้สำหรับการอ่านเพิ่มเติม (จาก "บทเรียนเกี่ยวกับอัลกอริธึมควอนตัมกว่า^{10,000บทเรียน}ที่มีอยู่บนเว็บ"):
• Shor, Peter W. (1997), "อัลกอริทึมเวลาพหุนามสำหรับการแยกตัวประกอบเฉพาะและลอการิทึมแบบไม่ต่อเนื่องบนคอมพิวเตอร์ควอนตัม", SIAM J. Comput. , 26 (5): 1484– 1509, arXiv : quant-ph/9508027v2 , Bibcode : 1999SIAMR..41..303S , doi : 10.1137/S0036144598347011ฉบับปรับปรุงแก้ไขจากบทความต้นฉบับโดย ปีเตอร์ ชอร์ ("28 หน้า, LaTeX. นี่คือฉบับขยายความของบทความที่ตีพิมพ์ในรายงานการประชุมสัมมนาประจำปีครั้งที่ 35 เรื่องพื้นฐานของวิทยาการคอมพิวเตอร์ ณ เมืองซานตาเฟ รัฐนิวเม็กซิโก วันที่ 20-22 พฤศจิกายน 1994 มีการแก้ไขเล็กน้อยในเดือนมกราคม 1996")
• การคำนวณควอนตัมและอัลกอริทึมของชอร์ , หน้าเว็บอัลกอริทึมควอนตัมของแมทธิว เฮย์เวิร์ด, 17 กุมภาพันธ์ 2548, imsa.edu, เวอร์ชัน LaTeX2HTML ของเอกสาร LaTeX ต้นฉบับ มีให้ดาวน์โหลดในรูปแบบ PDFหรือเอกสารPostscriptด้วย
• การคำนวณควอนตัมและอัลกอริทึมการแยกตัวประกอบของชอร์ , โรนัลด์ เดอ วูล์ฟ, CWI และมหาวิทยาลัยอัมสเตอร์ดัม, 12 มกราคม 1999, เอกสารโพสต์สคริปต์ 9 หน้า
• อัลกอริทึมการแยกตัวประกอบของ Shorบันทึกจากการบรรยายครั้งที่ 9 ของวิชา Berkeley CS 294–2 ลงวันที่ 4 ตุลาคม 2547 เอกสาร Postscript 7 หน้า
• บทที่ 6 การคำนวณควอนตัม เก็บถาวรเมื่อวันที่ 30 เมษายน 2020 ที่Wayback Machineเอกสาร Postscript จำนวน 91 หน้า Caltech, Preskill, PH229
• การคำนวณควอนตัม: คู่มือโดยซามูเอล แอล. บราวน์สไตน์
• สถานะควอนตัมของอัลกอริทึมของชอร์โดย นีล ยัง แก้ไขล่าสุด: วันอังคารที่ 21 พฤษภาคม 1996 เวลา 11:47:38
• III. การถอดรหัส RSA ด้วยคอมพิวเตอร์ควอนตัม: อัลกอริทึมการแยกตัวประกอบของ Shor เอกสารประกอบการบรรยายเกี่ยวกับการคำนวณควอนตัม มหาวิทยาลัยคอร์เนล วิชาฟิสิกส์ 481–681, CS 483 ภาคเรียนฤดูใบไม้ผลิ ปี 2006 โดย N. David Mermin แก้ไขล่าสุด 28 มีนาคม 2006 เอกสาร PDF 30 หน้า
• Lavor, C.; Manssur, LRU; Portugal, R. (2003). "อัลกอริทึมของ Shor สำหรับการแยกตัวประกอบจำนวนเต็มขนาดใหญ่". arXiv : quant-ph/0303175 .
• Lomonaco, Jr (2000). "อัลกอริทึมการแยกตัวประกอบควอนตัมของ Shor". arXiv : quant-ph/0010034 .เอกสารฉบับนี้เป็นเอกสารที่เขียนขึ้นจากบทบรรยายหนึ่งชั่วโมงเกี่ยวกับอัลกอริทึมการแยกตัวประกอบควอนตัมของปีเตอร์ ชอร์ จำนวน 22 หน้า
• บทที่ 20 การคำนวณควอนตัมจาก หนังสือ "ความซับซ้อนของการคำนวณ: แนวทางสมัยใหม่ " ฉบับร่าง: มกราคม 2550 โดย Sanjeev Arora และ Boaz Barak มหาวิทยาลัยพรินซ์ตัน ตีพิมพ์เป็นบทที่ 10 การคำนวณควอนตัม ในหนังสือ "ความซับซ้อนของการคำนวณ: แนวทางสมัยใหม่" โดย Sanjeev Arora และ Boaz Barak สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ ปี 2009 ISBN 978-0-521-42426-4
• ก้าวแรกสู่การคำนวณควอนตัม: การพันกันของอนุภาค 10 พันล้านอนุภาคเก็บถาวรเมื่อวันที่ 20 มกราคม 2011 ในWayback Machineจากนิตยสาร "Discover Magazine" ลงวันที่ 19 มกราคม 2011
• Josef Gruska - ความท้าทายของการคำนวณควอนตัมในคณิตศาสตร์ไร้ขีดจำกัด: ปี 2001 และหลังจากนั้นบรรณาธิการ Björn Engquist, Wilfried Schmid, Springer, 2001, ISBN 978-3-540-66913-5

• libquantumเวอร์ชัน 1.0.0 ประกอบด้วยการใช้งานอัลกอริธึมของ Shor ด้วยภาษา C โดยใช้ไลบรารีคอมพิวเตอร์ควอนตัมจำลอง แต่ควรตั้งค่าตัวแปร width ในไฟล์ shor.c เป็น 1 เพื่อปรับปรุงความซับซ้อนของรันไทม์
• PBS Infinite Seriesได้สร้างวิดีโอสองตอนที่อธิบายหลักการทางคณิตศาสตร์เบื้องหลังอัลกอริทึมของชอร์ ได้แก่ " วิธีการถอดรหัสลับ " และ " การแฮ็กด้วยความเร็วควอนตัมโดยใช้อัลกอริทึมของชอร์ "
• การนำอัลกอริทึมของ Shor มาใช้งานอย่างสมบูรณ์ด้วย Classiq