論文の概要: A fast quantum algorithm for computing matrix permanent

• arxiv url: http://arxiv.org/abs/2205.01328v2
• Date: Thu, 14 Jul 2022 06:37:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-14 11:59:27.557846
• Title: A fast quantum algorithm for computing matrix permanent
• Title（参考訳）: 行列永久数計算のための高速量子アルゴリズム
• Authors: Joonsuk Huh
• Abstract要約: 本稿では,行列永久計算のための最初の効率的な量子アルゴリズムを提案する。 行列の特殊集合において、行列の永久性に対する乗法的誤差推定が可能であることを示す。
• 参考スコア（独自算出の注目度）: 3.04585143845864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Computing a matrix permanent is known to be a classically intractable problem. This paper presents the first efficient quantum algorithm for computing matrix permanents. We transformed the well-known Ryser's formula into a single quantum overlap integral and a polynomial sum of quantum overlap integrals to estimate a matrix permanent with the multiplicative error and additive error protocols, respectively. We show that the multiplicative error estimation of a matrix permanent would be possible for a special set of matrices. Such a quantum algorithm would imply that quantum computers can be more powerful than we expected. Depending on the size of a matrix norm and the ratio between 2-norm and 1-norm, we can obtain an exponentially small additive error estimation and better estimation against Gurvits' classical sampling algorithm with our quantum protocol. Our quantum algorithm attains the milestone of opening a new direction in quantum computing and computational complexity theory. It might resolve crucial computational complexity issues like locating the bounded error quantum polynomial time (BQP) relative to the polynomial hierarchy, which has been a big complexity question. Moreover, our quantum algorithm directly shows the computational complexity connection between the matrix permanent and the real-time partition function of the quantum Ising Hamiltonian.
• Abstract（参考訳）: 行列の永続性を計算することは古典的な難解な問題として知られている。 本稿では,行列永久計算のための最初の効率的な量子アルゴリズムを提案する。 我々は、よく知られたライザーの公式を1つの量子重なり積分と量子重なり積分の多項式和に変換し、それぞれ乗算誤差と加法誤差プロトコルに永続的な行列を推定した。 行列の特殊集合に対して、行列の恒久的な乗法的誤差推定が可能であることを示す。 このような量子アルゴリズムは、期待以上に量子コンピュータが強力であることを意味する。 行列ノルムの大きさと2ノルムと1ノルムの比に依存すると、指数関数的に小さな加算誤差推定と、Gurvitsの古典的サンプリングアルゴリズムに対するより優れた推定を量子プロトコルで得ることができる。 我々の量子アルゴリズムは、量子コンピューティングと計算複雑性理論の新しい方向性を開拓するマイルストーンを達成している。 これは、多項式階層に対する有界誤差量子多項式時間(bqp)の配置のような重要な計算複雑性の問題を解く可能性がある。 さらに,量子アルゴリズムは,行列の永久関数と量子イジングハミルトニアンの実時間分割関数との計算複雑性関係を直接示す。

関連論文リスト

• 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)
• 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)

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

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