論文の概要: The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut
- arxiv url: http://arxiv.org/abs/2206.00213v2
- Date: Tue, 20 Sep 2022 02:48:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-11 01:22:36.174989
- Title: The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut
- Title（参考訳）: 量子および古典マックスカットの量子および古典的ストリーミング複雑性
- Authors: John Kallaugher, Ojas Parekh
- Abstract要約: グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。
我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
- 参考スコア（独自算出の注目度）: 0.07614628596146598
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the space complexity of two graph streaming problems: Max-Cut
and its quantum analogue, Quantum Max-Cut. Previous work by Kapralov and
Krachun [STOC `19] resolved the classical complexity of the \emph{classical}
problem, showing that any $(2 - \varepsilon)$-approximation requires
$\Omega(n)$ space (a $2$-approximation is trivial with $\textrm{O}(\log n)$
space). We generalize both of these qualifiers, demonstrating $\Omega(n)$ space
lower bounds for $(2 - \varepsilon)$-approximating Max-Cut and Quantum Max-Cut,
even if the algorithm is allowed to maintain a quantum state. As the trivial
approximation algorithm for Quantum Max-Cut only gives a $4$-approximation, we
show tightness with an algorithm that returns a $(2 +
\varepsilon)$-approximation to the Quantum Max-Cut value of a graph in
$\textrm{O}(\log n)$ space. Our work resolves the quantum and classical
approximability of quantum and classical Max-Cut using $\textrm{o}(n)$ space.
We prove our lower bounds through the techniques of Boolean Fourier analysis.
We give the first application of these methods to sequential one-way quantum
communication, in which each player receives a quantum message from the
previous player, and can then perform arbitrary quantum operations on it before
sending it to the next. To this end, we show how Fourier-analytic techniques
may be used to understand the application of a quantum channel.
- Abstract（参考訳）: グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。
Kapralov と Krachun [STOC `19] による以前の研究は、任意の$(2 - \varepsilon)$-approximation が$\Omega(n)$ space ($$$2$-approximation は $\textrm{O}(\log n)$ space で自明である)であることが示されている。
これらの等式を一般化し、アルゴリズムが量子状態を維持することを許されたとしても、$(2 - \varepsilon)$-approximating Max-Cut and Quantum Max-Cut に対して$\Omega(n)$ space lower bounds を示す。
Quantum Max-Cut の自明な近似アルゴリズムは 4$-approximation しか与えないため、$(2 + \varepsilon)$-approximation を $\textrm{O}(\log n)$ space のグラフの Quantum Max-Cut 値に戻すアルゴリズムとの密接性を示す。
我々の研究は、$\textrm{o}(n)$空間を用いて量子および古典マックスカットの量子および古典近似性を解決している。
ブールフーリエ解析(Boolean Fourier analysis)による下界の証明を行う。
本稿では,各プレイヤーが前者のプレイヤーから量子メッセージを受信し,次に送信する前に任意の量子演算を行うことのできる,一方向量子通信へのこれらの手法の最初の応用について述べる。
この目的のために,フーリエ解析手法を用いて量子チャネルの応用を理解する方法を示す。
関連論文リスト
- Approximating Korobov Functions via Quantum Circuits [6.460951804337735]
我々は、コロボフ関数空間において$d$次元関数を近似できる量子回路を明示的に構築する。
我々の研究は定量的近似境界を提供し、提案した量子回路の実装の複雑さを推定する。
論文 参考訳（メタデータ） (2024-04-22T20:33:53Z) - 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 Speedups of Optimizing Approximately Convex Functions with
Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
量子アルゴリズムは、$F(x*)-min_xincal K F(x)leqepsilon$が$tildeO(n3)$が$F$となるような$x*incal K$を求める。
応用として、ゼロ階凸包帯に対して $tildeO(n5log2 T)$ regret の量子関数アルゴリズムを与える。
論文 参考訳（メタデータ） (2022-09-26T03:19:40Z) - Testing and Learning Quantum Juntas Nearly Optimally [3.030969076856776]
量子量$k$-juntasの検証と学習の問題を考察する。
a)$widetildeO(sqrtk)$-query量子アルゴリズムを与え、量子$k$-juntaと量子$k$-juntaの「遠い」ユニタリ行列を区別することができる。
我々は、量子$k$-juntasのテストと量子$k$-juntasの学習のための上限を、ほぼ一致する$Omega(sqrtk)$と$Omega(frac)$で補完する。
論文 参考訳（メタデータ） (2022-07-13T00:11:14Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - 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) - 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) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。