An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation

Details An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation

2003-11-29

arxiv.org/abs/quant-ph/0312003v3

Physics

Quantum Physics

16 pages. An extended abstract will appear in the Proceedings of the 29th International Symposium on Mathematical Foundations

Scientific paper

This paper employs a powerful argument, called an algorithmic argument, to prove lower bounds of the quantum query complexity of a multiple-block ordered search problem in which, given a block number i, we are to find a location of a target keyword in an ordered list of the i-th block. Apart from much studied polynomial and adversary methods for quantum query complexity lower bounds, our argument shows that the multiple-block ordered search needs a large number of nonadaptive oracle queries on a black-box model of quantum computation that is also supplemented with advice. Our argument is also applied to the notions of computational complexity theory: quantum truth-table reducibility and quantum truth-table autoreducibility.

Affiliated with

Also associated with

No associations

Rating

An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-643967