論文の概要: A Lovász theta lower bound on Quantum Max Cut

• arxiv url: http://arxiv.org/abs/2512.20326v1
• Date: Tue, 23 Dec 2025 12:53:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-24 19:17:49.876397
• Title: A Lovász theta lower bound on Quantum Max Cut
• Title（参考訳）: 量子マックスカットによるロヴァース座下界
• Authors: Felix Huber,
• Abstract要約: 我々は、グラフの量子マックスカットへの下界を、その補体のロヴシュ・テータ函数の観点から証明する。 境界は量子マックスカットに適用されたときの古典的境界よりも優れる。
• 参考スコア（独自算出の注目度）: 2.0305676256390934
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove a lower bound to quantum Max Cut of a graph in terms of the Lovász theta function of its complement. For a graph with $m$ edges, $\text{qmc}(G) \geq \tfrac{m}{4}\big( 1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$, with the bound achieved by a product state. The proof extends a result by Balla, Janzer, and Sudakov on classical Max Cut and is also inspired by the randomized rounding method of Gharibian and Parekh. The bound outperforms the classical bound when applied to quantum Max Cut.
• Abstract（参考訳）: 我々は、グラフの量子マックスカットへの下界を、その補体のロヴァース・テータ函数の観点から証明する。 m$エッジを持つグラフに対して、$\text{qmc}(G) \geq \tfrac{m}{4}\big(1 + \tfrac{8}{3π}\tfrac{1}{\vartheta(\bar{G}) -1} \big)$ は積状態によって達成される。 この証明は、古典的なマックスカットに関するバラ、ヤンツァー、スダコフの結果を拡張し、またガリービアンとパレフのランダムな丸め法にも着想を得ている。 境界は量子マックスカットに適用されたときの古典的境界よりも優れる。

関連論文リスト

• Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA [0.027042267806481293]
  我々は MaxCut を、様々な$g$s に対して最小の girth $g$ の 3 つの正則グラフ上で研究する。 深さ$g geq 16$、深さ$p geq 7$の場合、QAOAは以前に知られていた下限を改善する。
  論文  参考訳（メタデータ） (2025-03-17T03:58:43Z)
• On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut [2.2776283699063664]
  最大カット問題(Max-Cut)の1-varepsilon$と1-varepsilon1/2$から、任意の有限$ell_p$-normの下での$gamma$-Approximate Closest Vector Problemへの線形サイズの縮小を示す。 有限 $ell_p$-norm における $o(sqrtlog nfrac1p)$- Approximate Closest Vector Problem に対する部分指数時間(古典的あるいは量子的)アルゴリズムは、状態よりも高速であることを示す。
  論文  参考訳（メタデータ） (2024-11-06T18:58:17Z)
• The classical limit of Quantum Max-Cut [0.16385815610837165]
  我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。 半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
  論文  参考訳（メタデータ） (2024-01-23T18:53:34Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  量子Max-$d$-Cut問題(Quantum Max-$d$-Cut problem)は、プロジェクターに付随する期待エネルギーを、全ての局所相互作用上の2つの$d$-dimensional quditsの非対称部分空間に最大化する量子状態を見つけることである。 我々は,非自明な性能保証を実現するために,有界な純度を持つ混合状態の積状態解を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-09-19T22:53:17Z)
• The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut [0.07614628596146598]
  グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。 我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
  論文  参考訳（メタデータ） (2022-06-01T03:40:56Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Quantum Max-Flow Min-Cut theorem [11.98034899127065]
  量子最大流の新しい定義に対する量子最大流分法定理を確立する。 この結果は、量子最大フローと量子ミンカットの比が、次元$n$が無限大になる傾向にあるため、$$に収束することを示している。
  論文  参考訳（メタデータ） (2021-10-03T02:11:39Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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