Superlinear Advantage for Exact Quantum Algorithms
From MaRDI portal
Publication:2805516
DOI10.1137/130939043zbMath1339.68092OpenAlexW2570091096MaRDI QIDQ2805516
Publication date: 12 May 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/130939043
Related Items (5)
Quantum query as a state decomposition ⋮ An exact quantum algorithm for a restricted subtraction game ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Query complexity of generalized Simon's problem ⋮ Evaluation of exact quantum query complexities by semidefinite programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the distributional complexity of disjointness
- On the degree of Boolean functions as real polynomials
- Complexity measures and decision tree complexity: a survey.
- On rank vs. communication complexity
- On exact quantum query complexity
- Polynomial degree vs. quantum query complexity
- Span-program-based quantum algorithm for evaluating formulas
- Exact Quantum Query Algorithm for Error Detection Code Verification
- Optimal quantum query bounds for almost all Boolean functions.
- Exact Quantum Query Complexity of EXACT and THRESHOLD
- The Probabilistic Communication Complexity of Set Intersection
- Rapid solution of problems by quantum computation
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Quantum algorithms revisited
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- On the Power of Quantum Computation
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
- Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
- Quantum lower bounds by polynomials
- Quantum Walk Algorithm for Element Distinctness
- Automata, Languages and Programming
This page was built for publication: Superlinear Advantage for Exact Quantum Algorithms
