The Multiplicative Quantum Adversary

2007/03/26 by Robert Špalek, Robert Spalek, Spalek, Robert · 2 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0703237

15 pages, v2: removed an incorrect claim, v3: cleaned up, commented better, added stronger bound for OR

arxiv created 2007/04/25 · arxiv updated 2009/12/01

Abstract

We present a new variant of the quantum adversary method. All adversary methods give lower bounds on the quantum query complexity of a function by bounding the change of a progress function caused by one query. All previous variants upper-bound the_difference_ of the progress function, whereas our new variant upper-bounds the_ratio_ and that is why we coin it the multiplicative adversary. The new method generalizes to all functions the new quantum lower-bound method by Ambainis [Amb05, ASW06] based on the analysis of eigenspaces of the density matrix. We prove a strong direct product theorem for all functions that have a multiplicative adversary lower bound.

Citations

• Strengths and Weaknesses of Quantum Computing
• Quantum Complexity Theory

Cited by

• The Compressed Oracle is a Worthy (Multiplicative) Adversary
• An adversary bound for quantum signal processing

Related

• Variations on Quantum Adversary
• The General Adversary Bound: A Survey
• Tight adversary bounds for composite functions
• A Direct Reduction from the Polynomial to the Adversary Method
• Applications of the Adversary Method in Quantum Query Algorithms