論文の概要: Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
- arxiv url: http://arxiv.org/abs/2606.28866v3
- Date: Fri, 03 Jul 2026 10:56:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-07 13:04:58.196245
- Title: Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
- Title（参考訳）: 実用性尺度における最大独立集合問題への量子変分法アプローチ
- Abstract要約: 最大独立集合(MIS)問題に対する変分量子アルゴリズムを64,99,180頂点のベンチマークグラフ上で検討する。
新しい構成により、複数のシードを同時に量子並列変動探索することができ、単一シードのメソッドが失敗する正確なMISを発見することができる。
IBM Quantumハードウェア ibm_marrakesh のハードウェア検証では、収束したシミュレータパラメータがノイズの多い量子実行に効果的に転送されることを確認した。
- 参考スコア（独自算出の注目度）: 6.404616027487662
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study variational quantum algorithms for the Maximum Independent Set (MIS) problem on benchmark graphs of 64, 99, and 180 vertices. The Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA) are compared across SPSA and COBYLA optimizers at multiple circuit depths. A preprocessing pipeline comprising spectral graph reordering (via the Fiedler vector) and distance-based sparsification reduces circuit depth while preserving energy fidelity. Classical post-processing via history-guided bitstring correction and stepwise maximality extension recovers the exact MIS across all instances. With CVaR optimization, VQE with SPSArecovers up to 6 distinct MIS per run for the 64-node instance and up to 10 distinct MIS per run for the 99-node instance, sampling broadly from the optimal solution population. Repeated runs with different SPSA trajectories collectively enumerate a larger fraction of all MIS for each instance. For the 180-node instance, where standard approaches stall at size 14 (MIS is 15), we introduce ancilla-assisted superposition initialization: ancilla qubits prepare a uniform superposition over classically-found near-optimal solutions, and an excitation-preserving ansatz evolves this state while conserving Hamming weight. This novel construction enables quantum-parallel variational search over multiple seeds simultaneously, discovering the exact MIS where single-seed methods fail. The 180-qubit simulation represents, to our knowledge, the largest scale at which gate-based variational algorithms have solved MIS to optimality. Hardware validation on IBM Quantum hardware ibm_marrakesh confirms that converged simulator parameters transfer effectively to noisy quantum execution.
- Abstract（参考訳）: 最大独立集合(MIS)問題に対する変分量子アルゴリズムを64,99,180頂点のベンチマークグラフ上で検討する。
変動量子固有解法 (VQE) と量子近似最適化アルゴリズム (QAOA) は、複数の回路深さでSPSAとCOBYLAオプティマイザ間で比較される。
スペクトルグラフの並べ替え(ファイドラーベクトルによる)と距離ベースのスペーシングを含む前処理パイプラインは、エネルギーの忠実さを保ちながら回路深さを減少させる。
履歴誘導ビットストリング補正とステップワイズ最大性拡張による古典的な後処理は、全インスタンスにわたって正確なMISを復元する。
CVaR最適化では、SPSAを使用したVQEは64ノードインスタンスで最大6つのMISを、99ノードインスタンスで最大10個のMISを、最適なソリューション人口から広範囲にサンプリングする。
異なるSPSAトラジェクトリを持つ繰り返し実行は、各インスタンスに対する全てのMISのより大きな部分の列挙を行う。
標準アプローチがサイズ14で停止する180ノードのインスタンス(MISは15)に対して、アンシラ補助的な重ね合わせ初期化を導入する: アンシラ量子ビットは古典的に見いだされた準最適解に対して均一な重ね合わせを作成し、励起保存アンサッツはハミング重みを保ちながらこの状態を進化させる。
この新しい構成により、複数のシードを同時に量子並列変動探索することができ、単一シードのメソッドが失敗する正確なMISを発見することができる。
180量子ビットシミュレーションは、我々の知る限り、ゲートベースの変分アルゴリズムがMISを最適に解いた最大の尺度である。
IBM Quantumハードウェア ibm_marrakesh のハードウェア検証では、収束したシミュレータパラメータがノイズの多い量子実行に効果的に転送されることを確認した。
関連論文リスト
- Quantum-Informed Portfolio Selection: An End-to-End Pipeline Validated on Trapped-Ion Hardware with Real Market Data [10.505676456054193]
ポートフォリオの多様化は、資産相関グラフ上の最大独立集合(MIS)問題として定式化することができる。
ハイブリッド量子古典アルゴリズムであるqReduMISを利用するエンドツーエンドパイプラインを提案する。
我々は、最大225の資産を持つ4大市場指標の実際の財務データについてqReduMISをベンチマークする。
論文 参考訳（メタデータ） (2026-07-01T15:04:48Z) - SpinGQE: A Generative Quantum Eigensolver for Spin Hamiltonians [42.007194397302825]
基底状態探索は量子コンピューティングの中心である。
我々は、生成量子固有ソルバフレームワークをスピンハミルトニアンに拡張したSpinGQEを提案する。
我々は、低エネルギー状態を生成する量子回路について学ぶために、トランスフォーマーベースのデコーダを用いる。
論文 参考訳（メタデータ） (2026-03-25T13:38:15Z) - A Depth-Independent Linear Chain Ansatz for Large-Scale Quantum Approximate Optimization [19.43182259360486]
本稿では, 線形連鎖 QAOA の変種を提案するとともに, 従来の QAOA のパラダイムである MaxCut 問題に対して, その優位性を実証する。
アンザッツでは、元のMaxCutグラフから線形鎖を見つけ、この鎖に沿ってエンタングゲートを順次配置する。
この線形鎖アンサッツは、浅い量子回路と、問題の大きさとは独立にスケールする低い実行時間によって特徴付けられる。
論文 参考訳（メタデータ） (2025-09-22T00:33:54Z) - Variational quantum algorithms with exact geodesic transport [0.0]
変分量子アルゴリズム(VQA)は、量子コンピュータの短期的応用に期待できる候補である。
本稿では,変分量子回路の解析的リーマン最適化を可能にする曲率対応フレームワークVQAを紹介する。
論文 参考訳（メタデータ） (2025-06-20T18:00:10Z) - Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。
本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
論文 参考訳（メタデータ） (2025-04-21T18:19:19Z) - Differentiable Quadratic Optimization For The Maximum Independent Set Problem [23.643727259409744]
pCQO-MISはグラフ内の数ノードでのみスケールし、数値エッジではないことを示す。
実験により,提案手法の有効性を,精度,サンプリング,データ中心アプローチと比較した。
論文 参考訳（メタデータ） (2024-06-27T21:12:48Z) - Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
我々はこのプロトコルをバイアス場デジタルダイアバティック量子最適化(BF-DCQO)と呼ぶ。
私たちの純粋に量子的なアプローチは、古典的な変分量子アルゴリズムへの依存を排除します。
基底状態の成功確率のスケーリング改善を実現し、最大2桁まで増大する。
論文 参考訳（メタデータ） (2024-05-22T18:11:42Z) - An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文 参考訳（メタデータ） (2023-02-09T07:47:06Z) - Approximate Quantum Compiling for Quantum Simulation: A Tensor Network based approach [1.237454174824584]
行列生成状態(MPS)から短深さ量子回路を生成する新しいアルゴリズムであるAQCtensorを導入する。
我々のアプローチは、量子多体ハミルトニアンの時間進化から生じる量子状態の準備に特化している。
100量子ビットのシミュレーション問題に対して、AQCtensorは、結果の最適化回路の深さの少なくとも1桁の縮小を実現していることを示す。
論文 参考訳（メタデータ） (2023-01-20T14:40:29Z) - 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) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。
我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。
すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
論文 参考訳（メタデータ） (2020-10-01T18:14:11Z) - MoG-VQE: Multiobjective genetic variational quantum eigensolver [0.0]
変分量子固有解法 (VQE) は、近距離量子コンピュータのための最初の実用的なアルゴリズムとして登場した。
本稿では,低深度と精度の向上を両立させる手法を提案する。
2ビットゲート数の10倍近く削減されるのを、標準のハードウェア効率のアンサッツと比較して観察する。
論文 参考訳（メタデータ） (2020-07-08T20:44:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。