- Tight adversary bounds for composite functions
- Number of pages
- Unknown Publisher
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
The quantum adversary method is a very versatile method for proving lower bounds on quantum algorithms. It has many equivalent formulations, yields tight bounds for many computational problems, and has natural connections to classical lower bounds. One of its formulations is in terms of the spectral norm of some matrices. We define a weighted version of this spectral method and show that it possesses useful composition properties. The results generalize and unify previously known composition properties of adversary methods.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.