کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657899 | 690385 | 2005 | 49 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Quantum branching programs and space-bounded nonuniform quantum complexity
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, the space complexity of non-uniform quantum algorithms is investigated using the model of quantum branching programs (QBPs). In order to clarify the relationship between QBPs and non-uniform quantum Turing machines, simulations between these two models are presented which allow to transfer upper and lower bound results. Exploiting additional insights about the connection between the running time and the precision of amplitudes, it is shown that non-uniform quantum Turing machines with algebraic amplitudes and QBPs with a suitable analogous set of amplitudes are equivalent in computational power if both models work with bounded or unbounded error. Furthermore, quantum ordered binary decision diagrams (QOBDDs) are considered, which are restricted QBPs that can be regarded as a non-uniform analog of one-way quantum finite automata. Upper and lower bounds are proved that allow a classification of the computational power of QOBDDs in comparison to usual deterministic and randomized variants of the model. Finally, an extension of QBPs is proposed where the performed unitary operation may depend on the result of a previous measurement. A simulation of randomized BPs by this generalized QBP model as well as exponential lower bounds for its ordered variant are presented.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 334, Issues 1â3, 15 April 2005, Pages 177-225
Journal: Theoretical Computer Science - Volume 334, Issues 1â3, 15 April 2005, Pages 177-225
نویسندگان
Martin Sauerhoff, Detlef Sieling,