כל מה שרצית לדעת על אלגוריתם שור:
אלגוריתם שוֹר (Shor – על שם פיטר שור, ממציאו), הוא אלגוריתם קוונטי המשמש לפירוק לגורמים של מספר גדול, כלומר מציאת הגורמים הראשוניים של המספר.
האלגוריתם פורסם לראשונה על ידי פיטר שור בשנת 1994, ויחד עם אלגוריתם גרובר נחשב לאחד משני האלגוריתמים החשובים ביותר בתחום החישוב הקוונטי.
פיתוח האלגוריתם זיכה את ממציאו בפרס גדל (1999).
אלגוריתם שור מבוסס על הרעיונות הקוונטיים שהודגמו באלגוריתם סימון למציאת מחזור של פונקציה.
האלגוריתם עושה שימוש בהתמרת פורייה קוונטית (QFT), על מנת לקבל מחזור שהינו כפולה של אחד מהגורמים הראשוניים של המספר אותו רוצים לפרק.
האלגוריתמים הטובים ביותר הידועים, מפרקים מספר גדול ,לגורמיו בסיבוכיות זמן של , שאינה פולינומית ב-.
לעומת זאת, אלגוריתם שור פועל בסיבוכיות זמן של .
אלגוריתם זה מהווה דוגמה ליתרון אקספוננציאלי בסיבוכיות הזמן של אלגוריתמים קוונטיים לעומת אלגוריתם קלאסי.