A strong direct product theorem for quantum query complexity

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

Authors: Troy Lee, Jérémie Roland 

Publication date: 19 July 2013

Published in: Computational Complexity (Search for Journal in Brave)

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.

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

Recommendations

• Strong direct product theorems for quantum communication and query complexity
• Strong direct product theorems for quantum communication and 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
• 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

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)

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• A direct product theorem for two-party bounded-round public-coin communication complexity
• A strong direct product theorem for quantum query complexity
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Improved direct product theorems for randomized query complexity
• Tight characterizations for preprocessing against cryptographic salting
• 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)