論文の概要: 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})$である。 最後に、我々のアルゴリズムは、古典的に検証可能な量子上の優位性のために、我々が知っている最小の回路を含む、実際に関連する問題のサイズで以前の提案を上回る可能性を実証する。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT回路は一般的な量子回路の共通構成ブロックである。 本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。 シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
  論文  参考訳（メタデータ） (2024-08-07T19:51:22Z)
• Quantum hashing algorithm implementation [0.0]
  我々は1988年にAmbainisとFreevaldsが発表したフィンガープリント技術に基づく量子ハッシュアルゴリズムをゲートベース量子コンピュータ上で実装した。 我々は,LNN(Linear Nearest Neighbor)ではない隣接アーキテクチャを表すキュービットの特殊グラフを持つ16量子および27量子のIBMQを考察する。
  論文  参考訳（メタデータ） (2024-07-14T09:41:16Z)
• 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)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  CFD問題を解決するための現在の量子アルゴリズムは、単一の量子回路と、場合によっては格子ベースの方法を用いる。 量子格子ボルツマン法(QLBM)を用いた新しい多重回路アルゴリズムを提案する。 この問題は2次元ナビエ・ストークス方程式の流動関数-渦性定式化として鋳造され、2次元蓋駆動キャビティフローで検証および試験された。
  論文  参考訳（メタデータ） (2024-01-20T15:32:01Z)
• 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)

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

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