On the power of Ambainis lower bounds

DOI10.1016/J.TCS.2005.01.019MaRDI QIDQ557899zbMATHOpenAlexFDO

Authors 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

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)

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.

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

Cites work

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

Cited in

(19)

• On the quantum query complexity of local search in two and three dimensions
• Automata, Languages and Programming
• Symmetries, graph properties, and quantum speedups
• On query complexity measures and their relations for symmetric functions
• Quantum and classical query complexities of local search are polynomially related
• A query-efficient quantum algorithm for maximum matching on general graphs
• Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
• A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
• Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• Quantum counterfeit coin problems
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
• Quantum query complexity of constant-sized subgraph containment
• RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC
• Quantum separation of local search and fixed point computation
• scientific article; zbMATH DE number 7559367 (Why is no real title available?)
• On the power of non-adaptive learning graphs
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• The polynomial method strikes back: tight quantum query bounds via dual polynomials

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)