論文の概要: Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
- arxiv url: http://arxiv.org/abs/2407.06012v1
- Date: Mon, 8 Jul 2024 15:05:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-09 15:20:49.199265
- Title: Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
- Title（参考訳）: 線形方程式の解系の量子深さ下界
- Authors: Qisheng Wang, Zhicheng Zhang,
- Abstract要約: 時間複雑性を持つ線形方程式系を解くための量子アルゴリズムは、クエリの深さで$Omega(kappa)$が低いことを示す。
この問題の最先端の量子アルゴリズムは、Costa, An, Sanders, Su, Babbush, and Berry (2022) によるものであり、最適なクエリ複雑性は $Theta(kappa)$である。
- 参考スコア（独自算出の注目度）: 7.319050391449301
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Since Harrow, Hassidim, and Lloyd (2009) showed that a system of linear equations with $N$ variables and condition number $\kappa$ can be solved on a quantum computer in $\operatorname{poly}(\log(N), \kappa)$ time, exponentially faster than any classical algorithms, its improvements and applications have been extensively investigated. The state-of-the-art quantum algorithm for this problem is due to Costa, An, Sanders, Su, Babbush, and Berry (2022), with optimal query complexity $\Theta(\kappa)$. An important question left is whether parallelism can bring further optimization. In this paper, we study the limitation of parallel quantum computing on this problem. We show that any quantum algorithm for solving systems of linear equations with time complexity $\operatorname{poly}(\log(N), \kappa)$ has a lower bound of $\Omega(\kappa)$ on the depth of queries, which is tight up to a constant factor.
- Abstract（参考訳）: Harrow, Hassidim, and Lloyd (2009) は、$N$変数と条件数 $\kappa$ を持つ線形方程式の系が、量子コンピュータ上で $\operatorname{poly}(\log(N), \kappa)$ time で解けることを示したので、どの古典的アルゴリズムよりも指数関数的に高速である。
この問題の最先端の量子アルゴリズムは、Costa, An, Sanders, Su, Babbush, and Berry (2022) によるものであり、最適なクエリ複雑性は$\Theta(\kappa)$である。
重要な疑問は、並列処理がさらなる最適化をもたらすかどうかである。
本稿では,この問題に対する並列量子コンピューティングの限界について考察する。
時間複雑性を持つ線形方程式の系を解くための量子アルゴリズムとして、$\operatorname{poly}(\log(N), \kappa)$ はクエリの深さで$\Omega(\kappa)$ の低い境界を持ち、これは定数係数に固まる。
関連論文リスト
- A shortcut to an optimal quantum linear system solver [55.2480439325792]
複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。
ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。
あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
論文 参考訳（メタデータ） (2024-06-17T20:54:11Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - 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) - 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) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - On solving classes of positive-definite quantum linear systems with
quadratically improved runtime in the condition number [0.0]
量子線形系を解くことは、$A$が正定値であるとき、$kappa$のランタイム線形を必要とすることを示す。
2つの新しい量子アルゴリズムで、$kappa$の2次スピードアップを特徴とする。
論文 参考訳（メタデータ） (2021-01-28T08:41:21Z) - 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) - Variational Quantum Linear Solver [0.3774866290142281]
本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。
リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
論文 参考訳（メタデータ） (2019-09-12T17:28:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。