Bill Gasarch is offering $289 for a 4-coloring of a 17-by-17 grid such that there is no rectangle with all four corners the same color. (No reward for proving one doesn't exist.)
Edit: The above problem, of 4-coloring grids, has since been solved completely; see the comments for the 12x21 case.
Scott Aaaronson offers $200 for an oracle relative to which BQP is not contained in PH, or $100 for an oracle relative to which BQP is not contained in AM.
He also offers $50 for... this one is long and technical and I don't know the subject very well so I won't bother trying to summarize.
Finally, he also offers $25 for an answer to the question: "If a quantum computer can efficiently solve a problem, can it also efficiently convince [a classical verifier] that the solution is correct? More formally, does every language in the class BQP admit an interactive protocol where the prover is in BQP and the verifier is in BPP?" He'll also pay $25 for an oracle relative relative to which the answer is "no".
