2018/05/07 by Salman Beigi, Beigi, Salman, Leila Taghavi +1
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1805.02714
41 pages, 2 figures. Changes in definition of non-binary span program and learning graph leading to major improvements in the results. Arguments added to support the naturalness of the definition of non-binary span program in the text and in a new appendix
arxiv created 2019/05/30 · arxiv updated 2019/05/31
Span programs characterize the quantum query complexity of binary functions f:\0,…,ℓ\n → \0,1\ up to a constant factor. In this paper we generalize the notion of span programs for functions with non-binary input/output alphabets f: [ℓ]n → [m]. We show that non-binary span program characterizes the quantum query complexity of any such function up to a constant factor. We argue that this non-binary span program is indeed the generalization of its binary counterpart. We also generalize the notion of span programs for a special class of relations. Learning graphs provide another tool for designing quantum query algorithms for binary functions. In this paper, we also generalize this tool for non-binary functions, and as an application of our non-binary span program show that any non-binary learning graph gives an upper bound on the quantum query complexity.