We introduce a complexity measure r for the class $\mathcal{F}$ of read-once formulas over the basis {AND, OR, NOT, XOR, MUX} and show that for any Boolean formula F in the class $\mathcal{F}$ , r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in $\mathcal{F}$ , the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.We introduce a complexity measure r for the class $\mathcal{F}$ of read-once formulas over the basis {AND, OR, NOT, XOR, MUX} and show that for any Boolean formula F in the class $\mathcal{F}$, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in $\mathcal{F}$, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.

IEICE Transactions on Information and SystemsJan 1, 20100 citations

Parameterized query complexity in quantum computation

Parijat Prashun Purohit

Jan 1, 20170 citations

Computer-assisted proof of lower bounds on the randomized query complexity of certain read-once threshold functions

Nikos Leonardos

Abstract: In this work we prove lower bounds on the randomized decision tree complexity of several read-once threshold functions. A read-once threshold formula can be defined by a rooted tree, in which every internal node is labeled by a threshold function (with output 1 only when at least out of input bits are 1) and each leaf by a variable. We consider the randomized decision tree complexity of such functions, when the underlying tree is a uniform and balanced tree with all its internal nodes labeled by the same threshold function. We prove lower bounds of the form , where is the depth of the tree, for certain values of and. The value of each parameter depends on the solution of a linear program, which is provided by computational methods. Keywords: Decision trees, query complexity, randomized computation, lower bounds, read-once functions. Title: Computer-assisted proof of lower bounds on the randomized query complexity of certain read-once threshold functions Author: Nikos Leonardos International Journal of Recent Research in Mathematics Computer Science and Information Technology ISSN 2350-1022 Vol. 9, Issue 2, October 2022 - March 2023 Page No: 11-17 Paper Publications Website: www.paperpublications.org Published Date: 10-December-2022 DOI: https://doi.org/10.5281/zenodo.7421269 Paper Download Link (Source) https://www.paperpublications.org/upload/book/Computer-assisted%20proof%20of%20lower-10122022-1.pdfAbstract: In this work we prove lower bounds on the randomized decision tree complexity of several read-once threshold functions. A read-once threshold formula can be defined by a rooted tree, in which every internal node is labeled by a threshold function (with output 1 only when at least out of input bits are 1) and each leaf by a variable. We consider the randomized decision tree complexity of such functions, when the underlying tree is a uniform and balanced tree with all its internal nodes labeled by the same threshold function. We prove lower bounds of the form , where is the depth of the tree, for certain values of and. The value of each parameter depends on the solution of a linear program, which is provided by computational methods. Keywords: Decision trees, query complexity, randomized computation, lower bounds, read-once functions. Title: Computer-assisted proof of lower bounds on the randomized query complexity of certain read-once threshold functions Author: Nikos Leonardos International Journal of Recent Research in Mathematics Computer Science and Information Technology ISSN 2350-1022 Vol. 9, Issue 2, October 2022 - March 2023 Page No: 11-17 Paper Publications Website: www.paperpublications.org Published Date: 10-December-2022 DOI: https://doi.org/10.5281/zenodo.7421269 Paper Download Link (Source) https://www.paperpublications.org/upload/book/Computer-assisted%20proof%20of%20lower-10122022-1.pdf

Dec 10, 20220 citations

Lower bounds on quantum query complexity for read-once decision trees with parity nodes

Hideaki Fukuhara, Eiji Takimoto

We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.We introduce a complexity measure for decision trees called the soft rank, which measures how well-balanced a given tree is. The soft rank is a somehow relaxed variant of the rank. Among all decision trees of depth d, the complete binary decision tree (the most balanced tree) has maximum soft rank d, the decision list (the most unbalanced tree) has minimum soft rank √d, and any other trees have soft rank between √d and d. We show that, for any decision tree T in some class G of decision trees which includes all read-once decision trees, the soft rank of T is a lower bound on the quantum query complexity of the Boolean function that T represents. This implies that for any Boolean function f that is represented by a decision tree in G, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f.

Computing: The Australasian Theory SymposiumJan 1, 20090 citations

The Quantum Query Complexity of Read-Many Formulas

Mitchell Andrew, Shelby Kimmel, Robin Kothari

Lecture notes in computer scienceJan 1, 20120 citations

We introduce a complexity measure r for the class

\mathcal{F}

of read-once formulas over the basis {AND, OR, NOT, XOR, MUX} and show that for any Boolean formula F in the class

\mathcal{F}

, r(F) is a lower bound on the quantum query complexity of the Boolean function that F represents. We also show that for any Boolean function f represented by a formula in

\mathcal{F}

, the deterministic query complexity of f is only quadratically larger than the quantum query complexity of f. Thus, the paper gives further evidence for the conjecture that there is an only quadratic gap for all functions.