ﻻ يوجد ملخص باللغة العربية
We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority). The algorithm is optimal on read-once formulas for which each gates inputs are balanced in a certain sense. The main new tool is a correspondence between a classical linear-algebraic model of computation, span programs, and weighted bipartite graphs. A span programs evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. A quantum computer can therefore evaluate the span program by applying spectral estimation to the graph. For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of randomized alpha-beta pruning is known to be suboptimal. In contrast, our algorithm generalizes the optimal quantum AND-OR formula evaluation algorithm and is optimal for evaluating the balanced ternary majority formula.
We provide several formulas that determine the optimal number of entangled bits (ebits) that a general entanglement-assisted quantum code requires. Our first theorem gives a formula that applies to an arbitrary entanglement-assisted block code. Corol
We question whether the measurement based quantum computing algorithm is in fact Grovers algorithm or simply a similar oracular search method. The two algorithms share several qualitative features especially in the case of the trivial 4 element searc
The stored-program architecture is canonical in classical computing, while its power has not been fully recognized for the quantum case. We study quantum information processing with stored quantum program states, i.e., using qubits instead of bits to
We present a bounded-error quantum algorithm for evaluating Min-Max trees. For a tree of size N our algorithm makes N^{1/2+o(1)} comparison queries, which is close to the optimal complexity for this problem.
We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n ad