The Multiplicative Quantum Adversary

2007/03/26 by Robert Špalek, Spalek, Robert · 1 citation
Computer Science · #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #Quantum Information and Cryptography

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

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

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