論文の概要: Non-variational Quantum Combinatorial Optimisation
- arxiv url: http://arxiv.org/abs/2404.03167v1
- Date: Thu, 4 Apr 2024 02:36:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-05 16:03:13.219853
- Title: Non-variational Quantum Combinatorial Optimisation
- Title（参考訳）: 非変分量子組合せ最適化
- Authors: Tavis Bennett, Lyle Noakes, Jingbo Wang,
- Abstract要約: 本稿では,多種多様な最適化問題を解くために,非変分量子アルゴリズムを提案する。
アルゴリズムの汎用性は、様々な問題に適用することで実証される。
各問題インスタンスに対して、アルゴリズムは少数の反復で大域的に最適な解を求める。
- 参考スコア（独自算出の注目度）: 3.6538093004443155
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces a non-variational quantum algorithm designed to solve a wide range of combinatorial optimisation problems. The algorithm leverages an engineered interference process achieved through repeated application of two unitaries; one inducing phase-shifts dependent on objective function values, and the other mixing phase-shifted probability amplitudes via a continuous-time quantum walk (CTQW) on a problem-specific graph. The algorithm's versatility is demonstrated through its application to various problems, namely those for which solutions are characterised by either a vector of binary variables, a vector of non-binary integer variables, or permutations (a vector of integer variables without repetition). An efficient quantum circuit implementation of the CTQW for each of these problem types is also discussed. A penalty function approach for constrained problems is also introduced, including a method for optimising the penalty function. The algorithm's performance is demonstrated through numerical simulation for randomly generated instances of the following problems (and problem sizes): weighted maxcut (18 vertices), maximum independent set (18 vertices), k-means clustering (12 datapoints, 3 clusters), capacitated facility location (12 customers, 3 facility locations), and the quadratic assignment problem (9 locations). For each problem instance, the algorithm finds a globally optimal solution with a small number of iterations.
- Abstract（参考訳）: 本稿では,様々な組合せ最適化問題を解くために,非変分量子アルゴリズムを提案する。
このアルゴリズムは、2つのユニタリの繰り返し適用によって達成されるエンジニアリングされた干渉プロセスを利用する。一方は目的関数値に依存する位相シフトを誘導し、もう一方は問題固有のグラフ上の連続時間量子ウォーク(CTQW)を介して位相シフトされた確率振幅を混合する。
アルゴリズムの汎用性は、様々な問題、すなわち解がバイナリ変数のベクトル、非バイナリ整数変数のベクトル、あるいは置換(繰り返しを持たない整数変数のベクトル)によって特徴づけられることを通じて示される。
これらの問題の種類ごとにCTQWの効率的な量子回路の実装についても論じる。
ペナルティ関数を最適化する方法を含む制約付き問題に対するペナルティ関数アプローチも導入する。
アルゴリズムの性能は、重み付きマックスカット(18頂点)、最大独立セット(18頂点)、k平均クラスタリング(12データポイント、3クラスタ)、容量化された施設位置(12顧客、3施設位置)、二次割り当て問題(9箇所)のランダムに生成されたインスタンスの数値シミュレーションによって実証される。
各問題インスタンスに対して、アルゴリズムは少数の反復で大域的に最適な解を求める。
関連論文リスト
- Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。
このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
論文 参考訳（メタデータ） (2024-07-29T13:54:28Z) - Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms [0.0]
組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。
この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
論文 参考訳（メタデータ） (2024-03-05T17:46:04Z) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳（メタデータ） (2023-11-16T09:19:01Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - 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) - Quantum approximate optimization algorithm for qudit systems [0.0]
量子近似最適化アルゴリズム(QAOA)について考察する。
本稿では、QAOAを用いて様々な整数最適化問題を定式化する方法を説明する。
最大$kのカラー化問題にマッピングした充電最適化問題の数値計算結果を示す。
論文 参考訳（メタデータ） (2022-04-01T10:37:57Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Continuous black-box optimization with quantum annealing and random
subspace coding [2.839269856680851]
ベイズ最適化のようなブラックボックス最適化アルゴリズムは、基礎関数の推論と獲得関数の最適化を交互に行い、未知関数の極端を見つける。
高次元空間では、そのようなアルゴリズムは獲得関数の最適化が困難であるため、性能が劣る。
連続ブラックボックス最適化の難しさを克服するために量子アニールを適用する。
論文 参考訳（メタデータ） (2021-04-30T06:19:07Z) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳（メタデータ） (2021-01-19T17:51:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。