論文の概要: Solving graph problems with single-photons and linear optics
- arxiv url: http://arxiv.org/abs/2301.09594v1
- Date: Mon, 23 Jan 2023 17:48:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-24 12:48:28.540888
- Title: Solving graph problems with single-photons and linear optics
- Title(参考訳): 単光子と線形光学によるグラフ問題の解法
- Authors: Rawad Mezher, Ana Filipa Carvalho, Shane Mansfield
- Abstract要約: 有界な$n×n$行列$A$を2n$モードの線形光回路に効率よく符号化する方法を示す。
単光子源、$A$を符号化する線形光回路、および単光子検出器からなるフォトニック量子プロセッサは、様々なグラフ問題を解くことができる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An important challenge for current and near-term quantum devices is finding
useful tasks that can be preformed on them. We first show how to efficiently
encode a bounded $n \times n$ matrix $A$ into a linear optical circuit with
$2n$ modes. We then apply this encoding to the case where $A$ is a matrix
containing information about a graph $G$. We show that a photonic quantum
processor consisting of single-photon sources, a linear optical circuit
encoding $A$, and single-photon detectors can solve a range of graph problems
including finding the number of perfect matchings of bipartite graphs,
computing permanental polynomials, determining whether two graphs are
isomorphic, and the $k$-densest subgraph problem. We also propose
pre-processing methods to boost the probabilities of observing the relevant
detection events and thus improve performance. Finally, we present various
numerical simulations which validate our findings.
- Abstract(参考訳): 現状と短期の量子デバイスにとって重要な課題は、それらをプリフォームできる有用なタスクを見つけることである。
まず、有界な$n \times n$ matrix $a$を2n$モードの線形光回路に効率的にエンコードする方法を示す。
次に、このエンコーディングを、$A$ がグラフ $G$ に関する情報を含む行列である場合に適用する。
単光子源からなるフォトニック量子プロセッサ、$A$を符号化する線形光回路、および単光子検出器により、2部グラフの完全マッチング数、永久多項式の計算、2つのグラフが同型かどうか、および$k$dsestサブグラフ問題などのグラフ問題を解くことができることを示す。
また,検出イベントの観測可能性を高め,性能を向上させるための前処理手法を提案する。
最後に, 実験結果を検証する数値シミュレーションを行った。
関連論文リスト
- Sample efficient graph classification using binary Gaussian boson
sampling [0.0]
本稿では,グラフ構造化データを用いた機械学習タスクにおける量子アルゴリズムの変形について述べる。
我々の装置は、光子数分解検出器とは対照的に、バイナリ(光/光)検出器のみを必要とする。
論文 参考訳(メタデータ) (2023-01-03T17:23:43Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳(メタデータ) (2022-07-09T09:14:12Z) - The complexity of quantum support vector machines [3.8998241153792454]
量子サポートベクトルマシンは、カーネル関数を定義するために量子回路を使用する。
我々は、カーネル化された原始問題は、ペガソスと呼ばれる既知の古典的アルゴリズムの一般化を用いて、$mathcalO(min M2, varepsilon6, 1/varepsilon10 )$評価で解けるという経験的な仮定の下で証明する。
論文 参考訳(メタデータ) (2022-02-28T19:01:17Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳(メタデータ) (2021-09-17T17:46:12Z) - Recurrently Predicting Hypergraphs [30.092688729343678]
問題は、$n$要素の集合に対して$mathcalO(2n)$でスケーリング可能なマルチウェイ関係(ハイパーエッジ)の数から生じる。
そこで本研究では,提案手法の初期推定を反復的に精算することにより,入射行列を予測する再帰型ハイパーグラフニューラルネットワークを提案する。
論文 参考訳(メタデータ) (2021-06-26T01:12:41Z) - SGL: Spectral Graph Learning from Measurements [4.721069729610892]
この研究は、線形測定で抵抗ネットワークを学習するための高度にスケーラブルなスペクトルグラフ密度化フレームワークを導入する。
提案手法は,ソリューション品質を犠牲にすることなく,超スパース抵抗ネットワークを学習するための拡張性が高いことを示す。
論文 参考訳(メタデータ) (2021-04-16T03:01:15Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized
Optimization [77.57736777744934]
この論文は、広く使用されている加速勾配追跡を再検討し、拡張する。
私たちの複雑さは $cal O(frac1epsilon5/7)$ と $cal O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$ で大幅に改善します。
論文 参考訳(メタデータ) (2021-04-06T15:34:14Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-10-25T18:12:50Z) - Multiway $p$-spectral graph cuts on Grassmann manifolds [0.3441021278275805]
直接マルチウェイスペクトルクラスタリングアルゴリズムを$p$-norm, for $p in (1, 2]$で提案する。
グラフ $p$-Laplacian の多重固有ベクトルを計算する問題は、グラスマン多様体上の制約のない最小化問題として再キャストされる。
バランスの取れたグラフの単調な減少を監視することは、検討された$p$レベルから最高の解が得られることを保証します。
論文 参考訳(メタデータ) (2020-08-30T16:25:04Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。