Lazy Fourier Transform (LFT)
עבור וקטור קלט $ \mathbf{x} $:
- רפד באפסים עד שגודל $ \mathbf{x} $ יהיה חזקה שלמה של 2
- רפד באפסים עד שגודל $ \mathbf{x} $ יהיה חזקה שלמה של 3
- זרוק לו עוד מיליארד אפסים
- עבור ראשוני אקראי $ p $, רפד באפסים עד שגודל $ \mathbf{x} $ יהיה חזקה שלמה של $ p $
- זהו, עכשיו בקירוב טוב $ \mathbf{x} \equiv 0 $, והתמרת פורייה של אפס זה אפס, אז תחזיר אפס
Slow Fourier Transform (SFT)
עבור וקטור קלט $ \mathbf{x} $:
- אתחל $ \mathbf{y}=0 $
- מצא ל-$ \mathbf{x} $ fit שהוא גאוסיאן
- התמרת פורייה של גאוסיאן זה גאוסיאן! אני זוכר כי הייתה לי בדיחה על זה באחד הפוסטים הקודמים
- הוסף ל-$ \mathbf{y} $ את הגאוסיאן המותמר והחסר מ-$ \mathbf{x} $ את הגאוסיאן המקורי
- חזור על התהליך עד ש-$ \mathbf{x}=0 $, ואז החזר את $ \mathbf{y} $
סיבוכיות: לא יודע, זה בכלל מתכנס?
Quantum Fourier Transform (QFT)
- חכה שיצליחו לבנות מחשב קוונטי אמיתי עם מספר גדול של קיוביטים
- הרץ עליו את האלגוריתם הידוע ל-QFT, שלוקח רק $ O(\log n) $
אה, רצית את וקטור הפלט בצורה של וקטור רגיל, ולא נוח לך שהרכיבים שלו שמורים כפאזות של קיוביטים? טוב זו לא בעיה, יש שיטה… *מלמול* מעגל הערכת-פאזה… *מלמול* וזהו, שיהיה בהצלחה!
Bogo Fourier Transform (BFT)
עבור וקטור קלט $ \mathbf{x} $:
- הגרל וקטור אקראי $ \mathbf{y} $
- חשב את התמרת פורייה ההפוכה של $ \mathbf{y} $, שנסמנה $ \text{FT}^{-1} [ \mathbf{y} ] $
- אם $ \mathbf{x} = \text{FT}^{-1} [ \mathbf{y} ] $, החזר $ \mathbf{y} $. אחרת חזור ל-1
הערה: איך לחשב את התמרת פורייה ההפוכה בשלב 2? אמממ… יש פונקציה לזה ב-MATLAB, נראה לי הכי טוב.