論文の概要: Quantum Max-Flow Min-Cut theorem

• arxiv url: http://arxiv.org/abs/2110.00905v1
• Date: Sun, 3 Oct 2021 02:11:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-12 16:14:30.115253
• Title: Quantum Max-Flow Min-Cut theorem
• Title（参考訳）: 量子マックスフローミニカット定理
• Authors: Nengkun Yu
• Abstract要約: 量子最大流の新しい定義に対する量子最大流分法定理を確立する。 この結果は、量子最大フローと量子ミンカットの比が、次元$n$が無限大になる傾向にあるため、$$に収束することを示している。
• 参考スコア（独自算出の注目度）: 11.98034899127065
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The max-flow min-cut theorem is a cornerstone result in combinatorial optimization. Calegari et al. (arXiv:0802.3208) initialized the study of quantum max-flow min-cut conjecture, which connects the rank of a tensor network and the min-cut. Cui et al. (arXiv:1508.04644) showed that this conjecture is false generally. In this paper, we establish a quantum max-flow min-cut theorem for a new definition of quantum maximum flow. In particular, we show that for any quantum tensor network, there are infinitely many $n$, such that quantum max-flow equals quantum min-cut, after attaching dimension $n$ maximally entangled state to each edge as ancilla. Our result implies that the ratio of the quantum max-flow to the quantum min-cut converges to $1$ as the dimension $n$ tends to infinity. As a direct application, we prove the validity of the asymptotical version of the open problem about the quantum max-flow and the min-cut, proposed in Cui et al. (arXiv:1508.04644 ).
• Abstract（参考訳）: 最大フロー min-cut 定理は組合せ最適化における基礎的な結果である。 Calegari et al. (arXiv:0802.3208) はテンソルネットワークのランクとミンカットを結びつける量子マックスフローミンカット予想の研究を初期化した。 Cui et al. (arXiv:1508.04644) は、この予想が一般に偽であることを示した。 本稿では,量子最大流の新たな定義のための量子最大流分法定理を確立する。 特に、任意の量子テンソルネットワークに対して、無限に多くの n$ が存在し、例えば量子マックスフローは、各辺にアンシラとして最大エンタングル状態の次元 n$ をアタッチした後、量子ミンカットに等しい。 その結果、量子マックスフローと量子ミニカットの比率は、次元$n$が無限大になるにつれて1ドルに収束することが示唆された。 直接応用として、Cui et al. (arXiv:1508.04644 ) で提案された量子最大流とmin-cutに関する開問題の漸近版の有効性を証明する。

関連論文リスト

• Circuit Complexity of Sparse Quantum State Preparation [0.0]
  任意の$n$-qubit $d$-sparse量子状態は、$O(fracdnlog d)$とdeep $Theta(log dn)$の量子回路で、少なくとも$O(fracndlog d )$ acillary qubitsを用いて作成できることを示す。 また、回路サイズに$Omega(fracdnlog(n + m) + log d + n)$ という下界の$Omega(fracdnlog(n + m) + log d + n)$ を設定できる。
  論文  参考訳（メタデータ） (2024-06-23T15:28:20Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• The classical limit of Quantum Max-Cut [0.18416014644193066]
  我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。 半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
  論文  参考訳（メタデータ） (2024-01-23T18:53:34Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  非最適化に対する古典的な下界の進歩にもかかわらず、これらの境界は依然として広く開である。 最初の設定について、Omegabig(frac-1+ppp)$。 第二設定については、おめがの()$。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。 Omega()$ if 勾配関数は滑らかである。
  論文  参考訳（メタデータ） (2022-12-07T19:02:36Z)
• 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 Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)
• Asymptotic theory of quantum channel estimation [3.3852463130297448]
  単純な基準でスケーリングが線形か二次かを判断できることが示される。 スケーリングが線形である場合、QFIは一般にシングルチャネルQFIのN$倍であることを示す。
  論文  参考訳（メタデータ） (2020-03-23T21:50:12Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。 重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。 クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
  論文  参考訳（メタデータ） (2020-02-17T08:51:42Z)

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

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