論文の概要: Improved Exact and Approximate Quantum Fourier Transforms from Multiplication

• arxiv url: http://arxiv.org/abs/2611.06341v1
• Date: Wed, 04 Nov 2026 11:02:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 03:25:58.088306
• Title: Improved Exact and Approximate Quantum Fourier Transforms from Multiplication
• Title（参考訳）: 乗算による量子フーリエ変換の精度向上と近似化
• Abstract要約: 整数乗算アルゴリズムを$O(n) (log n) で2つの$n$-bit整数を乗算する方法を示す。 これにより、$o left( q (log q)right)$ gates を持つ QFT 回路を持つ可能性が開ける。 ZZ/(2q ZZ)$を超えるQFTの近似について、Ahokas, Cleve and Hales (ERATO 2003)の結果は、$O left( q (log q)rightで近似回路を構築することができることを示した。
• 参考スコア（独自算出の注目度）: 0.06524460254566904
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the world of quantum computing, quantum Fourier transform (QFT) has been one of the most important subroutines for quantum algorithms, as exemplified by Shor's factoring algorithms and phase estimation (which in itself has been used as a primitive in various quantum algorithms). In fact most of the well known quantum algorithms can be divided into two classes, QFT based algorithms and search based algorithms. The usual circuit for QFT (covered in almost every basic quantum algorithms course) needs $O(q^2)$ gates (and $O(q)$ qubits) to perform the exact Fourier transform over $\mathbb{F}_{2^q}$. Cleve and Watrous (FOCS 2000) improved this gate count to $O(q (\log q)^2 (\log \log q))$ using the integer multiplication algorithm in $O(n (\log n) (\log \log n))$ time for two $n$-bit integers (best known at that time). Our first main result shows that this gate count can be improved to $O(q (\log q))$. In fact, if there is a multiplication circuit, to multiply two $n$-bit integers, with $O(n (\log n)^α)$ gates; we get a QFT circuit with $O(q (\log q)^α)$ gates (improving upon $O(q (\log q)^{α+ 1})$) gates from the construction of Cleve and Watrous). Given the recent claim by OpenAI about integer multiplication, this opens up the possibility of having a QFT circuit with $o \left( q (\log q)\right)$ gates. On approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that an approximating circuit can be built with $O \left( q (\log \log(q/\varepsilon))^{α+1} \right)$ gates, where $ε$ is the approximating parameter. Our second main result again improves this to $O \left( q (\log \log(q/\varepsilon))^α \right)$ gates.
• Abstract（参考訳）: 量子コンピューティングの世界では、量子フーリエ変換(QFT)は、ショアの分解アルゴリズムと位相推定(それ自身は様々な量子アルゴリズムにおいてプリミティブとして使われてきた)が示すように、量子アルゴリズムの最も重要なサブルーチンの1つである。 実際、よく知られた量子アルゴリズムのほとんどは、QFTベースのアルゴリズムと検索ベースのアルゴリズムの2つのクラスに分けられる。 QFT の通常の回路は、$O(q^2)$ gates (および$O(q)$ qubits) を必要とし、$\mathbb{F}_{2^q}$ 上で正確なフーリエ変換を実行する。 Cleve and Watrous (FOCS 2000)は、$O(q (\log q)^2 (\log \log q))$$$O(n (\log n) (\log \log n))$2$n$-bit整数の整数乗算アルゴリズムを用いて、このゲート数を$O(q (\log q)^2 (\log \log q)))$に改善した。 最初の主要な結果は、このゲートカウントを$O(q (\log q))$に改善できることを示しています。 実際、2つの$n$-bit整数に$O(n (\log n)^α)$ゲートを乗算すると、$O(q (\log q)^α)$ゲートを持つQFT回路が得られる(Cleve と Watrous の構成から$O(q (\log q)^{α+ 1})$ゲートを改良する)。 整数乗法に関するOpenAIの最近の主張を踏まえると、$o \left( q (\log q)\right)$ gates を持つ QFT 回路を持つ可能性が開ける。 The approximating the QFT over $\ZZ/(2^q \ZZ)$, the result of Ahokas, Cleve and Hales (ERATO 2003) showed that a approximating circuit can be built with $O \left( q (\log \log(q/\varepsilon))^{α+1} \right)$ gates, where $ε$ is the approximating parameter。 2つ目の結果は再び$O \left( q (\log \log(q/\varepsilon))^α \right)$ gatesに改善します。

関連論文リスト

• A Quantum Bluestein's Algorithm for Arbitrary-Size Quantum Fourier Transform [0.0]
  QBAは任意の長さの入力に対して正確な$N$ポイント離散フーリエ変換を生成する。 我々は,QBAの具体的な実装と古典シミュレーションを用いて,QBAの正当性を検証した。
  論文  参考訳（メタデータ） (2025-12-17T11:45:43Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• A Faster Quantum Fourier Transform [0.0]
  本稿では,量子フーリエ変換(QFT)を高精度かつ近似的に実装するアルゴリズムについて述べる。 量子ビットの2つの分割に再帰するQFTの新たな定式化を活用することで、これらのコストを削減することができることを示す。
  論文  参考訳（メタデータ） (2025-01-19T06:18:52Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  本稿では,一様制御ゲート実装のための2種類の定数深度構造を提案する。 我々は、リードオンリーおよびリードライトメモリデバイスの量子対数に対して、一定の深さの回路を得る。
  論文  参考訳（メタデータ） (2023-08-16T17:54:56Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Asymptotically optimal synthesis of reversible circuits [0.0]
  任意の$n$wire回路を$ (2n n/log n)$小ゲートで実装するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-13T03:08:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。