Fugu-MT 論文翻訳(概要): A new quantum algorithm for the hidden shift problem in $\mathbb{Z}

論文の概要: A new quantum algorithm for the hidden shift problem in $\mathbb{Z}_{2^t}^n$

arxiv url: http://arxiv.org/abs/2102.04171v1
Date: Mon, 8 Feb 2021 13:01:33 GMT
ステータス: 処理完了
システム内更新日: 2023-04-12 05:24:54.952462
Title: A new quantum algorithm for the hidden shift problem in $\mathbb{Z}_{2^t}^n$
Title（参考訳）: $\mathbb{Z}_{2^t}^n$における隠れシフト問題に対する新しい量子アルゴリズム
Authors: Gergely Cs\'aji
Abstract要約: k$が2のパワーであり、$nlog (k) で実行されている場合の解決策を提供します。一般的には、隠れたシフトや隠れた問題にも役立ちます。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: In this paper we make a step towards a time and space efficient algorithm for the hidden shift problem for groups of the form $\mathbb{Z}_k^n$. We give a solution to the case when $k$ is a power of 2, which has polynomial running time in $n$, and only uses quadratic classical, and linear quantum space in $n\log (k)$. It can be a useful tool in the general case of the hidden shift and hidden subgroup problems too, since one of the main algorithms made to solve them can use this algorithm as a subroutine in its recursive steps, making it more efficient in some instances.
Abstract（参考訳）: 本稿では,$\mathbb{z}_k^n$ という形の群に対する隠れシフト問題に対する時間と空間の効率的なアルゴリズムへの一歩を踏み出す。 k$ が 2 の力であるときの解は、多項式が $n$ で走る時間を持ち、二進古典的、線型量子空間が $n\log (k)$ でしか使われないものである。隠されたシフトや隠されたサブグループの問題の一般的な場合においても有用なツールであり、このアルゴリズムを再帰的なステップでサブルーチンとして使用できるため、いくつかのケースではより効率的である。

関連論文リスト

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)
Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
我々は,ゼロアンシラ量子ビットを用いた準四進時間量子乗法の新しいパラダイムを導入する。関連するキュービットは入力と出力レジスタ自身のみである。我々のアルゴリズムは、実際的な問題の大きさよりも優れている可能性がある。
論文参考訳（メタデータ） (2024-03-26T18:00:03Z)
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)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
An Efficient Quantum Factoring Algorithm [0.27195102129094995]
我々は、$tildeO(n3/2)$の量子回路を独立に実行することで、$n$bit整数を分解できることを示した。アルゴリズムの正しさは、指数的古典的因数分解アルゴリズムで使われるものに似た数論的な仮定に依存する。
論文参考訳（メタデータ） (2023-08-12T13:57:38Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
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)
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)
A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem [1.189332466445755]
我々は、$mathbbD_2n$上の隠れ部分群問題に対する時空量子アルゴリズムを提案する。問題のコドメインにエンコードされた構造に着目して、隠れた部分群で$mathbbD_2n$終了する部分群格子を「ウォーク」するアルゴリズムを開発する。
論文参考訳（メタデータ） (2022-02-19T23:51:15Z)
A polynomial time and space heuristic algorithm for T-count [2.28438857884398]
この研究は、最先端のフォールトトレラントな量子エラー訂正符号を使用する場合の量子アルゴリズム実装の物理的コストの低減に重点を置いている。普遍ゲート集合であるクリフォード+Tゲート集合からなる量子回路によって正確に実装できるユニタリ群を考える。
論文参考訳（メタデータ） (2020-06-22T17:21:41Z)

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