論文の概要: Magic in Grover's Algorithm and the Role of Oracle Synthesis
- arxiv url: http://arxiv.org/abs/2610.37772v1
- Date: Tue, 27 Oct 2026 18:00:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-03 19:48:12.803854
- Title: Magic in Grover's Algorithm and the Role of Oracle Synthesis
- Title（参考訳）: GroverのアルゴリズムにおけるマジックとOracle合成の役割
- Abstract要約: グロバーのアルゴリズムは量子優位性の教科書の例である。
我々はGroverのプロトコルを通じて開発された非安定化性(マジック)を特徴付ける。
- 参考スコア（独自算出の注目度）: 0.22917707112773592
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Grover's algorithm is a textbook example of quantum advantage, providing a quadratic query speedup over classical methods for unstructured search. In this Letter, we characterize the non-stabilizerness, or magic, developed throughout Grover's protocol, quantifying quantum complexity with respect to the efficiently simulable stabilizer states. First, we compute the compilation-independent magic at the end of each Grover iteration, deriving an analytic prediction for the stabilizer Rényi entropy and proving that it remains intensive as the system size grows. We then investigate the magic overhead due to decomposing the circuit into elementary gates. When the solution to the search problem is known, we show that an efficient decomposition exists that keeps magic bounded despite using an extensive number of Toffoli gates. In contrast, agnostic implementations are expected to generate volume-law non-stabilizerness, as we confirm for the 3-SAT problem, which rules out efficient simulation by stabilizer-based methods in practically relevant cases. Our findings clarify the growth of magic in Grover's algorithm and the role of solution-awareness in its circuit compilation.
- Abstract（参考訳）: グロバーのアルゴリズムは量子優位性の教科書の例であり、非構造化探索の古典的な方法よりも2次的なクエリ高速化を提供する。
このレターでは、Groverのプロトコルを通じて開発された非安定化器性(マジック)を特徴付け、効率よくシミュレート可能な安定化器状態に関する量子複雑性を定量化する。
まず、各Grover反復の最後にコンパイル非依存のマジックを計算し、安定化器のレニイエントロピーの解析的予測を導出し、システムサイズが大きくなるにつれてそれが集中的であることを証明した。
次に,回路を基本ゲートに分解してマジックオーバヘッドを解析する。
探索問題に対する解が分かっていれば,多数のトフォリゲートを用いても魔法を束縛する効率的な分解が存在することを示す。
これとは対照的に,本研究では,安定化器をベースとした手法による効率的なシミュレーションを行う3SAT問題について,容積的非安定化器性を生成することが期待されている。
本研究は,Groverのアルゴリズムにおけるマジックの成長と回路コンパイルにおける解認識の役割を明らかにするものである。
関連論文リスト
- Grover Adaptive Search with Problem-Specific State Preparation [0.0345923194452408]
我々は,バッテッチとエーデンベンツの以前の研究に基づいて,旅行販売問題のための国家準備ルーチンを構築した。
イテレーションでは、数回のイテレーションだけで妥当な近似比を達成することを目指しています。
論文 参考訳（メタデータ） (2026-02-09T09:21:04Z) - Function Recovery Attacks in Gate-Hiding Garbled Circuits using SAT Solving [18.958044099636982]
半原始関数評価は、入力データと関数ロジックの両方を保護しながら、共同計算を可能にする。
本研究では,現実的な計算能力を捉える2つの逆モデルの下で,ゲート隠蔽の実証的安全性を解析する。
本稿では,回路のパブリックトポロジから隠れゲート操作を再構築するSATベースの機能回復攻撃を提案する。
論文 参考訳（メタデータ） (2026-01-19T18:15:12Z) - A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization [39.146761527401424]
この研究は、測定駆動量子SATソルバの厳密な最悪の実行時解析を示す。
この量子アルゴリズムはGrover型法にのみ依存せず,有望な数値性能を示す。
また,複数のタスクを満足するインスタンスに対しても,効率的に解を見つける新しい読み出しルーチンを開発した。
論文 参考訳（メタデータ） (2025-11-12T19:00:13Z) - Average-Case Complexity of Quantum Stabilizer Decoding [42.770940323689445]
1つの論理量子ビットでさえも、ランダムな安定化符号を復号化することは、ランダムな古典符号を一定速度で復号化することと同じくらい難しいことを証明している。
この結果は、最も簡単なランダム量子復号問題は、少なくとも最も難しいランダム古典復号問題と同じくらい難しいことを示唆している。
論文 参考訳（メタデータ） (2025-09-25T03:04:40Z) - Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。
結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
論文 参考訳（メタデータ） (2025-08-04T16:44:53Z) - A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search [0.0]
本稿では、パスフィニングタスクを構造化探索問題としてキャストすることで、完璧な迷路を解くための量子アルゴリズムを提案する。
グロバーの振幅増幅に基づいて、アルゴリズムは重ね合わせ中の全ての候補経路を符号化し、その目標に近接することを評価する。
グロバー互換のオラクルは、高い適合状態を示し、適応的なカットオフ戦略は、探索を反復的に洗練する。
論文 参考訳（メタデータ） (2025-07-29T15:51:19Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z) - Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。
各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
論文 参考訳（メタデータ） (2020-09-11T17:31:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。