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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

הגדרה[עריכת קוד מקור | עריכה]

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

|x\rangle \stackrel{\text{QFT}}{\to}\frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}e^{2\pi i (x\cdot y)/2^n}|y\rangle

כאשר \ x\cdot y הינה המכפלה הסקאלרית של ייצוג \ 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.
P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.