論文の概要: Quantum Approximation Complexity of Classical Optimization Problems

• arxiv url: http://arxiv.org/abs/2610.09584v1
• Date: Wed, 07 Oct 2026 07:27:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:22.774981
• Title: Quantum Approximation Complexity of Classical Optimization Problems
• Title（参考訳）: 古典最適化問題の量子近似複雑性
• Abstract要約: 量子複雑性は最悪の近似保証を改善することができることを示す。 MaxCut や MaxSAT のような一般的な問題に対する量子古典的ギャップは依然として開である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors. Assuming NP $\subsetneq$ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.
• Abstract（参考訳）: 古典的な近似複雑性は、多項式時間計算でどの解の品質を保証できるかを問う。 クラスAPX、PTAS、FPTASは、固定近似比、任意の固定精度への近似、およびランニング時間が逆精度で多項式である近似スキームを識別する。 R-APX、R-PTAS、R-FPTASである。 我々は、BQ-APX、BQ-PTAS、BQ-FPTASの有界誤り量子対を定義する。 メンバーシップは、全ての入力において、少なくとも2/3の確率で主張される近似比を達成する可能な古典解を返す均一な量子アルゴリズムを必要とする。 スコア(目的値)は、効率よく古典的に計算可能でなければならない。 実行時間にはパラメータの選択、準備、測定、復号化、繰り返しが含まれる。 多くの量子最適化法がヒューリスティックに使われており、高いベンチマークスコアだけでこれらの保証は確立されていない。 さらに、対数、多項式、指数近似係数の条件階層を確立する。 NP $\subsetneq$ BQP と仮定すると、量子クラスは厳密な階層を形成する。 素因数分解と離散対数に基づく問題は、条件付き量子古典的分離を与える。 Certified Maximum Orderは正確な量子アルゴリズムを持ち、任意のランダム化された多項式時間アルゴリズムは全ての入力に対して少なくとも逆多項式近似比を保証する。 離散対数フィッティングは、厳密な量子アルゴリズムと決定論的一半近似を持ち、一方の固定された改善は、安全な離散対数問題に対してランダム化された多項式時間アルゴリズムを与える。 以上の結果から,量子計算が最悪の近似保証を改善することが示唆された。 MaxCut や MaxSAT のような一般的な問題に対する量子古典的ギャップは依然として開である。

関連論文リスト

• Global Optimization for Parametrized Quantum Circuits [3.558201566667322]
  トレーニング可能なパラメータを一定数有する量子回路の実践的なクラスのトレーニングについて検討する。 我々の主な成果は、完全にランダム化された近似スキーム (FPRAS) である。 変分アルゴリズムにおける標準的なハイブリッド量子古典的トレーニングとは異なり、我々の手法は計算を2つの異なる段階に分けている。
  論文  参考訳（メタデータ） (2026-03-23T09:49:40Z)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  量子コンピュータは、最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 本稿では,量子SDPソルバの非漸近的リソース要求の解析を行う。
  論文  参考訳（メタデータ） (2025-02-21T12:54:05Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  Decoded Quantum Interferometry (DQI) は、量子フーリエ変換を用いて、復号化問題に対する最適化問題を削減する量子アルゴリズムである。 有限体上の最適適合を近似するために、DQIは既知の古典的アルゴリズムよりも超多項式的なスピードアップを達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• 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)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。 不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。 無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
  論文  参考訳（メタデータ） (2023-12-18T18:29:01Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
  雑音は量子回路のバイアスによる目的関数の評価を行う。 我々は、欠落した保証を導き、収束率が影響を受けないことを見出す。
  論文  参考訳（メタデータ） (2022-09-21T19:18:41Z)
• 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)

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

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