論文の概要: Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms

• arxiv url: http://arxiv.org/abs/2606.14226v1
• Date: Fri, 12 Jun 2026 08:06:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-15 16:00:42.814577
• Title: Efficient Simulation of Szegedy Quantum Walk Formulations and Algorithms
• Title（参考訳）: 疑似量子ウォーク定式化とアルゴリズムの効率的なシミュレーション
• Authors: Sergio A. Ortega, Daniel K. Park,
• Abstract要約: 量子ウォークは、幅広いアプリケーションにわたる量子アルゴリズムのための汎用的なフレームワークを提供する。 本研究では,Szegedy量子ウォークの高速な古典的シミュレーション手法を開発し,完全ユニタリ進化演算子の明示的な構成を回避する。 我々はこれらの手法を、大きなスパースグラフに適した実装を含むウォークに結合した位相推定に基づくアルゴリズムに拡張する。
• 参考スコア（独自算出の注目度）: 0.21485350418225238
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum walks provide a versatile framework for quantum algorithms across a wide range of applications. We develop efficient classical simulation methods for Szegedy quantum walks that avoid explicit construction of the full unitary evolution operator. Unlike previous approaches restricted to a particular walk formulation, our framework is built from fundamental update and reflection operators, enabling the simulation of a broader class of Szegedy walk formulations. We further extend these methods to phase-estimation-based algorithms coupled to the walk, including implementations suitable for large sparse graphs. The resulting methods achieve optimal $O(N^2)$ complexity for dense graphs with $N$ nodes. For sparse graphs, the computational cost scales linearly with the number of edges, which is $O(N)$ in many cases. We implement the framework in the Python package SQWLib and illustrate its capabilities through simulations of representative algorithms, including quantum simulated annealing and quantum search on graphs. These results provide a practical tool for studying Szegedy-walk-based algorithms numerically beyond purely analytical treatments.
• Abstract（参考訳）: 量子ウォークは、幅広いアプリケーションにわたる量子アルゴリズムのための汎用的なフレームワークを提供する。 本研究では,Szegedy量子ウォークの高速な古典的シミュレーション手法を開発し,完全ユニタリ進化演算子の明示的な構成を回避する。 従来の特定の歩行定式化に制限されたアプローチとは異なり、我々のフレームワークは基本的な更新演算子とリフレクション演算子から構築されており、より広範なSzegedy歩行定式化のシミュレーションを可能にする。 我々はこれらの手法をさらに、大きなスパースグラフに適した実装を含む、ウォークに結合した位相推定に基づくアルゴリズムに拡張する。 得られた方法は、$N$ノードを持つ高密度グラフに対して最適な$O(N^2)$複雑性を達成する。 スパースグラフの場合、計算コストはエッジの数とともに線形にスケールし、多くの場合は$O(N)$である。 我々は,PythonパッケージSQWLibにこのフレームワークを実装し,量子シミュレーションアニーリングやグラフ上の量子探索など,代表アルゴリズムのシミュレーションを通じてその機能を説明する。 これらの結果は、Szegedy-walk-based algorithm を純粋に解析的処理を越えて数値的に研究するための実用的なツールを提供する。

関連論文リスト

• Solving Linear Systems of Equations with the Quantum HHL Algorithm: A Tutorial on the Physical and Mathematical Foundations for Undergraduate Students [36.94429692322632]
  2009年、ハロー、ハシディム、ロイドは、$poly(log N)$の複雑性を持つ方程式の線形系を解くアルゴリズムを提案した。 本稿では,学部生を対象としたHHLアルゴリズムの物理・数学的基礎を論じるチュートリアルについて述べる。
  論文  参考訳（メタデータ） (2025-09-20T11:37:48Z)
• Quantum Simulation-Based Optimization of a Cooling System [0.0]
  量子アルゴリズムは、数値シミュレーションに関連する特定のタスクに対して指数的なスピードアップを約束する。 しかし、量子コンピュータのデータ入力と出力を考えると、これらの利点はすぐに消える。 最近導入されたQuantum Simulation-Based Optimization (QuSO)は、より大規模な最適化の中でシミュレーションをサブプロブレムとして扱う。
  論文  参考訳（メタデータ） (2025-04-21T21:58:21Z)
• Practical Application of the Quantum Carleman Lattice Boltzmann Method in Industrial CFD Simulations [44.99833362998488]
  この研究は、格子ボルツマン法(LBM)に基づくCFDへのハイブリッド量子古典的アプローチの実用的な数値評価を提示する。 本手法は, 異なる境界条件, 周期性, バウンスバック, 移動壁を有する3つのベンチマークケースで評価した。 提案手法の有効性を検証し,10～3ドル程度の誤差忠実度と,実際の量子状態サンプリングに十分な確率を達成できた。
  論文  参考訳（メタデータ） (2025-04-17T15:41:48Z)
• 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)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• 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)
• Variational Quantum Algorithms for Semidefinite Programming [3.481985817302898]
  半定値プログラム(SDP)は、操作研究、最適化、量子情報科学などにおける凸最適化問題である。 本稿では,SDPを近似的に解くための変分量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-16T13:10:48Z)

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

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