論文の概要: Database Reordering for Compact Grover Oracles with ESOP Minimization
- arxiv url: http://arxiv.org/abs/2604.06578v1
- Date: Wed, 08 Apr 2026 02:02:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-09 17:30:51.295225
- Title: Database Reordering for Compact Grover Oracles with ESOP Minimization
- Title（参考訳）: ESOP最小化による小型Grover Oracleのデータベースリオーダ
- Authors: Yusuke Kimura, Yutaka Takita,
- Abstract要約: グロバーのアルゴリズムは、構造化されていないデータベースで望ましい条件を満たすデータを探索する。
繰り返し適用されるグローバーオラクル回路内では、量子状態準備回路は大きなゲート数と回路深さに悩まされる。
本稿では,データベースの並べ替えによる量子状態生成回路の削減を提案する。
- 参考スコア（独自算出の注目度）: 0.6875312133832079
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Grover's algorithm searches for data satisfying a desired condition in an unstructured database. This algorithm can search a space of size $N$ in $\sqrt{N}$ queries, thereby achieving a quadratic speedup. However, within the Grover oracle circuit that is repeatedly applied, the quantum state preparation circuit -- which embeds database information into quantum states -- suffers from a large gate count and circuit depth. To address this problem, we propose reducing the quantum state preparation circuit by reordering the database. Specifically, we consider a Quantum Read-Only Memory (QROM), where data are assigned to addresses, and assume that the address assignment of data can be freely permuted. By applying Exclusive Sum-of-Products (ESOP) minimization to the resulting truth table, we reduce the quantum circuit. Although the resulting circuit logic differs from the original, the state preparation remains correct in the sense that every desired datum is encoded at some address. Furthermore, we propose a proxy metric that estimates circuit size without compilation, and combine it with simulated annealing to efficiently find a near-optimal data ordering. In our experiments, an exhaustive search over all orderings for databases of size $N=8$ reveals that circuit size varies by up to approximately a factor of two depending on the ordering, demonstrating the utility of reordering. Compared with applying ESOP minimization without reordering, simulated annealing reduces the circuit size by approximately 30\% and yields circuits close to optimal. For $N=64$ and $128$, simulated annealing is shown to discover smaller circuits compared with random search.
- Abstract（参考訳）: グロバーのアルゴリズムは、構造化されていないデータベースで望ましい条件を満たすデータを探索する。
このアルゴリズムは、$N$ in $\sqrt{N}$クエリの空間を探索し、二次的なスピードアップを達成する。
しかし、繰り返し適用されるグローバーオラクル回路では、データベース情報を量子状態に埋め込む量子状態準備回路は、大きなゲート数と回路深さに悩まされている。
この問題に対処するため、データベースを並べ替えることにより量子状態準備回路の削減を提案する。
具体的には、アドレスにデータが割り当てられる量子読み取りオンリーメモリ(QROM)について検討し、データのアドレス割り当てを自由に変更できると仮定する。
結果の真理表に排他的Sum-of-Products(ESOP)最小化を適用することにより、量子回路を小さくする。
結果の回路論理は元の論理と異なるが、状態の準備は、任意のアドレスで全ての所望のダタムが符号化されるという意味では正しいままである。
さらに、回路サイズをコンパイルせずに推定し、それを擬似アニーリングと組み合わせて、ほぼ最適なデータ順序付けを効率的に見つけるプロキシメトリックを提案する。
実験の結果,N=8$のデータベースを網羅的に探索した結果,回路サイズは順序によって最大で2倍程度に変化することがわかった。
ESOPの最小化を並べ替えることなく適用した場合と比較して、シミュレートされたアニールは回路サイズを約30倍減らし、回路を最適に近いものにする。
N=64$と128$の場合、擬似アニールはランダムサーチに比べて小さな回路を発見する。
関連論文リスト
- A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
分散量子最適化のための構造認識フレームワークを提案する。
検索スペースが$N$の場合、我々のフレームワークはプロセッサやセパレータに依存した要素に対して$O(sqrtN)$クエリ複雑性を達成する。
構造を考慮した分解は、量子ネットワーク上でのスケーラブルな分散量子最適化に実践的な道をもたらすことを示す。
論文 参考訳（メタデータ） (2026-03-08T15:15:52Z) - Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
我々は、イオントラップハードウェアに存在するGlobal Molmer-Sorensenゲートのようなグローバルな相互作用を用いて量子回路を最適化し、合成する。
このアルゴリズムはZX計算に基づいており、係留ゲートをGlobal MolmerSorensenゲートにグループ化する特別な回路抽出ルーチンを使用する。
我々は,このアルゴリズムを様々な回路でベンチマークし,最新ハードウェアによる性能向上の方法を示す。
論文 参考訳（メタデータ） (2025-07-28T10:25:31Z) - Structured search algorithm: A quantum leap [0.0]
本稿では、絡み合いマップと固定点法を利用して、非分類データセットにおけるオラクルクエリの複雑さを最小化する構造化量子探索アルゴリズムを提案する。
IBM Kyivハードウェアの実験結果は、最大5TBの非分類データを持つデータセットでの検索が成功したことを実証している。
論文 参考訳（メタデータ） (2025-04-04T13:16:53Z) - Data Complexity Measures for Quantum Circuits Architecture Recommendation [55.74527632797241]
量子パラメトリック回路は、量子回路のサイズを減らす代替として構築される。
与えられた問題の最適回路を決定することは 未解決の問題です
本研究では,分類問題に対する量子回路レコメンデーションアーキテクチャを,データベースの複雑性尺度を用いて提案する。
論文 参考訳（メタデータ） (2025-02-21T01:17:24Z) - A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
量子格子ボルツマン法(QLBM)における非圧縮性ナビエ-ストークス方程式の多重回路アルゴリズムを提案する。
提案法は2次元蓋駆動キャビティフローに対して検証および実証を行った。
論文 参考訳（メタデータ） (2024-01-20T15:32:01Z) - Quantum algorithm for finding minimum values in a Quantum Random Access
Memory [0.0]
最適古典的決定論的アルゴリズムは、データベース内の要素数と線形に増加する時間複雑性で最小値を見つけることができる。
本稿では,データベースの最小値を求める量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-12T16:22:17Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。
我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
論文 参考訳（メタデータ） (2022-01-27T13:16:30Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z) - A polynomial size model with implicit SWAP gate counting for exact qubit
reordering [0.0]
量子回路設計者は、量子ビットの相互作用距離の制限によって生じる制約に従わなければならない。
線形アレイ上での最も近い近傍コンプライアンス問題について検討し、必要なSWAPゲートの個数を最小化する。
論文 参考訳（メタデータ） (2020-09-18T11:06:19Z) - Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
本稿では量子回路マッピングQXXとその機械学習バージョンQXX-MLPを紹介する。
後者は、レイアウトされた回路の深さが小さくなるように最適なQXXパラメータ値を自動的に推論する。
近似を用いてレイアウト法を学習可能な経験的証拠を提示する。
論文 参考訳（メタデータ） (2020-07-29T05:26:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。