Variations on Quantum Adversary

Abstract

The (negative-weighted) quantum adversary bound is a tight characterisation of the quantum query complexity for any partial function. We analyse the extent to which this bound can be generalised. Ambainis et al. [arXiv:1012.2112] and Lee et al. [arXiv:1011.3020] generalised this bound to the state generation and state conversion problems, respectively. Using the ideas by Lee et al., we get even further generalisations of the bound. We obtain a version of the bound for general input oracles, which are just arbitrary unitaries. We also generalise the bound to the problem of implementing arbitrary unitary transformations. Similarly to the bound by Lee et al., our bound is a lower bound for exact transformation and an upper bound for approximate transformation. This version of the bound possesses the tight composition property. Using this construction, we also obtain lower bounds on the quantum query complexity of functions and relations with general input oracles.

33 pages

References in corpus (14)

• Strengths and Weaknesses of Quantum Computing
• Quantum Algorithms Revisited
• Negative weights make adversaries stronger
• Quantum query complexity of state conversion
• Span-program-based quantum algorithm for evaluating formulas
• Efficient discrete-time simulations of continuous-time quantum query algorithms
• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Quantum Walks and Electric Networks
• Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
• Quantum lower bounds by quantum arguments
• On the power of Ambainis's lower bounds
• The Quantum Query Complexity of Algebraic Properties
• Adversary lower bounds in the Hamiltonian oracle model
• Quantum Algorithms for Finding Constant-sized Sub-hypergraphs

Cited by in corpus (6)

• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
• The Quantum Supremacy Tsirelson Inequality
• The quantum query complexity of composition with a relation
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments
• Provably secure key establishment against quantum adversaries