論文の概要: Fast quantum integer multiplication with zero ancillas
- arxiv url: http://arxiv.org/abs/2403.18006v1
- Date: Tue, 26 Mar 2024 18:00:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-28 21:24:43.325306
- Title: Fast quantum integer multiplication with zero ancillas
- Title(参考訳): 零アンシラによる高速量子整数乗算
- Authors: Gregory D. Kahanamoku-Meyer, Norman Y. Yao,
- Abstract要約: 我々は,ゼロアンシラ量子ビットを用いた準四進時間量子乗法の新しいパラダイムを導入する。
関連するキュービットは入力と出力レジスタ自身のみである。
我々のアルゴリズムは、実際的な問題の大きさよりも優れている可能性がある。
- 参考スコア(独自算出の注目度): 0.5755004576310334
- License: http://creativecommons.org/licenses/by/4.0/
- 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})$である。
最後に、我々のアルゴリズムは、古典的に検証可能な量子上の優位性のために、我々が知っている最小の回路を含む、実際に関連する問題のサイズで以前の提案を上回る可能性を実証する。
関連論文リスト
- 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) - Space-Efficient and Noise-Robust Quantum Factoring [12.964984355658995]
我々はRegevの最近の量子ファクタリングアルゴリズム(arXiv:2308.06572)を改善する。
我々は独立に$approx sqrtn$ timesを実行し、Regevの古典的な後処理手順を適用する。
第二の貢献は、レゲフの古典的な後処理手順が量子回路の一定の部分の誤りを許容するために修正可能であることを示すことである。
論文 参考訳(メタデータ) (2023-10-02T04:31:21Z) - An Efficient Quantum Factoring Algorithm [0.27195102129094995]
我々は、$tildeO(n3/2)$の量子回路を独立に実行することで、$n$bit整数を分解できることを示した。
アルゴリズムの正しさは、指数的古典的因数分解アルゴリズムで使われるものに似た数論的な仮定に依存する。
論文 参考訳(メタデータ) (2023-08-12T13:57:38Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - Asymptotically optimal synthesis of reversible circuits [36.53047196916995]
可逆回路は 学術界から注目を集めています
Omega (2n n/log n)$で、約20年間、$n$-wireの可逆回路の合成が提案されている。
我々は,O(2n n/log n)$小ゲートを含まない任意の$n$ワイヤ可逆回路を実装する手順を提案する。
論文 参考訳(メタデータ) (2023-02-13T03:08:55Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - Calculable lower bounds on the efficiency of universal sets of quantum
gates [0.0]
現在利用可能な量子コンピュータ、いわゆるNoisy Intermediate-Scale Quantum (NISQ) は、比較的少ない量子ビットと適度なゲートフィデリティによって特徴づけられる。
本稿では、$mathrmgap_r(mathcalS)$ 上の下界を導出し、その結果、$d$次元量子ゲートの普遍集合の効率について述べる。
論文 参考訳(メタデータ) (2022-01-27T19:38:13Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。