We consider the quantumquery model for computing Boolean functions. 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 quantumquery model for computing Boolean functions. 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 Boolean function - 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.
In quantum computation, designing an optimal exact quantum query algorithm (i.e., a quantum decision tree algorithm) for any small input Boolean function is a fundamental and abstract problem. As we are aware, there i...
详细信息
In quantum computation, designing an optimal exact quantum query algorithm (i.e., a quantum decision tree algorithm) for any small input Boolean function is a fundamental and abstract problem. As we are aware, there is not a general method for this problem. Due to the fact that every Boolean function can be represented by a sum-of-squares of some multilinear polynomials, in this paper a primary algorithm framework is proposed with three basic steps: The first basic step is to find sum-of-squares representations of the Boolean function and its negation function;the second basic step is to construct a state which is assumed to be the final state of an optimal exact quantum query algorithm;the third basic step is to find each unitary operator in the undetermined algorithm. However, there still exist some intractable problems such that the algorithm framework may not be feasible in some cases, but it can be used to investigate the quantumquery model with low complexity, such as Deutsch's problem, a five-bit symmetric Boolean function and the characterization of Boolean functions with exact quantum 2-query complexity.
The general adversary bound is a semi-definite program (SDP) that lower-bounds the quantumquery complexity of a function. We turn this lower bound into an upper bound, by giving a quantum walk algorithm based on the ...
详细信息
ISBN:
(纸本)9780769538501
The general adversary bound is a semi-definite program (SDP) that lower-bounds the quantumquery complexity of a function. We turn this lower bound into an upper bound, by giving a quantum walk algorithm based on the dual SDP that has query complexity at most the general adversary bound, up to a logarithmic factor. In more detail, the proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give an SDP that outputs for any boolean function a span program computing it that has optimal " witness size." The optimal witness size is shown to coincide with the general adversary lower bound. Second, we give a quantumalgorithm for evaluating span programs with only a logarithmic query overhead on the witness size. The first result is motivated by a quantumalgorithm for evaluating composed span programs. The algorithm is known to be optimal for evaluating a large class of formulas. The allowed gates include all constant-size functions for which there is an optimal span program. So far, good span programs have been found in an ad hoc manner, and the SDP automates this procedure. Surprisingly, the SDP's value equals the general adversary bound. A corollary is an optimal quantumalgorithm for evaluating "balanced" formulas over any finite boolean gate set. The second result broadens span programs' applicability beyond the formula-evaluation problem. We extend the analysis of the quantumalgorithm for evaluating span programs. The previous analysis shows that a corresponding bipartite graph has a large spectral gap, but only works when applied to the composition of constant-size span programs. We show generally that properties of eigenvalue-zero eigenvectors in fact imply an "effective" spectral gap around zero. A strong universality result for span programs follows. A good quantum query algorithm for a problem implies a good span program, and vice versa. Although nearly tight, this equivalence is nontrivial. Span programs
The combination of contextual side information and search is a powerful paradigm in the scope of artificial intelligence. The prior knowledge enables the identification of possible solutions but may be imperfect. Cont...
详细信息
The combination of contextual side information and search is a powerful paradigm in the scope of artificial intelligence. The prior knowledge enables the identification of possible solutions but may be imperfect. Contextual information can arise naturally, for example in game AI where prior knowledge is used to bias move decisions. In this work we investigate the problem of taking quantum advantage of contextual information, especially searching with prior knowledge. We propose a new generalization of Grover's search algorithm that achieves the optimal expected success probability of finding the solution if the number of queries is fixed. Experiments on small-scale quantum circuits verify the advantage of our algorithm. Since contextual information exists widely, our method has wide applications. We take game tree search as an example.
The subtraction game is a well-known problem in the field of game theory, which is often called a one-heap Nim game. There are two players, a heap of tokens, and a strategy matrix, in this game. It is called a restric...
详细信息
The subtraction game is a well-known problem in the field of game theory, which is often called a one-heap Nim game. There are two players, a heap of tokens, and a strategy matrix, in this game. It is called a restricted subtraction game if some constraints are imposed on the strategy matrix. The subtraction game could be solved by a classical algorithm with a query complexity no less than O(N (2)) and computed by an O ( N 3 2 l o g N ) quantum query algorithm with an error probability epsilon & LE;1 N . The restricted subtraction game proposed by Huang et al. can be computed by an exact quantumalgorithm with O ( N 3 2 ) queries. They also proved that the classical exact query complexity is & UTheta;(N (2)). In this study, we use an array and an adjacency list to replace the strategy matrix and propose another more general subtraction game than the one introduced by Huang et al. Based on dynamic programming and the replaced game strategy, two linear classical queryalgorithms are designed to solve the restricted subtraction game proposed by Huang and this study, respectively.
暂无评论