Good books to get a grasp of Quantum Computing? (+ preliminaries) What are good upper undergraduate/graduate level books on this matter? What are the preliminaries before you can go for an introduction to quantum computing? 
If there is a book like Sipser, that would be perfect! (but I doubt its existence)
This paper by Fortnow was pretty good but after a few pages I was lost because of my limited knowledge on complexity theory.
 A: Does Sipser, perchance, have any references or a bibliography of suggested reading in his Theory of Computation text?  There are a few texts listed on complexity; lots of articles.
I did come across an article by Sipser and colleagues on Arxiv:Quantum Computation by Adiabatic Evolution on arxiv.org: perhaps there are some survey articles in the references listed?  Such a survey article will likely suggest a good text to start with. 
This article on Arxiv came up in a search for "survey article..." @ http://arxiv.org/abs/0804.3401: Quantum Computational Complexity, by John Watrous. It could be a good start, and perhaps suggest other relevant, introductory/preliminary readings.
Sipser has an entry in Wikipedia: Sipser; it lists his research area, publications, and contact information, etc.  Since you seem to like Sipser's approach, perhaps contacting him directly at MIT with your question will yield a helpful response?
Sorry I couldn't be more helpful at the moment. Akhil seems to have added a suggestion in a comment.  I'll return later if I have time to expand on this.
A: Quantum computation and quantum information by Nielsen and Chuang is a very good reference.
A: Perhaps Quantum Computer Science: An Introduction by N.David Mermin. Perhaps it is too elementary for your needs – this may well be an excellent first book in the subject – but he is a prominent physicist and a good expositor, and I've enjoyed reading the beginning of the book.
"I am addressing computer scientists, electrical engineers, or mathematicians who may know little or nothing about quantum physics... but who wish to acquire enough facility in the subject to be able to follow the new developments in quantum computation.... Not the least of the surprising things about quantum computation is that remarkably little background in quantum mechanics has to be acquired...."
A: Quantum Processes Systems and Information by Schumacher and Westmoreland is good.
