論文の概要: A Simple Quantum Blockmodeling with Qubits and Permutations
- arxiv url: http://arxiv.org/abs/2311.07726v2
- Date: Mon, 22 Apr 2024 09:16:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-24 00:23:13.767978
- Title: A Simple Quantum Blockmodeling with Qubits and Permutations
- Title（参考訳）: 量子ビットと置換を用いた簡単な量子ブロックモデリング
- Authors: Ammar Daskin,
- Abstract要約: 量子コンピュータにおけるブロックモデリングの解法を示す。
モデルでは、小さな量子ビットのグループの測定結果が、適合度値を示すためにマッピングされる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Blockmodeling of a given problem represented by an $N\times N$ adjacency matrix can be found by swapping rows and columns of the matrix (i.e. multiplying matrix from left and right by a permutation matrix). Although classical matrix permutations can be efficiently done by swapping pointers for the permuted rows (or columns) of the matrix, by changing row-column order, a permutation changes the location of the matrix elements, which determines the membership of a group in the matrix based blockmodeling. Therefore, a brute force initial estimation of a fitness value for a candidate solution involving counting the memberships of the elements may require going through all the sum of the rows (or the columns). Similarly permutations can be also implemented efficiently on quantum computers, e.g. a NOT gate on a qubit. In this paper, using permutation matrices and qubit measurements, we show how to solve blockmodeling on quantum computers. In the model, the measurement outcomes of a small group of qubits are mapped to indicate the fitness value. However, if the number of qubits in the considered group is much less than $n=log(N)$, it is possible to find or update the fitness value based on the state tomography in $O(poly(log(N)))$. Therefore, when the number of iterations is less than $log(N)$ time and the size of the considered qubit group is small, we show that it may be possible to reach the solution very efficiently.
- Abstract（参考訳）: 与えられた問題のブロックモデリングを$N\times N$ adjacency matrix で表し、行列の行と列(行列を左右に置換行列で乗算する)を交換することによって見つけることができる。
古典行列の置換は、行列の置換行(または列)に対してポインタをスワップすることで効率的に行うことができるが、行列順を変更することで、置換は行列要素の位置を変化させ、行列ベースのブロックモデリングにおけるグループのメンバシップを決定する。
したがって、要素のメンバシップを数えることのできる候補解に対する適合値の初期推定は、行(または列)の総和を通り抜ける必要がある。
同様に置換は量子コンピュータ、例えば量子ビット上のNOTゲートでも効率的に実装できる。
本稿では、置換行列と量子ビット測定を用いて、量子コンピュータにおけるブロックモデリングの解法を示す。
モデルでは、小さな量子ビットのグループの測定結果が、適合度値を示すためにマッピングされる。
しかし、検討されたグループ内のキュービットの数が$n=log(N)$よりはるかに少ない場合、$O(poly(log(N))$の状態トモグラフィーに基づいてフィットネス値を検索または更新することができる。
したがって、繰り返し回数が$log(N)$時間未満で、検討されたキュービット群のサイズが小さい場合には、解に非常に効率的に到達できることが示される。
関連論文リスト
- Kissing to Find a Match: Efficient Low-Rank Permutation Representation [33.880247068298374]
そこで本稿では,低ランク行列係数化を用いて近似し,次いで非線形性を用いて,大きな置換行列の次元性の呪いに取り組むことを提案する。
提案手法の適用性とメリットを,様々な問題に対する一連の実験を通じて実証する。
論文 参考訳（メタデータ） (2023-08-25T08:59:03Z) - Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations
by QUBO and Ising Models with Quadratic Sizes [0.14454647768189902]
本稿では、二重行列ドメインウォールと呼ばれる新しい置換符号化手法を提案する。
これは、カーネル内の二次項の数と最大絶対係数値を著しく減少させる。
また、部分置換と準非制約バイナリ最適化(QUBO)モデルへの符号化手法の適用性を実証する。
論文 参考訳（メタデータ） (2023-08-02T09:15:30Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
本稿では,行列関数からのサンプリング作業のためのランダム化量子アルゴリズムのクラスを提案する。
量子ビットの使用は純粋にアルゴリズムであり、量子データ構造には追加の量子ビットは必要ない。
論文 参考訳（メタデータ） (2023-02-03T17:22:49Z) - A quantum algorithm for solving eigenproblem of the Laplacian matrix of
a fully connected weighted graph [4.045204834863644]
完全連結重み付きグラフのラプラシア行列の固有確率を解くための効率的な量子アルゴリズムを提案する。
具体的には,ブロック符号化フレームワークに基づく最適ハミルトンシミュレーション手法を採用する。
また、このアルゴリズムは対称(非対称)正規化ラプラス行列の固有確率を解くために拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-03-28T02:24:08Z) - Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
本稿では,「Sender-Receiver」モデルを用いた行列演算のための量子アルゴリズムを提案する。
これらの量子プロトコルは、他の量子スキームのサブルーチンとして使用できる。
論文 参考訳（メタデータ） (2022-02-10T08:12:20Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - On the Expressive Power of Self-Attention Matrices [41.72598286888797]
固定自己アテンションモジュールは入力に応じて任意のスパースパターンを近似することができることを示す。
行列を近似するために適応的な入力と固定された自己アテンションパラメータを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-07T16:30:28Z) - A Practical Method for Constructing Equivariant Multilayer Perceptrons
for Arbitrary Matrix Groups [115.58550697886987]
行列群の同変層を解くための完全一般的なアルゴリズムを提供する。
他作品からのソリューションを特殊ケースとして回収するだけでなく、これまで取り組んだことのない複数のグループと等価な多層パーセプトロンを構築します。
提案手法は, 粒子物理学および力学系への応用により, 非同変基底線より優れる。
論文 参考訳（メタデータ） (2021-04-19T17:21:54Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。