Span-program-based quantum algorithm for evaluating formulas
From MaRDI portal
Abstract: 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.
Recommendations
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- Faster quantum algorithm for evaluating game trees
- Span programs are equivalent to quantum query algorithms
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- The quantum query complexity of read-many formulas
Cites work
Cited in
(19)- Quantum algorithm design: techniques and applications
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Approximate span programs
- Superlinear advantage for exact quantum algorithms
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Span programs are equivalent to quantum query algorithms
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- New developments in quantum algorithms
- Approximate span programs
- Quantum algorithms for connectivity and related problems
- scientific article; zbMATH DE number 7559397 (Why is no real title available?)
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Faster quantum algorithm for evaluating game trees
- Quantum Algorithms for Evaluating Min-Max Trees
- On the relationship between continuous- and discrete-time quantum walk
- A direct reduction from the polynomial to the adversary method
- Quantum lower bounds by sample-to-query lifting
- Approximate degree composition for recursive functions
- Multidimensional quantum walks, recursion, and quantum divide \& conquer
This page was built for publication: Span-program-based quantum algorithm for evaluating formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913813)
