A strong direct product theorem for quantum query complexity
From MaRDI portal
Publication:354645
DOI10.1007/s00037-013-0066-8zbMath1286.68156arXiv1104.4468OpenAlexW2167217679MaRDI QIDQ354645
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
Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (4)
A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ A strong direct product theorem for quantum query complexity ⋮ Improved direct product theorems for randomized query complexity ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A direct product theorem for two-party bounded-round public-coin communication complexity
- A strong direct product theorem for quantum query complexity
- Complexity measures of sign matrices
- Complexity measures and decision tree complexity: a survey.
- Towards proving strong direct product theorems
- Positive definite matrices
- Polynomial degree vs. quantum query complexity
- A new quantum lower bound method,
- 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
- On Yao’s XOR-Lemma
- A Parallel Repetition Theorem
- Strong Direct Product Theorems for Quantum Communication and Query Complexity
- A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems
- Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum lower bounds by polynomials
- Elements of Information Theory
- Quantum Query Complexity of State Conversion
- Quantum lower bounds by quantum arguments
- Lower bounds in communication complexity based on factorization norms
This page was built for publication: A strong direct product theorem for quantum query complexity
