Physics – Quantum Physics
Scientific paper
2007-10-14
Extended abstract in Proc. 40th ACM Symp. on Theory of Computing (STOC), 2008, pages 103-112
Physics
Quantum Physics
42 pages, new appendix on four-bit functions
Scientific paper
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 gate's 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 program's 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.
Reichardt Ben W.
Spalek Robert
No associations
LandOfFree
Span-program-based quantum algorithm for evaluating formulas does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Span-program-based quantum algorithm for evaluating formulas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Span-program-based quantum algorithm for evaluating formulas will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-125869