論文の概要: Quantum Fourier Transform Revisited
- arxiv url: http://arxiv.org/abs/2003.03011v2
- Date: Wed, 23 Sep 2020 20:33:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 09:07:30.252563
- Title: Quantum Fourier Transform Revisited
- Title(参考訳): 量子フーリエ変換の再検討
- Authors: Daan Camps and Roel Van Beeumen and Chao Yang
- Abstract要約: 量子フーリエ変換(QFT)は、FFT行列分解の対角係数をKronecker積構造を持つ行列の積に分解することで導出可能であることを示す。
このような構造が量子コンピュータの重要な利点を生かし、量子コンピュータ上で古典的コンピュータ上でのFFTアルゴリズム上での指数的高速化を実現することができるのかを説明する。
- 参考スコア(独自算出の注目度): 3.23402688755667
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The fast Fourier transform (FFT) is one of the most successful numerical
algorithms of the 20th century and has found numerous applications in many
branches of computational science and engineering. The FFT algorithm can be
derived from a particular matrix decomposition of the discrete Fourier
transform (DFT) matrix. In this paper, we show that the quantum Fourier
transform (QFT) can be derived by further decomposing the diagonal factors of
the FFT matrix decomposition into products of matrices with Kronecker product
structure. We analyze the implication of this Kronecker product structure on
the discrete Fourier transform of rank-1 tensors on a classical computer. We
also explain why such a structure can take advantage of an important quantum
computer feature that enables the QFT algorithm to attain an exponential
speedup on a quantum computer over the FFT algorithm on a classical computer.
Further, the connection between the matrix decomposition of the DFT matrix and
a quantum circuit is made. We also discuss a natural extension of a radix-2 QFT
decomposition to a radix-d QFT decomposition. No prior knowledge of quantum
computing is required to understand what is presented in this paper. Yet, we
believe this paper may help readers to gain some rudimentary understanding of
the nature of quantum computing from a matrix computation point of view.
- Abstract(参考訳): 高速フーリエ変換(FFT)は20世紀で最も成功した数値アルゴリズムの1つであり、計算科学と工学の多くの分野において多くの応用が発見されている。
FFTアルゴリズムは離散フーリエ変換(DFT)行列の特定の行列分解から導出することができる。
本稿では,fft行列分解の対角因子をクロネッカー積構造を持つ行列の積にさらに分解することにより,量子フーリエ変換(qft)を導出できることを示す。
古典的コンピュータ上でのランク1テンソルの離散フーリエ変換におけるクローネッカー積構造の影響を解析する。
また、このような構造が量子コンピュータの重要な利点を生かし、古典的コンピュータ上のFFTアルゴリズム上で量子コンピュータ上で指数的高速化を実現することができる理由についても説明する。
さらに、DFT行列の行列分解と量子回路との接続を行う。
また、基数2のQFT分解から基数dのQFT分解への自然な拡張についても論じる。
本論文では, 量子コンピューティングに関する事前知識は不要である。
しかし,本論文は,行列計算の観点からの量子コンピューティングの性質の初歩的な理解を読者が得るのに役立つと考えている。
関連論文リスト
- Polynomial-depth quantum algorithm for computing matrix determinant [49.494595696663524]
正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。
行列の各行は、ある量子系の純粋な状態として符号化される。
したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
論文 参考訳(メタデータ) (2024-01-29T23:23:27Z) - Fourier expansion in variational quantum algorithms [1.4732811715354455]
定数ゲートはクリフォードゲートであり、パラメータ化ゲートはパウリ演算子によって生成される。
我々は、すべての三角単項の係数を$mathcalO(N2m)$で有界な時間で$m$まで計算する古典的アルゴリズムを与える。
論文 参考訳(メタデータ) (2023-04-07T18:00:01Z) - Multidimensional Quantum Fourier Transformation [0.0]
本研究では, 既知のQFT回路を用いて多次元QFTの効率的な回路を導出する。
現在のハードウェアの例は、IBM量子コンピュータを備えた6量子ビットの2D-QFTで描かれている。
論文 参考訳(メタデータ) (2023-01-31T18:25:40Z) - Quantum Fourier Transform Has Small Entanglement [0.0]
量子フーリエ変換は量子ビット系に大きな絡み合いをもたらすことを示す。
低結合次元の行列積状態におけるQFTの古典的シミュレーションは、キュービット数でのみ線形であることを示す。
長さ106ドルから108ドルのデータベクトルの場合、スピードアップは桁違いに行うことができる。
論文 参考訳(メタデータ) (2022-10-16T07:04:22Z) - Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
本稿では,QFT付加回路をToffoliベースの加算器に初めて体系的に変換する。
QFT回路からゲートを近似分解する代わりに、ゲートをマージする方が効率的である。
論文 参考訳(メタデータ) (2022-09-30T02:36:42Z) - Softmax-free Linear Transformers [101.01493387683898]
視覚変換器(ViT)は、視覚知覚タスクの最先端を推し進めている。
既存の手法は理論的に欠陥があるか、視覚認識に経験的に効果がないかのいずれかである。
我々はSoftmax-Free Transformers (SOFT) のファミリーを提案する。
論文 参考訳(メタデータ) (2022-07-05T03:08:27Z) - Quantum Augmented Dual Attack [8.134961550216618]
量子ランダムアクセス(QRACM)を用いたLearning with Errors(LWE)問題に対する2重格子攻撃の量子拡張変種を提案する。
本研究の結果を文献から格子パラメータに適用すると,QRACMへのユニットコストアクセスを前提として,我々のアルゴリズムが従来のアルゴリズムより優れていることが分かる。
論文 参考訳(メタデータ) (2022-05-27T13:54:31Z) - A quantum Fourier transform (QFT) based note detection algorithm [0.0]
量子情報処理において、量子変換(QFT)は多くの応用がある。
シミュレーションと実量子コンピュータの両方で量子音符検出アルゴリズムを作成する。
論文 参考訳(メタデータ) (2022-04-25T16:45:56Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。
これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
論文 参考訳(メタデータ) (2022-02-10T08:12:20Z) - SOFT: Softmax-free Transformer with Linear Complexity [112.9754491864247]
視覚変換器(ViT)は、パッチワイド画像トークン化と自己認識によって、様々な視覚認識タスクの最先端を推し進めている。
線形複雑度で自己注意を近似する様々な試みが自然言語処理で行われている。
これらの制限は、近似中にソフトマックスの自己注意を維持することに根ざしている。
ソフトマックスフリー変圧器(SOFT)を初めて提案する。
論文 参考訳(メタデータ) (2021-10-22T17:57:29Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。