We consider the quantum query model for computingbooleanfunctions. The definition of the function is known, but a black box contains the input X=(x(1), x(2), ..., x(n)). Black box can be accessed by querying xi valu...
详细信息
ISBN:
(纸本)9781424481262
We consider the quantum query model for computingbooleanfunctions. The definition of the function is known, but a black box contains the input X=(x(1), x(2), ..., x(n)). Black box can be accessed by querying xi values. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic booleanfunction - logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probability in the classical model, two queries are necessary. We analyze algorithms implementation differences and propose a way to extend the first algorithm to compute AND of two functions.
暂无评论