論文の概要: No quantum advantage implies improved bounds and classical algorithms for the binary paint shop problem

• arxiv url: http://arxiv.org/abs/2604.00607v1
• Date: Wed, 01 Apr 2026 08:12:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-02 16:44:31.899746
• Title: No quantum advantage implies improved bounds and classical algorithms for the binary paint shop problem
• Title（参考訳）: 量子優位性がないということは、二項ペイントショップ問題に対する改良された境界と古典的アルゴリズムを意味する
• Authors: Mark Goh, Lara Caroline Pereira dos Santos, Matthias Sperl,
• Abstract要約: 本稿ではRSGアルゴリズムと対数深度QAOAの両方を超越した古典的アルゴリズムを提案する。 平均場近似最適化アルゴリズム(MF-AOA)がそのようなアルゴリズムであることを示す。
• 参考スコア（独自算出の注目度）: 6.091153856401871
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The binary paint shop problem (BPSP) is an APX-hard optimization problem in which, given n car models that occur twice in a sequence of length 2n, the goal is to find a colouring sequence such that the two occurrences of each model are painted differently, while minimizing the number of times the paint is swapped along the sequence. A recent classical heuristic, known as the recursive star greedy (RSG) algorithm, is conjectured to achieve an expected paint swap ratio of 0.361, thereby outperforming the QAOA with circuit depth p = 7. Since the performance of the QAOA with logarithmic circuit depth is instance independent, the average paint swap ratio is upper-bounded by the QAOA, which numerical evidence suggests is approximately between 0.265 and 0.282. To provide hardware-relevant comparisons, we additionally implement the BPSP on a D-Wave Quantum Annealer Advantage 2, obtaining a minimum paint swap ratio of 0.320. Given that the QAOA with logarithmic circuit depth does not exhibit quantum advantage for sparse optimization problems such as the BPSP, this implies the existence of a classical algorithm that surpasses both the RSG algorithm and logarithmic depth QAOA. We provide numerical evidence that the Mean-Field Approximate Optimization Algorithm (MF-AOA) is one such algorithm that beats all known classical heuristics and quantum algorithms to date with a paint swap ratio of approximately 0.2799.
• Abstract（参考訳）: バイナリペイントショップ問題 (BPSP) は、長さ2nの列で2回発生するn台のモデルに対して、各モデルの2つの発生を異なる色で描画するカラーシーケンスを見つけることを目的とするAPXハード最適化問題である。 最近の古典的ヒューリスティック(recursive star greedy (RSG)アルゴリズム)は、予想されるペイントスワップ比0.361に達し、回路深さp = 7でQAOAを上回っていると推測されている。 対数回路深さを持つQAOAの性能はインスタンス独立であるため、平均塗料スワップ比はQAOAによって上界に設定されており、これは0.265から0.282の数値的な証拠である。 D-Wave Quantum Annealer Advantage 2 上で BPSP を実装し,最小塗料スワップ比 0.320 を得る。 対数回路深さを持つQAOAはBPSPのようなスパース最適化問題に量子的優位性を持たず、RSGアルゴリズムと対数回路深さQAOAの両方を超える古典的アルゴリズムの存在を示唆する。 平均場近似最適化アルゴリズム(Mean-Field Approximate Optimization Algorithm, MF-AOA)は、これまでに知られているすべての古典的ヒューリスティックと量子アルゴリズムを約0.2799で破るアルゴリズムである。

関連論文リスト

• An Optimization-Free Recursive QAOA for the Binary Paint Shop Problem [0.0]
  BPSP(Binary Paint Shop Problem)は、自動車間の色の変化を最小限に抑えつつ、一定の制約の下で車列を塗装しなければならない製造における最適化問題である。 パラメータ転送はQAOAとRQAOAの最適化よりも解の質が著しく低下しないことを示す。 RQAOAはフルステートベクターの代わりに$Z$-correlationsを計測することしか必要とせず、CNOT数と深さが著しく低い回路につながる逆カソーサルコーンの利点がある。
  論文  参考訳（メタデータ） (2025-07-15T01:54:11Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。 本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
  論文  参考訳（メタデータ） (2025-04-21T18:19:19Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
  量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。 QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。 この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
  論文  参考訳（メタデータ） (2023-02-09T07:47:06Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Multi-car paint shop optimization with quantum annealing [0.0]
  本稿では,自動車産業アプリケーション,マルチカーペンキショップ (MCPS) 問題に取り組むために,バイナリペイントショップ問題 (BPSP) の一般化を提案する。 この最適化の目的は、製造中のペイントショップキュー内の車両間のカラースイッチ数を最小化することであり、既知のNPハード問題である。 我々はペイントショップ問題のサブクラスを区別し,基本MCPS問題をIsingモデルとして定式化する方法を示す。
  論文  参考訳（メタデータ） (2021-09-16T11:14:45Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm [0.0]
  我々は、量子近似最適化アルゴリズム(QAOA)を用いてバイナリペイントショップ問題(BPSP)の解を求める方法を示す。 一定の深さを持つQAOAは、無限大の極限$nrightarrowinftyinftyにおいて、古典を平均的に破ることができることを示した。
  論文  参考訳（メタデータ） (2020-11-06T15:03:27Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)

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

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