Span-program-based quantum algorithm for evaluating unbalanced formulas
From MaRDI portal
Abstract: The formula-evaluation problem is defined recursively. A formula's evaluation is the evaluation of a gate, the inputs of which are themselves independent formulas. Despite this pure recursive structure, the problem is combinatorially difficult for classical computers. A quantum algorithm is given to evaluate formulas over any finite boolean gate set. Provided that the complexities of the input subformulas to any gate differ by at most a constant factor, the algorithm has optimal query complexity. After efficient preprocessing, it is nearly time optimal. The algorithm is derived using the span program framework. It corresponds to the composition of the individual span programs for each gate in the formula. Thus the algorithm's structure reflects the formula's recursive structure.
Recommendations
- Span-program-based quantum algorithm for evaluating formulas
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Faster quantum algorithm for evaluating game trees
- The quantum query complexity of read-many formulas
- Reflections for quantum query algorithms
Cites work
- A lower bound on the quantum query complexity of read-once functions
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- Efficient circuits for quantum walks
- Faster quantum algorithm for evaluating game trees
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 5899233 (Why is no real title available?)
- scientific article; zbMATH DE number 5899240 (Why is no real title available?)
- scientific article; zbMATH DE number 5899272 (Why is no real title available?)
- scientific article; zbMATH DE number 5485488 (Why is no real title available?)
- scientific article; zbMATH DE number 5485521 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2038718 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Lower bounds on probabilistic linear decision trees
- On read-once threshold formulae and their randomized decision tree complexity
- On the power of Ambainis lower bounds
- Polynomial degree vs. quantum query complexity
- Quantum complexities of ordered searching, sorting, and element distinctness
- Quantum lower bounds by polynomials
- Quantum lower bounds by quantum arguments
- Quantum lower bounds for the collision and the element distinctness problems
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions
- Size-Depth Tradeoffs for Algebraic Formulas
- Size-depth tradeoffs for Boolean formulae
- Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
- Strengths and Weaknesses of Quantum Computing
- The quantum adversary method and classical formula size power bounds
- The quantum query complexity of certification
- Two applications of information complexity
Cited in
(7)- Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure
- Span-program-based quantum algorithm for evaluating formulas
- Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
- New developments in quantum algorithms
- scientific article; zbMATH DE number 2021815 (Why is no real title available?)
- Faster quantum algorithm for evaluating game trees
- Reflections for quantum query algorithms
This page was built for publication: Span-program-based quantum algorithm for evaluating unbalanced formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453313)
