Nobel-prize winning physicist Richard Feynman is given credit as inventing the concept of quantum computers in about 1982 in the paper "Simulating physics with computers." Also, recently the company DWave has introduced an allegedly real quantum computer that has seen a lot of news, including purchases by NASA, Google, and Lockheed Martin.
When was the concept of a quantum computer first used in science fiction?
Quantum computing experts tend to say that DWave is not a "true" universal quantum computer which uses the quantum version of logic gates, rather it combines quantum physics with what's known as an "adiabatic computer", which does let it do certain types of calculations better than a classical computer though it's not clear whether this can be scaled up (see the Scientific American article here for a good summary).
As for your question, I tried searching "quantum computer" on google books, then when the list of results came up I clicked "search tools" at the top, then switched from "any time" to "custom range", and restricted the date range in various ways to try to find the earliest example of a sci-fi book with this phrase. Earliest I could find were the snippets here that showed up on pp. 155-159 of an issue of "Analog Science Fiction & Fact", a little searching for more snippets from the same story showed that it's the novelette "A Gift Before Leaving" by W.R. Thompson, from the Mid-December 1992 issue (see the two consecutive snippets on p. 159 here and here). That issue is available cheap from marketplace sellers on amazon, if you want to read it. Of course google books doesn't include all publications, but this is probably one of the earliest, anyway.
edit: Richard's answer of "Quarantine" by Greg Egan is a good find, the hardcover version was from September 1992 so it predates "A Gift Before Leaving" by a few months. If you click on the cover on its amazon page and do a search for "quantum computer", Egan never uses that specific phrase but there is a quote describing the idea on pp. 213-214: "Let a computer smear--with the right kind of quantum randomness--and you create, in effect, a 'parallel' machine with an astronomical number of processors. Each one executes the same program, but applies it to different data. All you have to do is be sure that when you collapse the system, you choose the version that happened to find the needle in the mathematical haystack."
I also came across a later essay by Egan where he explains that his idea in the story of what would be possible with a quantum computer was invalidated by later science:
That last part is where the dream collides with reality. There is no general-purpose method for instantly discovering which, if any, of the “branches” of the calculation yielded the desired result. All you have at the end of the calculation is a quantum system in a superposition of thousands of states, and if you simply measure the state of that system, the probability of observing the one result that tells you something useful is vanishingly small. You might just as well have run a single classical computer on a randomly chosen input! There are ingenious things that can be done for particular problems: approaches that exploit the detailed structure of the problem to enable a quantum computer to reach a state where it has a high probability of telling you something useful (Peter Shor's algorithm for factoring numbers is the most celebrated example of that). But what the 1997 “BBBV” paper showed was that the naive idea of taking a completely general problem and expecting a quantum computer to give the answer in the same manner, and just as rapidly, as if you were dealing with as many classical computers as there are branches to the quantum calculation, is untenable. I suppose I can’t be blamed for failing to know this result five years before it was proved, but this is fatal for most of Nick’s quantum feats, which amount to him “smearing”, simultaneously trying every alternative among thousands or millions, then choosing to collapse to the branch that happened to succeed.
Isaac Asimov's "The Last Question" 1956. It describes the evolution of the supercomputer Multivac as it tries to answer the ultimate question during the ages. The mechanics of the computer gets to the atomic level IIRC and beyond into hyperspace by the end.
There was a James Hogan book in 1996, Paths to Otherwhere. As memory serves, it's explained that rather than relying on binary, the computer relied on the quantum numbers instead. Whether this was meant as a simplified explanation for a quantum computer, I don't know.
