اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA note about claw function with a small range
200
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In the claw detection problem we are given two functions $f:Drightarrow R$ and $g:Drightarrow R$ ($|D|=n$, $|R|=k$), and we have to determine if there is exist $x,yin D$ such that $f(x)=g(y)$. We show that the quantum query complexity of this problem is between $Omegaleft(n^{1/2}k^{1/6}right)$ and $Oleft(n^{1/2+varepsilon}k^{1/4}right)$ when $2leq k<n$.
قيم البحث
اقرأ أيضاً
A emph{$k$--bisection} of a bridgeless cubic graph $G$ is a $2$--colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes have order at most $k$
. Ban and Linial conjectured that {em every bridgeless cubic graph admits a $2$--bisection except for the Petersen graph}. In this note, we prove Ban--Linials conjecture for claw--free cubic graphs.
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a $k$-Fourier-sparse $n$-bit Boolean function from $O(k^{1.5}(log k)^2)$ uniform quantum examples for that function. This improves over the boun
d of $widetilde{Theta}(kn)$ uniformly random classical examples (Haviv and Regev, CCC15). Our main tool is an improvement of Changs lemma for the special case of sparse functions. Second, we show that if a concept class $mathcal{C}$ can be exactly learned using $Q$ quantum membership queries, then it can also be learned using $Oleft(frac{Q^2}{log Q}log|mathcal{C}|right)$ classical membership queries. This improves the previous-best simulation result (Servedio and Gortler, SICOMP04) by a $log Q$-factor.
Function inversion is the problem that given a random function $f: [M] to [N]$, we want to find pre-image of any image $f^{-1}(y)$ in time $T$. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary in
formation or advice of size $S$ that only depends on $f$ but not on $y$. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grovers algorithm, which does not leverage the power of preprocessing. Nayebi et al. proved a lower bound $ST^2 ge tildeOmega(N)$ for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where $M = O(N)$. In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al., to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest.
In the article [Petojevic 2006], A. Petojevi c verified useful properties of the $K_{i}(z)$ functions which generalize Kurepas [Kurepa 1971] left factorial function. In this note, we present simplified proofs of two of these results and we answer the
open question stated in [Petojevic 2006]. Finally, we discuss the differential transcendency of the $K_{i}(z)$ functions.
We present a model of two-kinks resulting from an explicit composition of two standards kinks of the $phi^4$ model based on the procedure of Ref. cite{uchiyama}. The two-kinks have an additional parameter accounting for the separation of the standard
kinks of $phi^4$ model. We have shown that the two-kinks have two discrete internal modes besides the zeroth mode and the continuous spectrum. This new feature signalizes that the head-on collision a two-kinks/two-antikinks pair exhibits a rich and complex behavior due to the additional channel from which the energy of the system can be stored. We have exhibited the fractal structure associated with the main configurations after the collision. We have inferred the fractality as the imprint of the nonlinear exchange of energy into the two discrete internal modes.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
