論文の概要: 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（参考訳）: 疑似量子ウォーク定式化とアルゴリズムの効率的なシミュレーション
• 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)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Quantum-Trajectory-Inspired Lindbladian Simulation [16.17464946935405]
  リンドブラディアンズが支配するオープン量子系の力学をシミュレーションする2つの量子アルゴリズムを提案する。 最初のアルゴリズムはジャンプ演算子数とは無関係にゲート複雑性を達成し、$m$は効率を大幅に向上させる。 第二のアルゴリズムは進化時間$t$と精度$epsilon$にほぼ最適に依存し、追加の$tildeO(m)$ factorを導入する。
  論文  参考訳（メタデータ） (2024-08-20T03:08:27Z)
• 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)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。 アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
  論文  参考訳（メタデータ） (2022-11-22T18:54:48Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• The Quantum Approximate Optimization Algorithm performance with low entanglement and high circuit depth [0.0]
  変分量子アルゴリズムは、現在の雑音量子コンピュータを使用する最も広範な方法の1つである。 最適化問題の解法における絡み合いの役割について検討する。 ここでは, 絡み合いが MaxCut と Exact Cover 3 問題において軽微な役割を担っていると結論づける。
  論文  参考訳（メタデータ） (2022-07-07T16:21:36Z)
• 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)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。 一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。 幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
  論文  参考訳（メタデータ） (2021-04-01T19:06:00Z)
• Randomizing multi-product formulas for Hamiltonian simulation [2.2049183478692584]
  本稿では,一方のランダム化コンパイルの利点と他方の高次多重積公式を結合した量子シミュレーション手法を提案する。 本フレームワークは,振幅増幅を回避し,回路深度を低減させる。 本アルゴリズムは回路深さとともに指数関数的に縮小するシミュレーション誤差を実現する。
  論文  参考訳（メタデータ） (2021-01-19T19:00:23Z)

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

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