論文の概要: 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（参考訳）: 量子優位性がないということは、二項ペイントショップ問題に対する改良された境界と古典的アルゴリズムを意味する
• 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)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  量子コンピュータは、最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 本稿では,量子SDPソルバの非漸近的リソース要求の解析を行う。
  論文  参考訳（メタデータ） (2025-02-21T12:54:05Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  本稿では,デジタルカウンセバティック量子最適化(DCQO)パラダイムを用いて,ポートフォリオ最適化のための高速なディジタル量子アルゴリズムを提案する。 提案手法は,アルゴリズムの回路深度要件を特に低減し,解の精度を向上し,現在の量子プロセッサに適している。 我々は,IonQトラップイオン量子コンピュータ上で最大20量子ビットを使用するプロトコルの利点を実験的に実証した。
  論文  参考訳（メタデータ） (2023-08-29T17:53:08Z)
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
  量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。 QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。 この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
  論文  参考訳（メタデータ） (2023-02-09T07:47:06Z)
• 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)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• 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)

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

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