論文の概要: Classical and Quantum Heuristics for the Binary Paint Shop Problem

• arxiv url: http://arxiv.org/abs/2509.15294v1
• Date: Thu, 18 Sep 2025 18:00:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-22 18:18:10.853912
• Title: Classical and Quantum Heuristics for the Binary Paint Shop Problem
• Title（参考訳）: バイナリペイントショップ問題に対する古典的および量子的ヒューリスティックス
• Authors: V Vijendran, Dax Enshan Koh, Ping Koy Lam, Syed M Assad,
• Abstract要約: バイナリペイントショップ問題(BPSP)は自動車製造における最適化問題である。 主要な性能指標はペイントスワップ比であり、車ごとの平均色変化数である。 BPSPの重み付きMaxCutへの還元により,QAOAをBPSPに適用するための理論的基礎を構築した。
• 参考スコア（独自算出の注目度）: 0.3499870393443268
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Binary Paint Shop Problem (BPSP) is an $\mathsf{APX}$-hard optimisation problem in automotive manufacturing: given a sequence of $2n$ cars, comprising $n$ distinct models each appearing twice, the task is to decide which of two colours to paint each car so that the two occurrences of each model are painted differently, while minimising consecutive colour swaps. The key performance metric is the paint swap ratio, the average number of colour changes per car, which directly impacts production efficiency and cost. Prior work showed that the Quantum Approximate Optimisation Algorithm (QAOA) at depth $p=7$ achieves a paint swap ratio of $0.393$, outperforming the classical Recursive Greedy (RG) heuristic with an expected ratio of $0.4$ [Phys. Rev. A 104, 012403 (2021)]. More recently, the classical Recursive Star Greedy (RSG) heuristic was conjectured to achieve an expected ratio of $0.361$. In this study, we develop the theoretical foundations for applying QAOA to BPSP through a reduction of BPSP to weighted MaxCut, and use this framework to benchmark two state-of-the-art low-depth QAOA variants, eXpressive QAOA (XQAOA) and Recursive QAOA (RQAOA), at $p=1$ (denoted XQAOA$_1$ and RQAOA$_1$), against the strongest classical heuristics known to date. Across instances ranging from $2^7$ to $2^{12}$ cars, XQAOA$_1$ achieves an average ratio of $0.357$, surpassing RQAOA$_1$ and all classical heuristics, including the conjectured performance of RSG. Surprisingly, RQAOA$_1$ shows diminishing performance as size increases: despite using provably optimal QAOA$_1$ parameters at each recursion, it is outperformed by RSG on most $2^{11}$-car instances and all $2^{12}$-car instances. To our knowledge, this is the first study to report RQAOA$_1$'s performance degradation at scale. In contrast, XQAOA$_1$ remains robust, indicating strong potential to asymptotically surpass all known heuristics.
• Abstract（参考訳）: BPSP (Binary Paint Shop Problem) は自動車製造における$\mathsf{APX}$-hard optimization problem であり、それぞれ2つの異なるモデルがそれぞれ2つずつ出現し、各モデルの2つの発生が異なるように塗装する2つの色をそれぞれ決定し、連続的な色スワップを最小化する。 主要な性能指標は塗料スワップ比であり、車ごとの平均色変化数であり、生産効率とコストに直接影響を及ぼす。 以前の研究では、量子近似最適化アルゴリズム (QAOA) が深さ$p=7$でペイントスワップ比が0.393$で、古典的再帰グリーディ (RG) ヒューリスティックを0.4$ [Phys. Rev. A 104, 012403 (2021)] で上回ることを示した。 最近では、古典的再帰的スターグリード(RSG)ヒューリスティック(英語版)が0.361ドルと予測された。 本研究では,BPSPの重み付きMaxCutへの還元によるBPSPへのQAOA適用の理論基盤を開発し,このフレームワークを用いて,現在知られている最強の古典的ヒューリスティックスに対して,eXpressive QAOA (XQAOA) と Recursive QAOA (RQAOA) の2つの最先端の低深度QAOA変種(XQAAOA) を$p=1$(XQAOA$_1$およびRQAOA$_1$) でベンチマークする。 RQAOA$_1$を上回り、RSGの予想性能を含む古典的ヒューリスティックスをすべて上回る平均比が0.357$に達する。 驚くべきことに、RQAOA$_1$は、サイズが大きくなるにつれてパフォーマンスが低下する。各再帰で証明可能な最適なQAOA$_1$パラメータを使用するにもかかわらず、ほとんどの2^{11}$-carインスタンスとすべての2^{12}$-carインスタンスでRSGによりパフォーマンスが向上する。 我々の知る限り、RQAOA$_1$sのパフォーマンス劣化を報告した最初の研究である。 対照的に、XQAOA$_1$は頑健であり、既知のすべてのヒューリスティックを漸近的に超える強いポテンシャルを示している。

関連論文リスト

• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems [0.46040036610482665]
  線形ランプQAOAは,様々な最適化問題にまたがる最適解を効率的に近似できることを示す。 最大$N_q = 109$ qubits,$p=100$,21,200 CNOTゲートを必要とする回路を有する複数のQPU上でのLR-QAOAの結果を示す。
  論文  参考訳（メタデータ） (2024-05-15T08:07:52Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Sharpened Lazy Incremental Quasi-Newton Method [15.632456816019944]
  SLIQN法(シャープエントラジインクリメンタル準ニュートン法)について紹介する。 明示的な超線型収束率と優れた経験的性能を、定価$O(d2)$コストで達成する。 実験では,他の準ニュートン変種よりもSLIQNの方が優れていることを示した。
  論文  参考訳（メタデータ） (2023-05-26T22:06:24Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)
• Threshold-Based Quantum Optimization [0.0]
  Th-QAOA(Threshold QAOA)は、量子交互演算子Ansatz(QAOA)の変種である。 GM-Th-QAOAをGroverの量子探索アルゴリズムの一般化と見なすことができる。
  論文  参考訳（メタデータ） (2021-06-25T19:36:49Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [14.309243378538014]
  OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。 確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。 また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
  論文  参考訳（メタデータ） (2020-12-14T03:07:39Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。 また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
  論文  参考訳（メタデータ） (2020-06-08T18:30:12Z)

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

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