1965年にIBMの研究者によって初めて考案された高速フーリエ変換（FFT、Fast Fourier Transform）は、それ以降のコンピューティングの世界をがらりと変えました。量子アルゴリズムの開発に関して、そこからどのような教訓を学べるのでしょうか？
2025年6月11日、米国電気電子学会（IEEE、the Institute of Electrical and Electronics Engineers）は、高速フーリエ変換（FFT)の初の実用的デモを記念して、IBMにマイルストーン賞を授与しました。
このアルゴリズムは、近代的なコンピューティングの世界を一変させました。FFTは、JPEGおよびMPEG規格の基盤であり、MRIやCTスキャン画像の再構成などにも使用されています（詳細についてはIBM Researchのブログをご覧ください)。
しかし、FFTの物語はこれで終わりではありません。むしろ、FFTから得られる教訓はコンピューティングの未来にインスピレーションを与えてくれます。量子コンピューティングの未来について考える際にはとりわけです。FFTは、適切な表現形式を選択することで不可能を可能にすることを教えてくれましたが、これは新しい量子アルゴリズムを模索する際に重要な教訓となるでしょう。
James CooleyとJohn Tukeyが1965年にFFTを発明したとき、彼らは新しい物理現象を発見したのではなく、情報を表現するためのより良い方法を見つけたのでした。フーリエ変換は、時間領域の信号（波）を受け取り、それをさまざまな周波数の単純な波の合計に分割し、複雑な情報を理解するための新しくて秩序ある方法です。しかし、1960年代以前は、フーリエ変換の計算は遅すぎて、地震波の解読などのリアルタイム・アプリケーションには役立ちませんでした。
そこでFFTの出番です。1963年、John Tukey とJames Cooleyは、数学的トリックを利用してこの変換の実行に必要な反復回数を減らして、科学計算用コンピューターで利用する際に大幅に加速が得られるアルゴリズムを考案しました。その結果、離散フーリエ変換の計算量がO(N2)からO(N log N)に削減されました。これは大幅な改善です。
そのようなFFTの発明があって、リアルタイム信号処理は可能になりました。今日、CooleyとTukeyのFFTアルゴリズムは、通信(4G/5G、WiFiなど)、オーディオおよびビデオ圧縮（MP3、JPEGなど)、医用画像(MRI、CTなど)、科学計算(偏微分方程式を解くためのスペクトル法) などに使用されています。Richard Hammingが言ったように、「Cooley-Tukey FFTは、私たちの生涯で最も重要な数値計算アルゴリズムである」のです。
彼らのFFTアルゴリズムがこれほどまでに影響力を持つようになったのはなぜでしょうか？その答えは、次のようなシンプルな洞察として述べることができます。数学的表現を変えると、計算対象の問題も形が変わります。
科学の一歩一歩には、抽象化（現実をモデル化する行為）と、それらのモデルを計算可能な形でエンコードする表現形式が含まれています。
ビットは、物理状態をバイナリ値に抽象化したものです。たとえば「有料」と「無料」を0と1に抽象化できます。
数値は量の抽象化です。物が五つある時それらは、「5」、「V」、または「101」として表すことができます。
FFTは、数学的変換によって、同じ情報を別の形で表現する新しい表現を用いて、より簡単で高速な計算が可能になったケースです。FFTを用いると、乱雑な時間領域信号を、周波数領域で、より単純な項の合計として表現できます。
しかし、コンピューティングの未来について考える場合には、データを表現するさまざまな異なった方法を考えるだけではいけません。たとえば5、V、および 101 のように表現を変えたとしても機能的には同じかもしれません。私たちは、まったく新しい計算パラダイムでデータを研究できるように、データを抽象化する新しい方法を考える必要があります。
表現形式とは、私たちが世界を見て計算するためのレンズです。レンズを交換すれば、すべてが違って見えるのです。
量子コンピューティングは、単に古典手法を改善するだけでなく、情報表現と処理方法自体を再定義します。古典的な演算が決定論的であるのに対し、量子計算は重ね合わせ、干渉、量子もつれを利用したダンスのようなものであり、素粒子の本質的に確率的な性質と格闘することで、決定論的な答えに到達します。
古典コンピューティングでは、情報はバイナリコードとしてビットにエンコードされます。演算はブール演算で決定論的であり、"AND"、"OR"、"NOT" などのビット間の論理演算は "TRUE"と "FALSE"のどちらかを返して、次のビットの出力を決定します。
しかし、量子コンピューティングでは、情報は複素ベクトル空間に存在する確率振幅として量子ビットに符号化されます。各量子ビットは "0" や "1" ではなく、α|0⟩ + β|1⟩ を格納します。ここで確率振幅 α と β は a + bi 形式の複素数です。古典的な論理ではなく、計算は行列演算を使用した量子ビット状態のユニタリ発展となり、結果は量子力学の公理と完全に一致する確率的射影になります。計算の最後に、α と β を使用して、量子ビットが 0 または 1 を出力する確率が計算されます。
この新しい考え方により、まったく新しい計算能力が可能になります。ショアのアルゴリズムは、量子フーリエ変換を使用して、古典アルゴリズム2よりも指数関数的に速く整数を因数分解します。グローバーのアルゴリズムは、非構造化検索の 2次高速化を実現し、検索を O(N) クエリから O(√N) クエリに減らします 3。また、量子シミュレーションにより、古典的な計算機では扱いにくい量子系をモデル化することができます。 これは「自然は古典力学的ではない。自然のシミュレーションをしたいならば、量子力学を利用する方がよい」というファインマンの当初のビジョン4だったことです。
量子コンピューティングは、抽象化とその表現の両方を変更すると何が起こるかを示す例です。
量子は、世界を見る上で、これまでと大きく異なるレンズになりますが、未来に最大の革命を起こすのは量子と古典のどちらでもありません。それら二つの相乗効果が起こすのです。
というのは、まず、これら二つのパラダイムには、異なる長所と補完的な能力があるということがあります。古典コンピューターは、制御ロジック、データ・ストレージ、決定論的計算、および大規模なデジタル・インフラストラクチャーに優れています。何十年にもわたって改善・最適化が行われた結果として、古典コンピューターはこれらのタスクに非常に優れており、信じられないほどのスピードで計算が可能です。ローレンス・リバモア国立研究所のEl Capitanスーパーコンピューターは、1秒あたり2.75クインティリオン（100万の100万倍の100万倍)の数学演算を実行できます。
量子システムは、これらのタスクをより高速に実行することを約束するものではありません。量子システムは、古典データでは十分うまく表現できないような問題で、El Capitanでさえ答を計算するのに苦労するようなタスクを得意としています。そのようなタスクには、高次元の線形代数演算、確率的サンプリング、最適化ランドスケープの分析、量子現象のシミュレーションなどがあります。
量子と古典の計算パラダイムを組み合わせるということは、たとえば量子計算だけでは解決できない問題や、古典計算だけでは複雑すぎる問題を解決することを意味します。前者の例としては、大規模なパラメトリック・モデルの学習のためのビッグデータ処理がたとえばあります。
次に言えることは、近年、古典コンピューティングの限界が押し広げられているのと同時に、量子の可能性に関する知識が蓄積された結果、新しい実用的なハイブリッド古典・量子アルゴリズムが出現しているということです。
現在利用可能なシステムに最初に実装されたそのようなアルゴリズムの一つは、古典オプティマイザーを使用して量子回路を化学基底状態に導くVQE（Variational Quantum Eigensolver）です。また、QAOA（Quantum Approximate Optimization Algorithm)は、量子重ね合わせと古典フィードバック・ループを組み合わせたアルゴリズムです。
新しいアルゴリズムが発明されていくにしたがって、量子と古典の組み合わせが古典単独を凌駕するという量子優位性の歴史的一歩に、私たちは徐々に徐々に近づいてきています。SQDとSKQD （subspace quantum diagonalization)は、基底エネルギーを推定するための量子ハミルトニアンの古典的なサロゲートを構築できます。また、動的多重積公式は、古典計算（テンソル・ネットワークなど）を使用して、古典では計算が難しい、時間発展させたオブザーバブルの期待値を組み合わせることができます。
これらのアプローチは、特にQiskitで利用可能である高度な回路最適化技術と組み合わせることで、創薬、材料科学、金融、サプライチェーンの最適化において、すでに期待できる結果を示し始めています。Qiskitはこの領域で多くのユーザーに選ばれているオープンソースの量子SDKであり、最もパフォーマンスの高い量子ソフトウェア・スタックです。
そして量子と古典の相乗効果について最後に言えることは、他の最先端のコンピューティング・ハードウェアに目を向ければ、量子は古典を置き換えるのではなく、古典を機能強化していくという未来を予測できるということです。GPUは CPUに取って代わるものではなく、AI とシミュレーションの新領域でCPUを助けました。
量子システムは、同様の方法で古典コンピューティングを強化します。量子システムは、根本的に異なる能力を持つコプロセッサーと考えられます。
量子と古典が組み合わされることで、コンピューティングのボトルネックはハードウェアの限界からアルゴリズムの創造性へとシフトしています。では、量子と古典の相乗効果を十分に活用して、コンピューティング全体を進歩させるにはどうすればよいでしょうか。
そのためには両方の領域にわたって問題を記述する新しい抽象化が必要です。そして、量子回路や古典のプログラム・コードに問題を埋め込んで表現する、新しい表現形式が必要です。さらに、互いに補間し合うアーキテクチャー間でワークロードを動的にバランスする新しいアルゴリズムが必要です。
つまり、私たちは新しいアルゴリズム時代の夜明けを迎えているのです。そして、そのインパクトは、おそらくFFTによって引き起こされた以上になるかもしれません。
IEEEマイルストーン賞の献呈は、時代を超えた考察を試みる絶好の機会です。
ブレークスルーは、多くの場合、ただ大きな力を用いることではなく、より良い質問とより賢明な問題表現から始まります。言い換えれば、新しい考え方から始まるのです。
FFTが信号の表現方法を変えることで古典コンピューティングの風景を変えたように、量子コンピューティングは情報の抽象化そのものを再形成しています。量子時代に足を踏み入れつつある今、取り組むべきチャレンジは単に計算を高速化することではありません。計算の舞台となるキャンバスそのものを再定義することや、そのキャンバスに絵を描く方法を学ぶことがチャレンジなのです。
古典と量子の世界を一つにまとめることで、計算能力の新時代が開かれます。しかし、それには大胆な抽象化と革新的な表現が必要です。世界をつなぐ画期的なアルゴリズムが必要なのです。そして、明日のFouriers、Cooleys、Tukeysになる才能、つまりチャレンジに立ち向かう準備ができている新しい才能が必要です。
これはFFTの物語の終わりではなく、新たな始まりです。
References
1. Cooley, J. W., & Tukey, J. W. (1965). An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90), 297–301.| ↩
2. Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509.| ↩
3. Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212–219.| ↩
4. Feynman, R. P. (1982). Simulating physics with computers. International Journal of Theoretical Physics, 21(6–7), 467–488.| ↩
この記事は英語版IBM Researchブログ「From Representation to Revolution: Celebrating the FFT and the Future of Computing」（2025年6月16日公開、Alessandro Curioni、Jay Gambetta、Ryan Mandelbaum著）を翻訳し一部更新したものです。