論文の概要: Halving the cost of QROM

• arxiv url: http://arxiv.org/abs/2605.20334v1
• Date: Tue, 19 May 2026 18:00:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 19:19:56.301767
• Title: Halving the cost of QROM
• Title（参考訳）: QROMのコスト削減
• Authors: Danial Motlagh, Matthew Pocrnic,
• Abstract要約: テーブルルックアップ(英: Table lookup、しばしば量子読み取り専用メモリ(QROM)と呼ばれる)は、量子アルゴリズムにおいて最も広く用いられるサブルーチンの1つである。 これは、重ね合わせで$N$ビットストリングの長さ$b$のコヒーレントロードを含む。 $b, $ dirty qubits にアクセスすると、QROM の Toffoli コストを $2fracN + 4b(- 1)$ に下げることができることが知られている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Table lookup, often referred to as quantum read only memory (QROM), is one of the most widely used subroutines in quantum algorithms, and constitutes the majority share of algorithmic overheads in most practical applications of quantum computers. It involves the coherent loading of $N$ bitstrings of length $b$ in superposition, and naively has a non-Clifford cost of $N$ Toffolis. It is known that given access to $b\, λ$ dirty qubits, one can reduce the Toffoli cost of QROM to $2\frac{N}λ + 4b(λ- 1)$. In this work, we first present an optimization to reduce this cost to $2\frac{N}λ + 2b(λ- 1) + 2λ-6$ by replacing the ``SelectSwap" architecture with ``SelectCopy". We then provide a further optimization for the qubit-constrained regime where the Toffoli cost is typically $\sim 2\frac{N}λ$, and reduce it to $\sim (1+\frac{1}{b})\frac{N}λ$, cutting the cost by approximately $50\%$ and effectively matching the performance of clean-qubit QROM using dirty qubits for practical values of $b$. Lastly, we provide a parametric family of methods that allow the interpolation of the prefactor of the $\frac{N}λ $ term from $2$ to ($\, 1+\frac{1}{b}\,$) to obtain the best cost for different qubit availability regimes.
• Abstract（参考訳）: テーブルルックアップ(英: Table lookup、しばしば量子読み取り専用メモリ(英: quantum read only memory、QROM)は、量子アルゴリズムにおいて最も広く使われているサブルーチンの1つである。 これは、重ね合わせで$N$ビットストリングの長さ$b$のコヒーレントロードを伴い、非クリフォードコストが$N$トフォリスである。 b\, λ$ の汚れた量子ビットへのアクセスが与えられると、QROM のトフォリコストを 2 {\displaystyle 2\frac{N}λ + 4b(λ- 1)$ に下げることができることが知られている。 本稿では,まず,このコストを2.2\frac{N}λ + 2b(λ- 1) + 2λ-6$に削減するために, ``SelectSwap'アーキテクチャを ``SelectCopy' に置き換える最適化を提案する。 次に、Toffoli のコストが $\sim 2\frac{N}λ$ で、それを $\sim (1+\frac{1}{b})\frac{N}λ$ に減らし、約50\%$ のコストを削減し、実際の$b$ の値に対して汚いqubits を用いてクリーンキュービット QROM の性能を効果的にマッチングする。 最後に、$\frac{N}λ $ termのプレファクターを$$$から$$$, 1+\frac{1}{b}\,$) に補間して、異なるキュービットアベイラビリティーレジームの最良のコストを得るためのパラメトリックな方法の族を提供する。

関連論文リスト

• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Asymptotically Optimal Quantum Amplitude Estimation by Generalized Qubitization [5.0755851789013535]
  まず、標準値が約1.28 L-1$で、$L$はクエリの数であることを示す。 次に、複数の関数を同時にブロックエンコードできる一般化量子化法を提案し、量子振幅を推定して最適な精度を達成する方法を示す。
  論文  参考訳（メタデータ） (2023-06-29T05:31:52Z)
• Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions [10.44923461503086]
  量子ランダムアクセスコード(QRAC)は、バイナリ最適化の複数の変数を1量子ビットでエンコードする。 本研究では3つの古典的ビットを2つの量子ビットにエンコードする別のQRACを用いて量子緩和を拡張する。 また,新しい量子緩和法を設計し,量子ビット間圧縮比を常に2ドル(約2,300円)で保証する。
  論文  参考訳（メタデータ） (2023-02-19T05:31:21Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation [0.0]
  ノイズの多い中間スケールの量子計算は、スパース量子コンピューティングチップ上の対数深度量子回路と見なすことができる。 このようなノイズの多い中間スケール量子計算を効率よく検証する手法を提案する。
  論文  参考訳（メタデータ） (2021-09-30T08:56:30Z)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。 本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。 我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
  論文  参考訳（メタデータ） (2021-08-13T09:47:11Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。 最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
  論文  参考訳（メタデータ） (2020-07-23T10:50:42Z)

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

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