کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435543 | 689914 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Quantum algorithms for finding constant-sized sub-hypergraphs
ترجمه فارسی عنوان
الگوریتم های کوانتومی برای پیدا کردن زیرپراگراف های ثابت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های کوانتومی، هیپوگرافی، پیاده روی کوانتومی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We develop a general framework to construct quantum algorithms that detect if a 3-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a prespecified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez (2013) [12], and extends the methodology designed by Lee, Magniez and Santha (2013) [18] for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a 4-clique in a 3-uniform hypergraph on n vertices with query complexity O(n1.883)O(n1.883), and a quantum algorithm for determining if a ternary operator over a set of size n is associative with query complexity O(n2.113)O(n2.113).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 609, Part 3, 4 January 2016, Pages 569–582
Journal: Theoretical Computer Science - Volume 609, Part 3, 4 January 2016, Pages 569–582
نویسندگان
François Le Gall, Harumichi Nishimura, Seiichiro Tani,