論文の概要: Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization
- arxiv url: http://arxiv.org/abs/2509.15138v1
- Date: Thu, 18 Sep 2025 16:49:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-19 17:26:53.340842
- Title: Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization
- Title（参考訳）: サンプルベースガイド量子ウォーク:組合せ最適化のための非変分量子アルゴリズム
- Authors: Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto,
- Abstract要約: 任意の次数の二項最適化問題を解くための新しい量子アルゴリズムであるSamBa-GQWを紹介する。
我々のアルゴリズムの重要な新規性は、ハミルトニアン問題のスペクトルに関する情報を提供するオフラインの古典的サンプリングプロトコルである。
- 参考スコア（独自算出の注目度）: 0.20999222360659606
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce SamBa-GQW, a novel quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree with no use of any classical optimizer. The algorithm is based on a continuous-time quantum walk on the solution space represented as a graph. The walker explores the solution space to find its way to vertices that minimize the cost function of the optimization problem. The key novelty of our algorithm is an offline classical sampling protocol that gives information about the spectrum of the problem Hamiltonian. Then, the extracted information is used to guide the walker to high quality solutions via a quantum walk with a time-dependent hopping rate. We investigate the performance of SamBa-GQW on several quadratic problems, namely MaxCut, maximum independent set, portfolio optimization, and higher-order polynomial problems such as LABS, MAX-$k$-SAT and a quartic reformulation of the travelling salesperson problem. We empirically demonstrate that SamBa-GQW finds high quality approximate solutions on problems up to a size of $n=20$ qubits by only sampling $n^2$ states among $2^n$ possible decisions. SamBa-GQW compares very well also to other guided quantum walks and QAOA.
- Abstract（参考訳）: 古典最適化器を使わずに任意の次数の二項組合せ最適化問題を解く新しい量子アルゴリズムであるSamBa-GQWを紹介する。
このアルゴリズムは、グラフとして表される解空間上の連続時間量子ウォークに基づいている。
ウォーカーは、最適化問題のコスト関数を最小限に抑える頂点への道を見つけるために、解空間を探索する。
我々のアルゴリズムの重要な新規性は、ハミルトニアン問題のスペクトルに関する情報を提供するオフラインの古典的サンプリングプロトコルである。
そして、抽出した情報を用いて、時間依存ホッピングレートの量子ウォークを介して、歩行器を高品質なソリューションに誘導する。
我々は,SamBa-GQWの最大独立集合,ポートフォリオ最適化,LABS,MAX-$k$-SATなどの高次多項式問題,旅行セールスパーソン問題の質的再構成など,いくつかの二次問題に対する性能について検討する。
我々は、SamBa-GQWが、可能な決定のうち、$n^2$状態のみをサンプリングすることで、最大$n=20$ qubitsという問題に対する高品質な近似解を見つけることを実証的に実証した。
SamBa-GQWは、他のガイド付き量子ウォークやQAOAと非常によく比較している。
関連論文リスト
- Sampling-based Quantum Optimization Algorithm with Quantum Relaxation [0.0]
変分量子アルゴリズム(VQA)は、雑音量子デバイスのためのハイブリッドアルゴリズムである。
サンプリングに基づく量子アルゴリズムは、最近、大規模量子化学問題にうまく適用されている。
論文 参考訳（メタデータ） (2025-04-17T04:13:51Z) - 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) - Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm [0.7046417074932257]
量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。
古典的解法は線形時間複雑性において高品質な近似解を生成することができる。
異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
論文 参考訳（メタデータ） (2022-06-07T20:59:19Z) - 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) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。