התמרת פורייה קוונטית

בחישוב קוונטי, התמרת פורייה קוונטית היא שער קוונטי המבצע התמרת פורייה בדידה. פעולה זו בעלת חשיבות רבה עבור אלגוריתמים שונים בחישוב קוונטי, ובפרט אלגוריתם שור לפירוק לגורמים של מספר שלם, ואלגוריתם למציאת תת חבורה חבויהתבנית:אנ.

בעוד שחישוב התמרת פורייה "קלאסית" על קלט באורך $n$ דורשת ביצוע $O(n{2}^n)$ פעולות, הרי שביצוע פעולה זו על גבי מחשב קוונטי אפשרית על ידי ביצוע $O(n\log n)$ פעולות בלבדתבנית:הערה (כלומר, הפעלת $O(n\log n)$ שערים קוונטיים). מכאן שקיים יתרון מעריכי בסיבוכיות של הפעולה הקוונטית לעומת המקבילה הקלאסית.

מאידך, בעוד הפעולה ה"קלאסית" פועלת על וקטור של ערכים, הפעולה הקוונטית היא על מצב קוונטי הנמצא בסופרפוזיציה קוונטית, כאשר המקדמים מתארים את ערכי הווקטור הקלאסי השקול. מכיוון שלא ניתן לבצע מדידה ישירה של ערכי המקדמים בסופרפוזיציה קוונטית, השקילות אינה מלאה, ולא ניתן לקבל שיפור מעריכי עבור ביצוע ההתמרה באופן כללי.

הגדרה

הפעלת השער על אוגר בעל $n$ קיוביטים במצב הקוונטי $|x⟩$, כאשר $0\le x\le 2^n-1$ מוגדרת על ידי $$|x⟩\stackrel{\text{QFT}}{\to }\frac{1}{\sqrt{2^n}}\sum _{y=0}^{2^n-1}{e}^{2\pi ixy/2^n}|y⟩$$ כאשר $xy$ היא המכפלה של שני המספרים השלמים x ו-y.

קישורים חיצוניים

• תבנית:לא מדויק