論文の概要: A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint

• arxiv url: http://arxiv.org/abs/2508.07007v1
• Date: Sat, 09 Aug 2025 14:59:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-12 21:23:28.650474
• Title: A Quantum Walk-Driven Algorithm for the Minimum Spanning Tree Problem under a Maximal Degree Constraint
• Title（参考訳）: 最大Degree制約下での最小スパンニング木問題に対する量子ウォーク駆動アルゴリズム
• Authors: F. S. Luiz, F. F. Fanchini, Victor Hugo C. de Albuquerque, J. P. Papa, M. C. de Oliveira,
• Abstract要約: 我々は、最小スパンニングツリー(MST)問題を最大度制約(MDC)の下で解くための新しい量子ウォークに基づくアプローチを提案する。 量子進化は, 累積遷移確率(すなわちシャノンエントロピー)を最大化することにより, MSTを自然選択することを示した。 MDCを用いたQuantum Kruskalと呼ばれるこの手法は、競合する古典的な計算複雑性を維持しながら、量子リソースの要求を$mathcalO(log N)$ qubitsに大幅に削減する。
• 参考スコア（独自算出の注目度）: 9.382719568546758
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel quantum walk-based approach to solve the Minimum Spanning Tree (MST) problem under a maximal degree constraint (MDC). By recasting the classical MST problem as a quantum walk on a graph, where vertices are encoded as quantum states and edge weights are inverted to define a modified Hamiltonian, we demonstrate that the quantum evolution naturally selects the MST by maximizing the cumulative transition probability (and thus the Shannon entropy) over the spanning tree. Our method, termed Quantum Kruskal with MDC, significantly reduces the quantum resource requirement to $\mathcal{O}(\log N)$ qubits while retaining a competitive classical computational complexity. Numerical experiments on fully connected graphs up to $10^4$ vertices confirm that, particularly for MDC values exceeding $4$, the algorithm delivers MSTs with optimal or near-optimal total weights. When MDC values are less or equal to $4$, some instances achieve a suboptimal solution, still outperforming several established classical algorithms. These results open promising perspectives for hybrid quantum-classical solutions in large-scale graph optimization.
• Abstract（参考訳）: 我々は,最小スパンニングツリー(MST)問題を最大度制約(MDC)の下で解くための,新しい量子ウォークに基づくアプローチを提案する。 古典的MST問題を量子ウォークとして再キャストすることにより、頂点を量子状態としてエンコードし、エッジウェイトを逆転してハミルトン多様体を定義することにより、量子進化は、スパンニングツリー上の累積遷移確率(すなわちシャノンエントロピー)を最大化することによって、MSTを自然に選択することを示した。 MDCを用いたQuantum Kruskalと呼ばれるこの手法は、競合する古典的な計算複雑性を維持しながら、量子リソースの要求を$\mathcal{O}(\log N)$ qubitsに大幅に削減する。 完全連結グラフの10^4$頂点に関する数値実験により、特にMSC値が4$を超える場合、このアルゴリズムは最適あるいは最適に近い総重量でMSTを配信することを確認した。 MDC値が4ドル以下である場合、いくつかのインスタンスは、いくつかの確立された古典的アルゴリズムよりも優れた最適解が得られる。 これらの結果は、大規模グラフ最適化におけるハイブリッド量子古典解に対する有望な視点を開放する。

関連論文リスト

• Second order cone relaxations for quantum Max Cut [3.237380113935023]
  量子マックスカット(Quantum Max Cut、QMC)は、量子多体物理学と計算機科学に関連するQMA完全問題である。 我々はQMCに対して2次円錐緩和を与えるが、これは相互に一貫した3量子化密度行列の集合を最適化する。 我々の緩和は数百の量子ビットを持つ系で解決可能であり、大規模量子スピン系の基底状態エネルギー上の下界と上界を計算的に効率的に計算する方法を舗装する。
  論文  参考訳（メタデータ） (2024-11-06T18:54:26Z)
• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Alleviating the quantum Big-$M$ problem [0.22615818641180715]
  古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。 我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。 本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-19T18:00:05Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。 目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
  論文  参考訳（メタデータ） (2023-05-23T16:17:57Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)

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

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