論文の概要: A Simple Quantum Blockmodeling with Qubits and Permutations
- arxiv url: http://arxiv.org/abs/2311.07726v1
- Date: Mon, 13 Nov 2023 20:10:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-15 16:34:53.353551
- Title: A Simple Quantum Blockmodeling with Qubits and Permutations
- Title（参考訳）: 量子ビットと置換を用いた単純な量子ブロックモデリング
- Authors: Ammar Daskin
- Abstract要約: 量子コンピュータでは、置換を並列かつ効率的に適用することができる。
フィットネス値を$O(log(N))$ timeで見つけたり更新したりすることは可能である。
さらに、量子回路上で異なる置換列を並列に適用できるため、このモデルにおける機械学習タスクは量子コンピュータ上でより効率的に実装できる。
- 参考スコア（独自算出の注目度）: 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). In general,
through performing this task, row and column permutations affect the fitness
value in optimization: For an $N\times N$ matrix, it requires $O(N)$
computations to find (or update) the fitness value of a candidate solution.
On quantum computers, permutations can be applied in parallel and
efficiently, and their implementations can be as simple as a single qubit
operation (a NOT gate on a qubit) which takes an $O(1)$ time algorithmic step.
In this paper, using permutation matrices, we describe a quantum blockmodeling
for data analysis tasks. In the model, the measurement outcome of a small group
of qubits are mapped to indicate the fitness value. Therefore, we show that it
is possible to find or update the fitness value in $O(log(N))$ time. This lead
us to show that when the number of iterations are less than $log(N)$ time, it
may be possible to reach the same solution exponentially faster on quantum
computers in comparison to classical computers. In addition, since on quantum
circuits the different sequence of permutations can be applied in parallel
(superpositon), the machine learning task in this model can be implemented more
efficiently on quantum computers.
- Abstract（参考訳）: 与えられた問題のブロックモデリングを$N\times N$ adjacency matrix で表し、行列の行と列(行列を左右に置換行列で乗算する)を交換することによって見つけることができる。
一般に、このタスクを実行することで、行と列の置換が最適化の適合値に影響を与える:$N\times N$ matrixの場合、候補ソリューションの適合値を見つけ(または更新)するために$O(N)$計算が必要である。
量子コンピュータでは、置換は並列かつ効率的に適用でき、その実装は1量子ビット演算(量子ビット上のNOTゲート)のように単純で、O(1)$時間アルゴリズムのステップを踏むことができる。
本稿では,置換行列を用いて,データ解析タスクの量子ブロックモデリングについて述べる。
モデルでは、小グループの量子ビットの測定結果をマッピングして、適合値を示す。
したがって、$O(log(N))$timeでフィットネス値を検索または更新することが可能である。
これにより、繰り返し回数が$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。