On the power of Ambainis lower bounds

DOI10.1016/J.TCS.2005.01.019zbMATH Open1142.68367arXivquant-ph/0311060OpenAlexW2001383654MaRDI QIDQ557899FDOQ557899

Authors: Shengyu Zhang 

Publication date: 30 June 2005

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

Abstract: The polynomial method and the Ambainis's lower bound (or emph{Alb}, for short) method are two main quantum lower bound techniques. While recently Ambainis showed that the polynomial method is not tight, the present paper aims at studying the power and limitation of emph{Alb}'s. We first use known emph{Alb}'s to derive $Omega(n^{1.5})$ lower bounds for extsc{Bipartiteness}, extsc{Bipartiteness Matching} and extsc{Graph Matching}, in which the lower bound for extsc{Bipartiteness} improves the previous $Omega(n)$ one. We then show that all the three known Ambainis's lower bounds have a limitation $sqrtNcdotmin{C}_0(f),C_1(f)$, where $C_0(f)$ and $C_1(f)$ are the 0- and 1-certificate complexity, respectively. This implies that for some problems such as extsc{Triangle}, $k$- extsc{Clique}, and extsc{Bipartite/Graph Matching} which draw wide interest and whose quantum query complexities are still open, the best known lower bounds cannot be further improved by using Ambainis's techniques. Another consequence is that all the Ambainis's lower bounds are not tight. For total functions, this upper bound for emph{Alb}'s can be further improved to $minsqrt{C}_0(f)C_1(f),sqrtNcdotCI(f)$, where $CI(f)$ is the size of max intersection of a 0-and a 1-certificate set. Again this implies that $Alb$'s cannot improve the best known lower bound for some specific problems such as extsc{And-Or Tree}, whose precise quantum query complexity is still open. Finally, we generalize the three known emph{Alb}'s and give a new emph{Alb} style lower bound method, which may be easier to use for some problems.

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

Recommendations

• Automata, Languages and Programming
• Quantum lower bounds by quantum arguments
• SOFSEM 2004: Theory and Practice of Computer Science
• A lower bound on the quantum query complexity of read-once functions
• Quantum lower bounds by quantum arguments

zbMATH Keywords

Lower bound techniqueQuantum adversary methodQuantum computingQuantum query complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68)

Cites Work

• The quantum query complexity of approximating the median and related statistics
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Title not available (Why is that?)
• On the Power of Quantum Computation
• A new protocol and lower bounds for quantum coin flipping
• Rapid solution of problems by quantum computation
• Quantum lower bound for the collision problem
• Complexity measures and decision tree complexity: a survey.
• Quantum lower bounds by polynomials
• Automata, Languages and Programming
• SOFSEM 2004: Theory and Practice of Computer Science
• Quantum lower bounds by quantum arguments
• Lower bounds for local search by quantum arguments
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Quantum complexities of ordered searching, sorting, and element distinctness
• A lower bound on the quantum query complexity of read-once functions
• Title not available (Why is that?)
• Automata, Languages and Programming

Cited In (19)

• Title not available (Why is that?)
• Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas
• Quantum and classical query complexities of local search are polynomially related
• Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives
• Quantum separation of local search and fixed point computation
• Quantum query complexity of constant-sized subgraph containment
• Quantum counterfeit coin problems
• On the quantum query complexity of local search in two and three dimensions
• Title not available (Why is that?)
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
• Automata, Languages and Programming
• Title not available (Why is that?)
• RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
• On the power of non-adaptive learning graphs
• A query-efficient quantum algorithm for maximum matching on general graphs
• Symmetries, graph properties, and quantum speedups
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
• On query complexity measures and their relations for symmetric functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557899)