論文の概要: Maximum Independent Set via Probabilistic and Quantum Cellular Automata

• arxiv url: http://arxiv.org/abs/2512.06778v1
• Date: Sun, 07 Dec 2025 10:33:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-09 22:03:54.521038
• Title: Maximum Independent Set via Probabilistic and Quantum Cellular Automata
• Title（参考訳）: 確率・量子セルオートマタによる最大独立セット
• Authors: Federico Dell'Anna, Matteo Grotti, Vito Giardinelli,
• Abstract要約: まず、動的にシステムを最大独立集合の多様体に向けて駆動する同期PCAを紹介する。 この振る舞いを動機として、純散逸相と制約保存ユニタリ進化を組み合わせたQCAを構築する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study probabilistic cellular automata (PCA) and quantum cellular automata (QCA) as frameworks for solving the Maximum Independent Set (MIS) problem. We first introduce a synchronous PCA whose dynamics drives the system toward the manifold of maximal independent sets. Numerical evidence shows that the MIS convergence probability increases significantly as the activation probability p tends to 1, and we characterize how the steps required to reach the absorbing state scale with system size and graph connectivity. Motivated by this behavior, we construct a QCA combining a pure dissipative phase with a constraint-preserving unitary evolution that redistributes probability within this manifold. Tensor Network simulations reveal that repeated dissipative--unitary cycles concentrate population on MIS configurations. We also provide an empirical estimate of how the convergence time scales with graph size, suggesting that QCA dynamics can provide an efficient alternative to adiabatic and variational quantum optimization methods based exclusively on local and translationally invariant rules.
• Abstract（参考訳）: 我々は、最大独立セット(MIS)問題を解決するためのフレームワークとして、確率的セルオートマトン(PCA)と量子セルオートマトン(QCA)について検討する。 まず、動的にシステムを最大独立集合の多様体に向けて駆動する同期PCAを紹介する。 数値的なエビデンスにより、MIS収束確率は活性化確率pが1に傾向するにつれて著しく増加し、吸収状態のスケールに達するために必要なステップがシステムサイズとグラフ接続性によってどのように特徴づけられるかが示される。 この振る舞いにより、この多様体内の確率を再分配する制約保存ユニタリ進化と純粋散逸相を組み合わせたQCAを構築する。 テンソルネットワークシミュレーションにより、繰り返し散逸する単位サイクルがMIS構成に集中していることが明らかになった。 また,グラフサイズとともに収束時間がどのようにスケールするかを実証的に推定し,局所的および翻訳的不変規則のみに基づく,断熱的および変分的量子最適化手法の効率的な代替となることを示唆する。

関連論文リスト

• Tractable Infinite-Horizon Stochastic Model Predictive Control for Quantum Filtering via Eigenstate Reduction [8.368020865178844]
  本研究では,有限次元量子システムのためのトラクタブルモデル予測制御フレームワークを提案する。 オンラインSMPCステップでは,フィルタの決定論的伝播と終端忠実度評価が要求される。 等価性と平均二乗安定性の保証を確立し,マルチレベルおよびIsing型システムに対するアプローチを検証する。
  論文  参考訳（メタデータ） (2025-11-08T08:25:48Z)
• Free Probability in a Minimal Quantum Circuit Model [0.0]
  量子力学の最小回路モデルにおける高次外乱相関器(OTOC)のダイナミクスについて検討する。 我々は、高次OTOCの指数的崩壊を証明し、関連する時間スケールを完全に特徴づける。 このアプローチと関連する影響行列は、より一般的な設定で適用されることが期待される。
  論文  参考訳（メタデータ） (2025-06-12T18:00:11Z)
• Scaling of Stochastic Normalizing Flows in $\mathrm{SU}(3)$ lattice gauge theory [44.99833362998488]
  非平衡マルコフ連鎖モンテカルロシミュレーションは、ターゲット確率分布からのサンプルに対するジャージンスキーの等式に基づくよく理解されたフレームワークを提供する。 平衡外進化はフローベースアプローチの同じ枠組みを共有しており、自然に正規化フロー(SNF)と呼ばれる新しいアーキテクチャに結合することができる。 4次元における$mathrmSU(3)$の格子ゲージ理論に対するSNFの最初の実装は、非平衡モンテカルロ更新の間にゲージ同変層を導入することで定義される。
  論文  参考訳（メタデータ） (2024-11-29T19:01:05Z)
• Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution [44.99833362998488]
  量子系を古典的にシミュレートするためのモンテカルロ変分法(英語版)の精度とサンプルの複雑さを解析する。 時間依存変分モンテカルロ(tVMC)が最もよく用いられるスキームは、体系的な統計的バイアスによって影響を受けることを証明している。 本稿では,各段階における最適化問題の解法に基づく異なるスキームが,そのような問題から解放されていることを示す。
  論文  参考訳（メタデータ） (2023-05-23T17:38:10Z)
• A self-consistent field approach for the variational quantum eigensolver: orbital optimization goes adaptive [52.77024349608834]
  適応微分組立問題集合型アンザッツ変分固有解法(ADAPTVQE)における自己一貫したフィールドアプローチ(SCF)を提案する。 このフレームワークは、短期量子コンピュータ上の化学系の効率的な量子シミュレーションに使用される。
  論文  参考訳（メタデータ） (2022-12-21T23:15:17Z)
• Directed percolation in non-unitary quantum cellular automata [0.0]
  ドマニ・キンツェルセルオートマトンを一般化する非単位量子セルオートマトンを構築する。 テンソルネットワークiTEBDアルゴリズムを用いて数値シミュレーションにより結果の動的進化について検討する。
  論文  参考訳（メタデータ） (2021-05-04T10:10:16Z)
• Quantum Markov Chain Monte Carlo with Digital Dissipative Dynamics on Quantum Computers [52.77024349608834]
  少数のアンシラ量子ビットを用いて環境との相互作用をシミュレートするデジタル量子アルゴリズムを開発した。 逆イジングモデルの熱状態のシミュレーションによるアルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2021-03-04T18:21:00Z)
• Towards quantum simulation of Sachdev-Ye-Kitaev model [5.931069258860319]
  我々は,Sachdev-Ye-Kitaevモデル(SYK)の簡易バージョンについて,正確な対角化による実相互作用について検討した。 分離分離を増加させることで、カオス状態から可積分状態への量子相転移が観察される。
  論文  参考訳（メタデータ） (2020-03-03T14:18:07Z)

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

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