Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Cornelissen, Arjan, Mande, Nikhil S ORCID: 0000-0002-9520-7340 and Patro, Subhasree (2025) Improved Quantum Query Upper Bounds Based on Classical Decision Trees QUANTUM, 9. p. 1777. ISSN 2521-327X, 2521-327X

PDF q-2025-06-23-1777.pdf - Open Access published version Download (996kB) | Preview

Abstract

We consider the following question in query complexity: Given a classical query algorithm in the form of a decision tree, when does there exist a quantum query algorithm with a speed-up (i.e., that makes fewer queries) over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up in the number of queries. In particular, our results give a bounded-error quantum query algorithm of cost O(√s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s. This recovers an O(√n) algorithm for the Search problem, for example. Lin and Lin [Theory of Computing’16] and Beigi and Taghavi [Quantum’20] showed results of a similar flavor. Their upper bounds are in terms of a quantity which we call the “guessing complexity” of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Information and Computation’89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any measure studied in classical complexity theory. We also show a polynomial separation between rank and its natural randomized analog for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to edges of the tree. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are asymptotically stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes in their construction could yield better upper bounds.

Item Type:	Article
Uncontrolled Keywords:	4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	01 Jul 2025 08:18
Last Modified:	23 May 2026 10:19
DOI:	10.22331/q-2025-06-23-1777
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3193416
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.