論文の概要: Quantum Computers Can Find Quadratic Nonresidues in Deterministic
Polynomial Time
- arxiv url: http://arxiv.org/abs/2106.03991v1
- Date: Mon, 7 Jun 2021 22:22:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-27 08:37:58.711780
- Title: Quantum Computers Can Find Quadratic Nonresidues in Deterministic
Polynomial Time
- Title(参考訳): 量子コンピュータは決定論的多項式時間で二次非正則を見つけることができる
- Authors: Thomas G. Draper
- Abstract要約: 整数 $a$ が素数 $p$ の二次的非残留であるとき、$x2 equiv a modb p$ は解を持たない。
決定論的時間で二次的非残留を生成する量子アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: An integer $a$ is a quadratic nonresidue for a prime $p$ if $x^2 \equiv a
\bmod p$ has no solution. Quadratic nonresidues may be found by probabilistic
methods in polynomial time. However, without assuming the Generalized Riemann
Hypothesis, no deterministic polynomial-time algorithm is known. We present a
quantum algorithm which generates a random quadratic nonresidue in
deterministic polynomial time.
- Abstract(参考訳): 整数 $a$ は素数 $p$ に対する二次非正則で、$x^2 \equiv a \bmod p$ は解を持たない。
二次的非残留は多項式時間における確率的方法によって見つかる。
しかし、一般リーマン仮説を仮定することなく、決定論的多項式時間アルゴリズムは知られていない。
決定論的多項式時間でランダムな二次不一致を生成する量子アルゴリズムを提案する。
関連論文リスト
- Quadratic Speed-up in Infinite Variance Quantum Monte Carlo [1.2891210250935148]
我々はモンタナロのarXiv/archive:1504.06987量子モンテカルロ法の拡張を与える。
無限分散を示す確率変数の期待値を計算するために調整されている。
論文 参考訳(メタデータ) (2024-01-15T06:31:36Z) - 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) - Quantum Speedups for Bayesian Network Structure Learning [0.0]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。
近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。
我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
論文 参考訳(メタデータ) (2023-05-31T09:15:28Z) - Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。
ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文 参考訳(メタデータ) (2023-03-03T16:53:30Z) - Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer [0.20999222360659603]
いくつかの量子SDOソルバは、低精度な状態において高速化を提供する。
この事実を利用してアルゴリズムの精度への依存を指数関数的に改善する。
我々のアルゴリズムの量子実装は、$mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$の最悪の実行時間を示す。
論文 参考訳(メタデータ) (2023-01-10T23:12:05Z) - 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) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model [0.0]
2次時間分解可能問題のビット並列性を、係数$n$でスピードアップできる量子アルゴリズムに変換する方法を示す。
まず、Myers (J. ACM, 1999) の有名な$O(n2/w)$ time bit-parallel アルゴリズムが算術+演算なしで動作するように調整可能であることを示す。
論文 参考訳(メタデータ) (2021-12-24T09:26:55Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - Quantum algorithms for spectral sums [79.28094304325116]
対称正定値行列(SPD)の最も一般的なスペクトル和を推定するための新しい量子アルゴリズムを提案し,解析する。
関数 $f$ と行列 $A に対して、スペクトル和は $S_f(A) :=textTr[f(A)] = sum_j f(lambda_j)$, ここで $lambda_j$ は固有値である。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z) - On the complexity of finding a local minimizer of a quadratic function
over a polytope [1.0048921884287543]
P=NPがなければ、ポリトープ上の$n$2次関数の局所最小値の$cn$以内の点を見つけるユークリッド時間アルゴリズムは存在しない。
また,2次関数が非有界ポリヘドロン上の局所最小値を持つか否か,およびクォートが局所最小値を持つか否かを判定する問題も示唆している。
論文 参考訳(メタデータ) (2020-08-12T20:09:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。