論文の概要: Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem
- arxiv url: http://arxiv.org/abs/2306.05253v1
- Date: Thu, 8 Jun 2023 14:48:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-09 13:56:52.250555
- Title: Quantum computing algorithms for inverse problems on graphs and an
NP-complete inverse problem
- Title（参考訳）: グラフ上の逆問題に対する量子計算アルゴリズムとNP完全逆問題
- Authors: Joonas Ilmavirta, Matti Lassas, Jinpeng Lu, Lauri Oksanen, Lauri
Ylinen
- Abstract要約: 有限グラフ $(X,E)$ に対する逆問題を考える。
この問題には特定の条件下でのユニークな解法があることを示し、量子計算法を開発した。
- 参考スコア（独自算出の注目度）: 0.1259953341639576
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider an inverse problem for a finite graph $(X,E)$ where we are given
a subset of vertices $B\subset X$ and the distances $d_{(X,E)}(b_1,b_2)$ of all
vertices $b_1,b_2\in B$. The distance of points $x_1,x_2\in X$ is defined as
the minimal number of edges needed to connect two vertices, so all edges have
length 1. The inverse problem is a discrete version of the boundary rigidity
problem in Riemannian geometry or the inverse travel time problem in
geophysics. We will show that this problem has unique solution under certain
conditions and develop quantum computing methods to solve it. We prove the
following uniqueness result: when $(X,E)$ is a tree and $B$ is the set of
leaves of the tree, the graph $(X,E)$ can be uniquely determined in the class
of all graphs having a fixed number of vertices. We present a quantum computing
algorithm which produces a graph $(X,E)$, or one of those, which has a given
number of vertices and the required distances between vertices in $B$. To this
end we develop an algorithm that takes in a qubit representation of a graph and
combine it with Grover's search algorithm. The algorithm can be implemented
using only $O(|X|^2)$ qubits, the same order as the number of elements in the
adjacency matrix of $(X,E)$. It also has a quadratic improvement in
computational cost compared to standard classical algorithms. Finally, we
consider applications in theory of computation, and show that a slight
modification of the above inverse problem is NP-complete: all NP-problems can
be reduced to a discrete inverse problem we consider.
- Abstract（参考訳）: 有限グラフ $(x,e)$ の逆問題を考えると、頂点 $b\subset x$ の部分集合と距離 $d_{(x,e)}(b_1,b_2)$ のすべての頂点 $b_1,b_2\in b$ が与えられる。
点距離$x_1,x_2\in X$ は、2つの頂点を結ぶのに必要なエッジの最小数として定義される。
逆問題(英: inverse problem)とは、リーマン幾何学における境界剛性問題や地球物理学における逆旅行時間問題の離散版である。
この問題には特定の条件下でのユニークな解法があることを示し、それを解決するための量子コンピューティング手法を開発する。
例えば、$(x,e)$ が木であり、$b$ が木の葉の集合であるとき、グラフ $(x,e)$ は、一定の数の頂点を持つすべてのグラフのクラスにおいて一意的に決定できる。
グラフ$(X,E)$,あるいはそれらのうちの1つを生成する量子計算アルゴリズムについて,与えられた頂点数と頂点間の所要距離を$B$で表現する。
そこで我々はグラフの量子ビット表現を取り込んでグローバーの探索アルゴリズムと組み合わせるアルゴリズムを開発した。
このアルゴリズムは$O(|X|^2)$ qubitsだけで実装できるが、これは隣接行列の$(X,E)$の要素の数と同じ順序である。
また、従来のアルゴリズムに比べて計算コストが2倍に向上している。
最後に、計算理論の応用を考察し、上述の逆問題に対する若干の修正がNP完全であることを示し、全てのNPプロブレムを離散逆問題に還元することができる。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Quantum Speedup for the Maximum Cut Problem [6.588073742048931]
古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。
NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
論文 参考訳（メタデータ） (2023-05-26T05:31:25Z) - The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
量子回路におけるパターンマッチングを同時に行うアルゴリズムを提案する。
量子回路の場合、量子ビットの最大数から得られる境界を表現することができる。
論文 参考訳（メタデータ） (2023-02-13T22:09:02Z) - Quantum Algorithm for Dynamic Programming Approach for DAGs and
Applications [0.0]
有向非巡回グラフ(DAG)問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。
OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
論文 参考訳（メタデータ） (2022-12-29T19:07:39Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。
グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
論文 参考訳（メタデータ） (2021-07-29T20:37:28Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。