Quantum Adversary (Upper) Bound

Details Quantum Adversary (Upper) Bound Quantum Adversary (Upper) Bound

2011-01-04

arxiv.org/abs/1101.0797v3

Physics

Quantum Physics

NOTE: There is a typo in reference [9], such that Lemma 2.3 in this paper only applies to total functions, which would cause t

Scientific paper

We propose a method for upper bounding the quantum query complexity of a boolean oracle problem using properties of the general adversary bound. This nonconstructive method gives an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem that we prove can be solved in O(1) queries, but we don't know the algorithm that achieves this. For a special case of this oracle problem, we give an O(1) query algorithm that uses the quantum Haar transform. This special case is an interesting problem in its own right, which we call the Haar Problem.

Affiliated with

Also associated with

No associations

Rating

Quantum Adversary (Upper) Bound 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 Quantum Adversary (Upper) Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Adversary (Upper) Bound will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-75428