The polynomial method and the Ambainis lower bound (or 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 Alb's. We first use known Alb's to derive Ω (n1. 5) lower bounds for BIPARTITENESS,
BIPARTITENESS MATCHING and GRAPH MATCHING, in which the lower bound for
BIPARTITENESS improves the previous Ω (n) one. We then show that all the three known …

The polynomial method and the Ambainis's lower bound (or 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 Alb's. We first use known Alb's to derive Ω (n 1.5) lower bounds for Bipartiteness,
Bipartiteness Matching and Graph Matching, in which the lower bound for Bipartiteness
improves the previous Ω (n) one. We then show that all the three known Ambainis's lower …