論文の概要: Quantum Complexity of Permutations
- arxiv url: http://arxiv.org/abs/2207.14102v2
- Date: Fri, 12 Aug 2022 11:45:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-04 05:15:13.171080
- Title: Quantum Complexity of Permutations
- Title(参考訳): 置換の量子複雑性
- Authors: Andrew Yu
- Abstract要約: 論理ゲートとして$sigma, tau, tau-1$を用いて, 置換の量子複雑性について検討した。
我々は、$S_n$ のほとんどすべての置換が、$nrightarrow infty$ のときの2次量子複雑性を下限とすることを示した。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Let $S_n$ be the symmetric group of all permutations of $\{1, \cdots, n\}$
with two generators: the transposition switching $1$ with $2$ and the cyclic
permutation sending $k$ to $k+1$ for $1\leq k\leq n-1$ and $n$ to $1$ (denoted
by $\sigma$ and $\tau$). In this article, we study quantum complexity of
permutations in $S_n$ using $\{\sigma, \tau, \tau^{-1}\}$ as logic gates. We
give an explicit construction of permutations in $S_n$ with quadratic quantum
complexity lower bound $\frac{n^2-2n-7}{4}$. We also prove that all
permutations in $S_n$ have quadratic quantum complexity upper bound $3(n-1)^2$.
Finally, we show that almost all permutations in $S_n$ have quadratic quantum
complexity lower bound when $n\rightarrow \infty$.
- Abstract(参考訳): 2つのジェネレータを持つ$\{1, \cdots, n\}$ のすべての置換の対称群を$s_n$ とすると、変換は$$$$ で、巡回置換は$k$から$k+1$ で$\leq k\leq n-1$ と $n$から$$$$$ となる($\sigma$ と $\tau$ で示される)。
本稿では、論理ゲートとして$\{\sigma, \tau, \tau^{-1}\}$を用いて、置換の量子複雑性を$s_n$で研究する。
二次量子複雑性を持つ$s_n$ の置換を明示的に構成し、$\frac{n^2-2n-7}{4}$ とする。
また、S_n$ のすべての置換が2次量子複雑性上界 3(n-1)^2$ を持つことを示す。
最後に、$S_n$ のほとんどすべての置換は、$n\rightarrow \infty$ のときの二次量子複雑性が下界であることを示す。
関連論文リスト
- An Efficient Quantum Circuit Construction Method for Mutually Unbiased
Bases in $n$-Qubit Systems [0.3955651218777455]
2n+1$の相互バイアスのないベース(MUB)を$O(n3)$時間複雑性を持つ$n$量子ビットシステムで生成できる回路。
絡み合う部分の固定加群は2n-3$で、非自明な回路はいくつかの興味深い線形関係を満たす。
論文 参考訳(メタデータ) (2023-11-20T12:00:41Z) - 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) - On the moments of random quantum circuits and robust quantum complexity [0.0]
我々は、ロバスト量子回路の複雑さの増大に新たな低い境界を証明した。
局所ゲートを持つランダム量子回路に対して、$SU(4)$の部分群から引き出された2つの境界を示す。
論文 参考訳(メタデータ) (2023-03-29T18:06:03Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$ [0.0]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳(メタデータ) (2023-03-20T08:17:32Z) - Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。
偏光理論への我々の結果の即時適用について述べる。
論文 参考訳(メタデータ) (2022-05-30T18:01:34Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳(メタデータ) (2022-04-22T12:37:56Z) - Optimal (controlled) quantum state preparation and improved unitary
synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。
我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文 参考訳(メタデータ) (2022-02-23T04:19:57Z) - 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) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳(メタデータ) (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。