On the power of Ambainis lower bounds

DOI10.1016/j.tcs.2005.01.019zbMath1142.68367arXivquant-ph/0311060OpenAlexW2001383654MaRDI QIDQ557899

Shengyu Zhang

Publication date: 30 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0311060

zbMATH Keywords

Quantum computingLower bound techniqueQuantum adversary methodQuantum query complexity

Mathematics Subject Classification ID

Related Items (16)

A query-efficient quantum algorithm for maximum matching on general graphs ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ On the quantum query complexity of local search in two and three dimensions ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT ⋮ Quantum separation of local search and fixed point computation ⋮ Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives ⋮ On the power of non-adaptive learning graphs ⋮ A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems ⋮ Quantum counterfeit coin problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity measures and decision tree complexity: a survey.
• Quantum complexities of ordered searching, sorting, and element distinctness
• A lower bound on the quantum query complexity of read-once functions
• The quantum query complexity of approximating the median and related statistics
• Quantum lower bound for the collision problem
• Lower bounds for local search by quantum arguments
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• 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
• A new protocol and lower bounds for quantum coin flipping
• Quantum lower bounds by polynomials
• Automata, Languages and Programming
• Automata, Languages and Programming
• Quantum lower bounds by quantum arguments
• SOFSEM 2004: Theory and Practice of Computer Science

This page was built for publication: On the power of Ambainis lower bounds