論文の概要: Fast quantum integer multiplication with zero ancillas

• arxiv url: http://arxiv.org/abs/2403.18006v4
• Date: Thu, 14 Nov 2024 17:31:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-15 15:22:01.723709
• Title: Fast quantum integer multiplication with zero ancillas
• Title（参考訳）: 零アンシラによる高速量子整数乗算
• Authors: Gregory D. Kahanamoku-Meyer, Norman Y. Yao,
• Abstract要約: 我々は,ゼロアンシラ量子ビットを用いた準四進時間量子乗法の新しいパラダイムを導入する。 関連するキュービットは入力と出力レジスタ自身のみである。 我々のアルゴリズムは、実際的な問題の大きさよりも優れている可能性がある。
• 参考スコア（独自算出の注目度）: 0.5755004576310334
• License:
• Abstract: The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of $\mathcal{O}(n^{1+\epsilon})$ for any $\epsilon > 0$; with practical choices of parameters, we expect scalings as low as $\mathcal{O}(n^{1.3})$. Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with $\mathcal{O}(n^{2+\epsilon})$ gates and only $2n + \mathcal{O}(\log n)$ qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is $\mathcal{O}(n^{1.5+\epsilon})$. Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.
• Abstract（参考訳）: 数値の重ね合わせの乗法は、多くの量子アルゴリズムのコア演算である。 乗算の標準的な方法(古典と量子の両方)は、入力のサイズが2次である。 漸近的に少ないゲートを持つ量子回路が開発されたが、一般的には大きなオーバーヘッド、特にアンシラ量子ビットの数を示す。 本研究では,0個のアンシラ量子ビットを持つ準四進時間量子乗算のための新しいパラダイムを導入する。 我々のアルゴリズムは、任意の$\epsilon > 0$に対して$\mathcal{O}(n^{1+\epsilon})$の漸近ゲート数を達成する。 Shorのアルゴリズムのサブルーチンとして使われ、我々の手法は直ちに$\mathcal{O}(n^{2+\epsilon})$ Gatesと$2n + \mathcal{O}(\log n)$ qubitsのファクタリング回路を得る。 Regevの最近のファクタリングアルゴリズムで使用されるゲートカウントは$\mathcal{O}(n^{1.5+\epsilon})$である。 最後に、我々のアルゴリズムは、古典的に検証可能な量子上の優位性のために、我々が知っている最小の回路を含む、実際に関連する問題のサイズで以前の提案を上回る可能性を実証する。

関連論文リスト

• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth [8.938538037322381]
  本稿では、古典的硬さがRSAと同値であると期待されているものを含む、整数の大規模なクラスを分解する小型量子回路を提案する。 我々の知る限り、古典的にハードなファクタリング問題に対して、サブ線形量子ビットカウントを達成した初めてのMod-time回路である。 We build on the quantum algorithm found by Li, Peng, Du and Suter (Nature Scientific Reports 2012) which instead on computing the Jacobi symbol in quantum superposition。
  論文  参考訳（メタデータ） (2024-12-17T05:34:54Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT回路は一般的な量子回路の共通構成ブロックである。 本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。 シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
  論文  参考訳（メタデータ） (2024-08-07T19:51:22Z)
• Lower $T$-count with faster algorithms [3.129187821625805]
  低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。 様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。 我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
  論文  参考訳（メタデータ） (2024-07-11T17:31:20Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  そこで我々は,行列式と逆行列の計算に$(N-1)倍 (N-1)$行列を求める量子アルゴリズムを提案する。 このアプローチは、N×N$行列の行列式を決定するための既存のアルゴリズムの簡単な修正である。 3つのアルゴリズムすべてに対して適切な回路設計を提供し、それぞれが空間的に$O(N log N)$と見積もられている。
  論文  参考訳（メタデータ） (2024-01-29T23:23:27Z)
• An Efficient Quantum Factoring Algorithm [0.27195102129094995]
  我々は、$tildeO(n3/2)$の量子回路を独立に実行することで、$n$bit整数を分解できることを示した。 アルゴリズムの正しさは、指数的古典的因数分解アルゴリズムで使われるものに似た数論的な仮定に依存する。
  論文  参考訳（メタデータ） (2023-08-12T13:57:38Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• CNOT-count optimized quantum circuit of the Shor's algorithm [8.88308897530269]
  整数分解のためのShorアルゴリズムにおいて最も高価な演算である定数のモジュラー指数化のための改良された量子回路を提案する。 CNOTゲートの数に応じて、イオントラップ量子コンピュータ上でShorのアルゴリズムの実行時間と実現可能性を分析する。
  論文  参考訳（メタデータ） (2021-12-21T16:56:22Z)
• Low-depth Quantum State Preparation [3.540171881768714]
  量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。 ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。 我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
  論文  参考訳（メタデータ） (2021-02-15T13:11:43Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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