اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدQuantum computational algorithm for hidden symmetry subgroup problems on semi-direct product of cyclic groups
61
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We characterize the algebraic structure of semi-direct product of cyclic groups, $Z_{N}rtimesZ_{p}$, where $p$ is an odd prime number which does not divide $q-1$ for any prime factor $q$ of $N$, and provide a polynomial-time quantum computational algorithm solving hidden symmetry subgroup problem of the groups.
قيم البحث
اقرأ أيضاً
The generalized wreath product of permutation groups is introduced. By means of it we study the schurity problem for S-rings over a cyclic group $G$ and the automorphism groups of them. Criteria for the schurity and non-schurity of the generalized wr
eath product of two such S-rings are obtained. As a byproduct of the developed theory we prove that $G$ is a Schur group whenever the total number $Omega(n)$ of prime factors of the integer $n=|G|$ is at most 3. Moreover, we describe the structure of a non-schurian S-ring over $G$ when $Omega(n)=4$. The latter result implies in particular that if $n=p^3q$ where $p$ and $q$ are primes, then $G$ is a Schur group.
This paper addresses a decision problem highlighted by Grigorchuk, Nekrashevich, and Sushchanskii, namely the finiteness problem for automaton (semi)groups. For semigroups, we give an effective sufficient but not necessary condition for finiteness
and, for groups, an effective necessary but not sufficient condition. The efficiency of the new criteria is demonstrated by testing all Mealy automata with small stateset and alphabet. Finally, for groups, we provide a necessary and sufficient condition that does not directly lead to a decision procedure.
Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structure of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shif
t structure has received far less attention in the context of quantum computation. In this paper, we present three examples of ``unknown shift problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.
We give an algorithm to solve the quantum hidden subgroup problem for maximal cyclic non-normal subgroups of the affine group of a finite field (if the field has order $q$ then the group has order $q(q-1)$) with probability $1-varepsilon$ with (polyl
og) complexity $O(log(q)^{R}log(varepsilon)^{2})$ where $R<infty.$
A subset $B$ of an Abelian group $G$ is called a difference basis of $G$ if each element $gin G$ can be written as the difference $g=a-b$ of some elements $a,bin B$. The smallest cardinality $|B|$ of a difference basis $Bsubset G$ is called the diffe
rence size of $G$ and is denoted by $Delta[G]$. We prove that for every $ninmathbb N$ the cyclic group $C_n$ of order $n$ has difference size $frac{1+sqrt{4|n|-3}}2le Delta[C_n]lefrac32sqrt{n}$. If $nge 9$ (and $nge 2cdot 10^{15}$), then $Delta[C_n]lefrac{12}{sqrt{73}}sqrt{n}$ (and $Delta[C_n]<frac2{sqrt{3}}sqrt{n}$). Also we calculate the difference sizes of all cyclic groups of cardinality $le 100$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
