Optimal parallel quantum query algorithms
From MaRDI portal
Publication:2408924
DOI10.1007/s00453-016-0206-zzbMath1372.68107arXiv1309.6116OpenAlexW2170333283MaRDI QIDQ2408924
Ronald de Wolf, Frédéric Magniez, Stacey Jeffery
Publication date: 10 October 2017
Published in: Algorithmica, Algorithms - ESA 2014 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1309.6116
Parallel algorithms in computer science (68W10) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (2)
Element distinctness revisited ⋮ On the compressed-oracle technique, and post-quantum security of proofs of sequential work
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Collapse of the hierarchy of constant-depth exact quantum circuits
- On the power of non-adaptive learning graphs
- On the degree of Boolean functions as real polynomials
- Nonadaptive quantum query complexity
- Complexity measures and decision tree complexity: a survey.
- Sharp quantum versus classical query complexity separations
- Parallel Quantum Computation and Quantum Codes
- Forrelation
- Optimal quantum query bounds for almost all Boolean functions.
- Adversary lower bound for the k-sum problem
- Search via Quantum Walk
- Quantum Circuits with Unbounded Fan-out
- Quantum lower bounds for the collision and the element distinctness problems
- CREW PRAM<scp>s</scp> and Decision Trees
- Rapid solution of problems by quantum computation
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- On the Power of Quantum Computation
- Separations in Query Complexity Based on Pointer Functions
- Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
- Time-Efficient Quantum Walks for 3-Distinctness
- Separations in query complexity using cheat sheets
- Efficient distributed quantum computing
- Span programs for functions with constant-sized 1-certificates
- Quantum lower bounds by polynomials
- Quantum Walk Algorithm for Element Distinctness
- Quantum Query Complexity of State Conversion
- Quantum lower bounds by quantum arguments
This page was built for publication: Optimal parallel quantum query algorithms
