Name
Abstract | ||
|---|---|---|
Span programs characterize the quantum query complexity of binary functions f : {0, ..., l}(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 : [l](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. |
Year | Venue | Keywords |
|---|---|---|
2018 | QUANTUM INFORMATION & COMPUTATION | Quantum query complexity,Span program,Learning graph |
Field | DocType | Volume |
Graph,Discrete mathematics,Quantum,Existential quantification,Mathematics,Binary number | Journal | 19 |
Issue | ISSN | Citations |
9-10 | 1533-7146 | 0 |
PageRank | References | Authors |
0.34 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Salman Beigi | 1 | 56 | 11.43 |
| Leila Taghavi | 2 | 1 | 0.96 |