論文の概要: Quantum algorithms for computational geometry problems
- arxiv url: http://arxiv.org/abs/2004.08949v1
- Date: Sun, 19 Apr 2020 20:01:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-23 00:48:36.769463
- Title: Quantum algorithms for computational geometry problems
- Title（参考訳）: 計算幾何学問題に対する量子アルゴリズム
- Authors: Andris Ambainis and Nikita Larka
- Abstract要約: 計算幾何学における問題(POINT-ON-3-LINES問題など)について量子アルゴリズムについて検討する。
我々は、POINT-ON-3-LINESを時間$O(n1 + o(1))$で解く量子アルゴリズムを構築する。
同じアイデアが、多くの3SUM-HARD幾何学的問題に対して$O(n1 + o(1))$Timeアルゴリズムを与えることを示す。
- 参考スコア（独自算出の注目度）: 1.2944868613449219
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study quantum algorithms for problems in computational geometry, such as
POINT-ON-3-LINES problem. In this problem, we are given a set of lines and we
are asked to find a point that lies on at least $3$ of these lines.
POINT-ON-3-LINES and many other computational geometry problems are known to be
3SUM-HARD. That is, solving them classically requires time
$\Omega(n^{2-o(1)})$, unless there is faster algorithm for the well known 3SUM
problem (in which we are given a set $S$ of $n$ integers and have to determine
if there are $a, b, c \in S$ such that $a + b + c = 0$). Quantumly, 3SUM can be
solved in time $O(n \log n)$ using Grover's quantum search algorithm. This
leads to a question: can we solve POINT-ON-3-LINES and other 3SUM-HARD problems
in $O(n^c)$ time quantumly, for $c<2$? We answer this question affirmatively,
by constructing a quantum algorithm that solves POINT-ON-3-LINES in time
$O(n^{1 + o(1)})$. The algorithm combines recursive use of amplitude
amplification with geometrical ideas. We show that the same ideas give $O(n^{1
+ o(1)})$ time algorithm for many 3SUM-HARD geometrical problems.
- Abstract（参考訳）: 計算幾何学における問題,例えばポイントオン-3-ライン問題について量子アルゴリズムを研究した。
この問題では、一組のラインが与えられ、これらのラインのうち少なくとも3ドル以上のポイントを見つけるように求められます。
POINT-ON-3-LINESや他の多くの計算幾何学問題は3SUM-HARDとして知られている。
つまり、これらを古典的に解くには時間$\Omega(n^{2-o(1)})$が必要であり、よく知られた3SUM問題のより高速なアルゴリズムがなければ(ここでは、$S$ of $n$整数が与えられ、$a + b + c = 0$となるような$a, b, c \in S$が存在するかどうかを判断しなければならない)。
3SUMはGroverの量子探索アルゴリズムを用いて時間$O(n \log n)$で解くことができる。
POINT-ON-3-LINES や他の 3SUM-HARD 問題を$O(n^c)$ time, for $c<2$?
我々は、時間$O(n^{1 + o(1)})$でPOINT-ON-3-LINESを解く量子アルゴリズムを構築することで、この質問に答える。
このアルゴリズムは振幅増幅の再帰的利用と幾何学的アイデアを組み合わせたものである。
同じアイデアが多くの3サムハード幾何問題に対して$o(n^{1 + o(1)})$ timeアルゴリズムを与えることを示した。
関連論文リスト
- Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。
得られた解法は数値的に安定かつ高速であることを示す。
論文 参考訳（メタデータ） (2024-04-25T12:09:16Z) - 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) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
論文 参考訳（メタデータ） (2023-12-05T21:15:09Z) - Using 1-Factorization from Graph Theory for Quantum Speedups on Clique
Problems [0.0]
完全グラフの一因子化に基づく新しい量子オラクル設計を提供する。
また、Triangle Findingの時間複雑性を$O(n2.25 poly(log n))$に下げる際の、これらのオラクルの1つの利用についても論じる。
論文 参考訳（メタデータ） (2023-08-31T15:59:35Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-28T18:12:54Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Matching Triangles and Triangle Collection: Hardness based on a Weak
Quantum Conjecture [0.8924669503280332]
これら2つのグラフ問題のいずれかに対する$n1.5-epsilon$の時間量子アルゴリズムは、k-SAT, 3SUM, APSPの量子アルゴリズムを高速化することを示す。
また、データ構造とアムバイニスの変動時間探索を慎重に利用する必要がある量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-22T13:16:50Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。