A strong direct product theorem for quantum query complexity

DOI10.1007/S00037-013-0066-8zbMATH Open1286.68156OpenAlexW2167217679MaRDI QIDQ354645FDOQ354645

Authors Troy Lee, Jérémie Roland 

Publication date 19 July 2013

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.4468

zbMATH Keywords

strong direct product theoremadversary methodquantum query complexityXOR lemma

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: We show that quantum query complexity satisfies a strong direct product theorem. This means that computing $k$ copies of a function with less than $k$ times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in $k$. For a boolean function $f$ we also show an XOR lemma---computing the parity of $k$ copies of $f$ with less than $k$ times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, is always at least as large as the additive adversary method, which is known to characterize quantum query complexity.

Recommendations

• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• A new quantum lower bound method, with an application to a strong direct product theorem for quantum search
• On exact quantum query complexity
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• The quantum query complexity of the determinant
• The Quantum Query Complexity of Algebraic Properties

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• scientific article; zbMATH DE number 5485521 (Why is no real title available?)
• A Parallel Repetition Theorem
• A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
• A direct product theorem for two-party bounded-round public-coin communication complexity
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• A strong direct product theorem for quantum query complexity
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Complexity measures and decision tree complexity: a survey.
• Complexity measures of sign matrices
• Discrete-query quantum algorithm for NAND trees
• Elements of Information Theory
• Lower bounds in communication complexity based on factorization norms
• On Yao's XOR-lemma
• Polynomial degree vs. quantum query complexity
• Positive definite matrices
• Quantum Query Complexity of State Conversion
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Reflections for quantum query algorithms
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• The quantum query complexity of certification
• Towards proving strong direct product theorems

Cited in

(7)

• A direct product theorem for two-party bounded-round public-coin communication complexity
• Tight characterizations for preprocessing against cryptographic salting
• A strong direct product theorem for quantum query complexity
• Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
• Improved direct product theorems for randomized query complexity
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• A new quantum lower bound method, with an application to a strong direct product theorem for quantum search

This page was built for publication: A strong direct product theorem for quantum query complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q354645)