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

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

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

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

הגדרה

הפעלת השער על אוגר בעל $\ n$ קיוביטים במצב הקוונטי $|x\rangle$, כאשר $0\leq x\leq 2^{n}-1$ מוגדרת על ידי

$$|x\rangle {\stackrel {\text{QFT}}{\to }}{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}e^{2\pi ixy/2^{n}}|y\rangle$$

כאשר $\ xy$ היא המכפלה של שני המספרים השלמים x ו-y.

הערות שוליים

ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום למכלול ולהרחיב אותו.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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