Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?
This is Assignment 3, Question 5 in Richard Cleve's ongoing intro to quantum computing course. (Seems like this assignment was due today.)

While we're not supposed to answer homework questions on CSTheory, fortunately the assignment answers all your questions. It also takes you through the construction of the quantum algorithm. I strongly recommend reading it.