Fugu-MT 論文翻訳(概要): Quantum Computers Can Find Quadratic Nonresidues in Deterministic Polynomial Time

論文の概要: 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$ は解を持たない。二次的非残留は多項式時間における確率的方法によって見つかる。しかし、一般リーマン仮説を仮定することなく、決定論的多項式時間アルゴリズムは知られていない。決定論的多項式時間でランダムな二次不一致を生成する量子アルゴリズムを提案する。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms [0.0]
2023年、レジチェフはショアのアルゴリズムの多次元バージョンを提案し、より少ない量子ゲートを必要とした。解析的数論の道具を用いて、この予想のバージョンを証明する。その結果、この改良された量子アルゴリズムの正確性の無条件証明が得られる。
論文参考訳（メタデータ） (2024-04-25T09:30:19Z)
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)
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)
Near-term quantum algorithm for computing molecular and materials properties based on recursive variational series methods [44.99833362998488]
本稿では,分子の特性を短期量子デバイスを用いて推定する量子アルゴリズムを提案する。エネルギー領域における一粒子グリーン関数と時間領域における自己相関関数を計算し,本手法を検証した。
論文参考訳（メタデータ） (2022-06-20T16:33:23Z)
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)
Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文参考訳（メタデータ） (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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。