A strong direct product theorem for quantum query complexity
From MaRDI portal
(Redirected from Publication:354645)
Abstract: We show that quantum query complexity satisfies a strong direct product theorem. This means that computing copies of a function with less than times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in . For a boolean function we also show an XOR lemma---computing the parity of copies of with less than 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)
