論文の概要: 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)の配置のような重要な計算複雑性の問題を解く可能性がある。
さらに,量子アルゴリズムは,行列の永久関数と量子イジングハミルトニアンの実時間分割関数との計算複雑性関係を直接示す。
関連論文リスト
- Polynomial-depth quantum algorithm for computing matrix determinant [49.494595696663524]
正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。
行列の各行は、ある量子系の純粋な状態として符号化される。
したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
論文 参考訳(メタデータ) (2024-01-29T23:23:27Z) - Generalized Quantum Singular Value Transformation [0.0]
量子特異値変換は量子アルゴリズムに革命をもたらした。
任意の行列に計算を適用することにより、量子アルゴリズムの統一図を提供する。
最近の作業は制限を取り除き、より高速な計算を可能にした。
論文 参考訳(メタデータ) (2023-12-01T16:59:14Z) - Practical limitations of quantum data propagation on noisy quantum
processors [1.2891210250935146]
行列を高い条件数で反転させるのに古典的な計算を必要とする量子アルゴリズムは、誤り確率が非常に低い単一および2量子ゲートを必要とすることを示す。
我々の研究は、ノイズの多い環境下で実行できるハイブリッド量子古典アルゴリズムの主流概念に挑戦する。
論文 参考訳(メタデータ) (2023-06-22T17:12:52Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。
このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。
大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
論文 参考訳(メタデータ) (2023-04-12T18:10:47Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳(メタデータ) (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳(メタデータ) (2022-10-04T13:27:01Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - Quantum algorithms for powering stable Hermitian matrices [0.7734726150561088]
行列パワーティング(英: Matrix Powering)は、線形代数における基本的な計算プリミティブである。
古典行列パワーリングアルゴリズムを高速化する2つの量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-03-15T12:20:04Z) - Finding high-order Hadamard matrices by using quantum computers [0.0]
H行列の古典的構成・探索手法を採用することにより、高次H行列を見つけるための新しい量子コンピューティング手法を開発することができることを示す。
特に、チューリンに基づく量子計算法は、任意に高次H行列を見つけるためにさらに発展することができる。
論文 参考訳(メタデータ) (2020-09-23T03:19:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。