論文の概要: Complexity of quantum state verification in the quantum linear systems problem

• arxiv url: http://arxiv.org/abs/2007.15698v2
• Date: Tue, 23 Feb 2021 18:25:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-07 18:11:39.444071
• Title: Complexity of quantum state verification in the quantum linear systems problem
• Title（参考訳）: 量子線形系問題における量子状態検証の複雑さ
• Authors: Rolando D. Somma and Yigit Subasi
• Abstract要約: A vec x = vec b$ という形の線形方程式の系を解く文脈における量子状態検証の複雑さを解析する。 与えられた量子状態が量子線型系問題の解から一定の距離内にあるかどうかを検証する量子演算には、$q=Omega(kappa)$が必要であることを示す。
• 参考スコア（独自算出の注目度）: 0.12891210250935145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form $A \vec x = \vec b$. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires $q=\Omega(\kappa)$ uses of a unitary that prepares a quantum state $\left| b \right>$, proportional to $\vec b$, and its inverse in the worst case. Here, $\kappa$ is the condition number of the matrix $A$. For typical instances, we show that $q=\Omega(\sqrt \kappa)$ with high probability. These lower bounds are almost achieved if quantum state verification is performed using known quantum algorithms for the quantum linear systems problem. We also analyze the number of copies of $\left| b \right>$ required by verification procedures of the prepare and measure type. In this case, the lower bounds are quadratically worse, being $\Omega(\kappa^2)$ in the worst case and $\Omega(\kappa)$ in typical instances with high probability. We discuss the implications of our results to known variational and related approaches to this problem, where state preparation, gate, and measurement errors will need to decrease rapidly with $\kappa$ for worst-case and typical instances if error correction is not used, and present some open problems.
• Abstract（参考訳）: A \vec x = \vec b$ という形の線形方程式の系を解く文脈における量子状態検証の複雑さを解析する。 与えられた量子状態が量子線型系の問題の解から一定の距離内にあるかどうかを検証する量子演算は、$q=\Omega(\kappa)$ 量子状態 $\left| b \right>$ を準備するユニタリの使用が必要であり、その逆は$\vec b$ に比例する。 ここで、$\kappa$ は行列 $a$ の条件数である。 典型的な場合、$q=\Omega(\sqrt \kappa)$ は高い確率で表される。 これらの下限は、量子線形系問題に対する既知の量子アルゴリズムを用いて量子状態検証を行うとほぼ達成される。 また、準備および測定型の検証手順によって必要となる$\left| b \right>$のコピー数を分析する。 この場合、下界は2次に悪化し、最悪の場合は$\Omega(\kappa^2)$、確率の高い典型的な場合$\Omega(\kappa)$である。 我々は,この問題に対する既知の変分的および関連するアプローチに対する結果の影響について論じる。状態準備,ゲートおよび測定誤差は,最悪の場合や,エラー訂正が使用されていない場合の典型的なインスタンスに対して$\kappa$ で急速に減少しなければならず,いくつかの未解決な問題を示す。

関連論文リスト

• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations [7.319050391449301]
  時間複雑性を持つ線形方程式系を解くための量子アルゴリズムは、クエリの深さで$Omega(kappa)$が低いことを示す。 この問題の最先端の量子アルゴリズムは、Costa, An, Sanders, Su, Babbush, and Berry (2022) によるものであり、最適なクエリ複雑性は $Theta(kappa)$である。
  論文  参考訳（メタデータ） (2024-07-08T15:05:46Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• A generalized framework for quantum state discrimination, hybrid algorithms, and the quantum change point problem [3.4683494246563606]
  半定値計画法に基づくハイブリッド量子古典アルゴリズムを提案し、状態が純粋で効率的な回路を持つ場合の最大報酬を計算する。 量子状態の列が与えられた場合、量子状態が変化したときの時間ステップを決定する量子変化点同定問題に対して、現在可能なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-12-07T03:42:40Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  2つの未知の混合量子状態 $rho$ と $sigma$ に対して、それらの忠実度 $F(rho,sigma)$ は基本的な問題である。 我々は、この問題を$namepoly(log (N), r, 1/varepsilon)$ timeで解く量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-16T13:57:01Z)
• Efficient Verification of Anticoncentrated Quantum States [0.38073142980733]
  準備可能な量子状態 $mu$ と古典的に指定されたターゲット状態 $tau$ の間に、忠実度 $F(mu,tau)$ を推定する新しい方法を提案する。 また,本手法のより洗練されたバージョンを提示する。このバージョンでは,高効率に準備可能な,かつ良好な量子状態が重要試料として使用される。
  論文  参考訳（メタデータ） (2020-12-15T18:01:11Z)
• 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)
• Bosonic quantum communication across arbitrarily high loss channels [68.58838842613457]
  一般減衰器$Phi_lambda, sigma$はボゾン量子チャネルであり、入力と固定された環境状態を組み合わせることで作用する。 任意の$lambda>0$に対して、適切な単一モード状態 $sigma(lambda)$が存在することを示す。 我々の結果は、チャネルの入力でエネルギー制約を固定しても成り立ち、任意に低い透過率の極限でも一定の速度で量子通信が可能であることを示唆している。
  論文  参考訳（メタデータ） (2020-03-19T16:50:11Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。 リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
  論文  参考訳（メタデータ） (2019-09-12T17:28:09Z)

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

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