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

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

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

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

הגדרה

הפעלת השער על אוגר בעל ${\displaystyle \ n}$ קיוביטים במצב הקוונטי ${\displaystyle |x\rangle }$, כאשר ${\displaystyle 0\leq x\leq 2^{n}-1}$ מוגדרת על ידי $${\displaystyle |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 }$$ כאשר ${\displaystyle \ xy}$ היא המכפלה של שני המספרים השלמים x ו-y.

הערות שוליים

1. L. Hales, S. Hallgren, "An improved quantum Fourier transform algorithm and applications", Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.515, November 2000.

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