An Optimal Separation of Randomized and Quantum Query Complexity
From MaRDI portal
communication complexityforrelationFourier analysis of Boolean functionsFourier weight of decision treesquantum-classical separationsquery complexity
Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)
Recommendations
Cites work
- Analysis of Boolean Functions
- Complexity measures and decision tree complexity: a survey.
- Entangled Simultaneity Versus Classical Interactivity in Communication Complexity
- Exponential separation of quantum and classical communication complexity
- Extremal combinatorics. With applications in computer science
- Forrelation: a problem that optimally separates quantum from classical computing
- Fourier growth of parity decision trees
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- scientific article; zbMATH DE number 7250141 (Why is no real title available?)
- scientific article; zbMATH DE number 6789278 (Why is no real title available?)
- scientific article; zbMATH DE number 7768398 (Why is no real title available?)
- Improved pseudorandomness for unordered branching programs through local monotonicity
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Learning Monotone Decision Trees in Polynomial Time
- On the Power of Quantum Computation
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Pseudorandomness and Fourier-growth bounds for width-3 branching programs
- Quantum Complexity Theory
- Quantum lower bounds by polynomials
- Quantum one-way communication can be exponentially stronger than classical communication
- Quantum Property Testing
- Query-to-communication lifting for BPP using inner product
- Rapid solution of problems by quantum computation
- Separations in query complexity using cheat sheets
- Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)
Cited in
(12)- Optimal separation in exact query complexities for Simon's problem
- The power of various real-valued quantum queries
- Improved bounds on the randomized and quantum complexity of initial-value problems
- The quantum query complexity of approximating the median and related statistics
- scientific article; zbMATH DE number 6667586 (Why is no real title available?)
- Optimality proofs of quantum weight decision algorithms
- Optimal separation and strong direct sum for randomized query complexity
- Algorithms and Computation
- Mathematical Foundations of Computer Science 2004
- An optimal separation of randomized and Quantum query complexity
- One-way communication complexity of partial XOR functions
- The quantum setting with randomized queries for continuous problems
This page was built for publication: An Optimal Separation of Randomized and Quantum Query Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890036)
