論文の概要: Quantum estimation bound of Gaussian matrix permanent

• arxiv url: http://arxiv.org/abs/2205.01328v3
• Date: Tue, 23 Jul 2024 15:01:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-24 23:52:45.630941
• Title: Quantum estimation bound of Gaussian matrix permanent
• Title（参考訳）: ガウス行列の永久的量子推定境界
• Authors: Joonsuk Huh,
• Abstract要約: 行列永久性の厳密な計算と乗算誤差推定は、古典コンピュータと量子コンピュータの両方において困難である。 行列の永久性に関する新しい公式とその対応する量子式は, 平均加算誤差のより優れた推定を可能にした。
• 参考スコア（独自算出の注目度）: 1.7404865362620803
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers. Regarding the permanents of random Gaussian matrices, the additive error estimation is closely linked to boson sampling, and achieving multiplicative error estimation requires exponentially many samplings. Our newly developed formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error for random Gaussian matrices compared to Gurvits' classical sampling algorithm. The well-known Ryser formula has been converted into a quantum permanent estimator. When dealing with real random Gaussian square matrices of size $N$, the quantum estimator can approximate the matrix permanent with an additive error smaller than $\epsilon(\sqrt{\mathrm{e}N})^{N}$, where $\epsilon$ is the estimation precision. In contrast, Gurvits' classical sampling algorithm has an estimation error of $\epsilon(2\sqrt{N})^{N}$, which is exponentially larger ($1.2^{N}$) than the quantum method. As expected, the quantum additive error bound fails to reach the multiplicative error bound of $(2\pi N)^{1/4}\epsilon(\sqrt{N/\mathrm{e}})^{N}$. Additionally, the quantum permanent estimator can be up to quadratically faster than the classical estimator when using quantum phase estimation-based amplitude estimation.
• Abstract（参考訳）: 行列永久性の厳密な計算と乗算誤差推定は、古典コンピュータと量子コンピュータの両方において困難である。 ランダムガウス行列の永久性については、加算誤差推定はボソンサンプリングと密接に関連しており、乗算誤差推定には指数関数的に多くのサンプリングが必要である。 Gurvitsの古典的サンプリングアルゴリズムと比較して,新たに開発された行列永久数とその対応する量子式は,ランダムなガウス行列に対する平均加法誤差のより優れた推定を可能にした。 有名なライザーの公式は、量子永久推定器に変換されている。 実ランダムなガウス平方行列を$N$で扱うとき、量子推定器は行列を$\epsilon(\sqrt{\mathrm{e}N})^{N}$より小さい加法誤差で永久的に近似することができる。 対照的に、ガーヴィットの古典的なサンプリングアルゴリズムは$\epsilon(2\sqrt{N})^{N}$という推定誤差を持ち、これは量子法よりも指数関数的に大きい(1.2^{N}$)。 予想通り、量子加法的誤差境界は、$(2\pi N)^{1/4}\epsilon(\sqrt{N/\mathrm{e}})^{N}$の乗法誤差境界に達することに失敗する。 さらに、量子位相推定に基づく振幅推定を使用する場合、量子永久推定器は古典的推定器よりも最大で2倍高速である。

関連論文リスト

• Heisenberg-limited adaptive gradient estimation for multiple observables [0.39102514525861415]
  量子力学において、一般観測値の期待値を測定することは、固有の統計的不確実性を持つ。 我々は,ルート平均二乗誤差内における一般可観測値の期待値を推定する適応量子アルゴリズムを提案する。 本手法は,量子コンピュータを用いた複雑な量子システムにおいて,様々な物理特性を正確に理解し,予測する新しい手法である。
  論文  参考訳（メタデータ） (2024-06-05T14:16:47Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
  正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。 行列の各行は、ある量子系の純粋な状態として符号化される。 したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
  論文  参考訳（メタデータ） (2024-01-29T23:23:27Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  我々は、von-Neumann方程式を線形化するための一般的なフレームワークを開発し、量子シミュレーションに適した形でレンダリングする。 フォン・ノイマン方程式のこれらの線型化のうちの1つは、状態ベクトルが密度行列の列重ね元となる標準的な場合に対応することを示す。 密度行列の力学をシミュレートする量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-14T23:08:51Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• Trimmed Sampling Algorithm for the Noisy Generalized Eigenvalue Problem [0.0]
  一般化固有値問題を解くことは、大きな量子系のエネルギー固有状態を見つけるのに有用な方法である。 マトリックス要素がメソッドを使って評価され、大きなエラーバーがある場合、特に問題となる。 本稿では,この問題を解決するためにトリミングサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-05T18:10:12Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• The limits of quantum circuit simulation with low precision arithmetic [0.0]
  目標は、ランダムで最大に絡み合った量子状態を含むシミュレーションで、どれだけのメモリを節約できるかを推定することである。 B$ビットの算術極表現は、各量子振幅に対して定義される。 Q$ qubits と $G$ gates の回路上の累積誤差を定量化するモデルを開発した。
  論文  参考訳（メタデータ） (2020-05-27T14:48:31Z)
• 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)

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

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