論文の概要: Exponential Quantum Space Advantage for Approximating Maximum Directed
Cut in the Streaming Model
- arxiv url: http://arxiv.org/abs/2311.14123v1
- Date: Thu, 23 Nov 2023 17:38:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-27 16:37:36.690663
- Title: Exponential Quantum Space Advantage for Approximating Maximum Directed
Cut in the Streaming Model
- Title（参考訳）: ストリーミングモデルにおける最大有向カット近似に対する指数量子空間アドバンテージ
- Authors: John Kallaugher and Ojas Parekh and Nadezhda Voronova
- Abstract要約: 自然ストリーミング問題に対して指数量子空間の優位性を示す。
これはまた、離散最適化問題を近似する最初の無条件指数量子資源の利点でもある。
我々の結果は、最近の$widetildetextO(sqrtn)$ space classical streaming approachに基づいています。
- 参考スコア（独自算出の注目度）: 0.24554686192257422
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: While the search for quantum advantage typically focuses on speedups in
execution time, quantum algorithms also offer the potential for advantage in
space complexity. Previous work has shown such advantages for data stream
problems, in which elements arrive and must be processed sequentially without
random access, but these have been restricted to specially-constructed problems
[Le Gall, SPAA `06] or polynomial advantage [Kallaugher, FOCS `21]. We show an
exponential quantum space advantage for the maximum directed cut problem. This
is the first known exponential quantum space advantage for any natural
streaming problem. This also constitutes the first unconditional exponential
quantum resource advantage for approximating a discrete optimization problem in
any setting.
Our quantum streaming algorithm $0.4844$-approximates the value of the
largest directed cut in a graph stream with $n$ vertices using polylog$(n)$
space, while previous work by Chou, Golovnev, and Velusamy [FOCS '20] implies
that obtaining an approximation ratio better than $4/9 \approx 0.4444$ requires
$\Omega(\sqrt{n})$ space for any classical streaming algorithm. Our result is
based on a recent $\widetilde{\text{O}}(\sqrt{n})$ space classical streaming
approach by Saxena, Singer, Sudan, and Velusamy [FOCS '23], with an additional
improvement in the approximation ratio due to recent work by Singer [APPROX
'23].
- Abstract（参考訳）: 量子アドバンテージの探索は一般的に実行時間の高速化に重点を置いているが、量子アルゴリズムは空間複雑性の利点も提供する。
これまでの研究は、要素がランダムアクセスなしで順次処理されるデータストリーム問題に対してそのような利点を示してきたが、これらは特別に構築された問題(Le Gall, SPAA `06]や多項式の利点(Kallaugher, FOCS `21]に限られていた。
最大有向切断問題に対する指数量子空間の優位性を示す。
これは、任意の自然ストリーミング問題に対する最初の指数関数的量子空間アドバンテージである。
これはまた、任意の設定で離散最適化問題を近似する最初の非条件指数量子リソースの利点を構成する。
我々の量子ストリーミングアルゴリズム$0.4844$は、ポリログ$(n)$空間を用いたグラフストリームにおける最大有向カットの値を近似するが、chou, golovnev, velusamy [focs '20] による以前の研究は、任意の古典的なストリーミングアルゴリズムに対して$\omega(\sqrt{n})$空間を必要とする。
この結果は、Sexena, Singer, Sudan, Velusamy [FOCS '23] による空間古典的ストリーミングアプローチである $\widetilde{\text{O}}(\sqrt{n})$ に基づいており、Singer [APPROX '23] による最近の研究により近似比がさらに改善されている。
関連論文リスト
- Quantum Algorithm for Online Exp-concave Optimization [30.962392035110135]
本稿では,量子オンライン準ニュートン法を提案する。
提案手法は, 量子推定不正確な勾配によりヘシアンを近似する。
このような後悔は、最適古典アルゴリズムを$T2/3$の係数で改善する。
論文 参考訳（メタデータ） (2024-10-25T16:58:44Z) - 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Alleviating the quantum Big-$M$ problem [0.237499051649312]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm [0.7046417074932257]
量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。
古典的解法は線形時間複雑性において高品質な近似解を生成することができる。
異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
論文 参考訳（メタデータ） (2022-06-07T20:59:19Z) - 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 Quantum Advantage for a Natural Streaming Problem [0.07614628596146598]
古典グラフカウントにおける最も研究の進んだ問題の1つとして,1パスの量子ストリーミングアルゴリズムを提案する。
ほぼ28個のパラメタライズされた上境界と下限は、ストリーミングで知られている。
論文 参考訳（メタデータ） (2021-06-08T18:34:22Z) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。