Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas
From MaRDI portal
Publication:3453313
DOI10.1007/978-3-642-54429-3_6zbMath1451.68127arXiv0907.1622OpenAlexW1917967022MaRDI QIDQ3453313
Publication date: 20 November 2015
Published in: Theory of Quantum Computation, Communication, and Cryptography (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0907.1622
Cites Work
- On the power of Ambainis lower bounds
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions
- Lower bounds on probabilistic linear decision trees
- On read-once threshold formulae and their randomized decision tree complexity
- Size-depth tradeoffs for Boolean formulae
- Quantum complexities of ordered searching, sorting, and element distinctness
- A lower bound on the quantum query complexity of read-once functions
- The quantum adversary method and classical formula size power bounds
- Polynomial degree vs. quantum query complexity
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
- Quantum lower bounds for the collision and the element distinctness problems
- Two applications of information complexity
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
- Strengths and Weaknesses of Quantum Computing
- Size-Depth Tradeoffs for Algebraic Formulas
- Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
- Quantum lower bounds by polynomials
- Quantum lower bounds by quantum arguments
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas
