user78: A scalable quantum computer is a quantum computer that is easy to extend - adding more (q)bits of memory is not a fundamentally hard problem, and will happen. Or, alternatively, that it follows Moore's Law - its memory capacity and speed will increase exponentially over the years with technological advancement (the exponent might be relatively low).
Suppose such a Quantum Computer were constructed tomorrow - what would this mean for bitcoin?

user18458: I want to point out a quick possibly important point.
As other answers have mentioned current implementations of Bitcoin could be compromised by a quantum computer.
However, Quantum Computers do not solve all known classically hard problems and so any cryptography that is based on problems that are also difficult for a Quantum Computer to solve should work just as fine as classical crypto which also lives under the existential threat of someone discovering a polynomial time algorithm for factoring and similar problems.

user18526: With the current mining difficulty classical computers need to do 2*10^21 SHA256D invocations in average to find a block nonce. A quantum computer would need to do 4.5*10^10 invocations, which is billions times "faster". This means that the answer is: It would be able to doublespend as many times as the quantum adversary wants.

user5462: Worst case scenario:

Bitcoin ECDSA algorithm would be broken. Because quantum computers can easily decrypt the private key using the public key, anyone with a quantum computer can extract Bitcoins using the corresponding public key.
Bitcoin hashing would become exponentially difficult. There's already a predicted escalation in mining difficulty due to the advent of ASIC, and quantum computers would create a spike in mining difficulty to which ASIC mining effects pale in comparison. In the short run, this would lead to hyperinflation, but the long run effects aren't known at this point.
The hashing advantage of quantum computer will be curtailed by block mining limitations. To quote from the Bitcoin wiki: 

"The difficulty is the measure of how difficult it is to find a new block compared to the easiest it can ever be. It is recalculated every 2016 blocks to a value such that the previous 2016 blocks would have been generated in exactly two weeks had everyone been mining at this difficulty. This will yield, on average, one block every ten minutes. As more miners join, the rate of block creation will go up. As the rate of block generation goes up, the difficulty rises to compensate which will push the rate of block creation back down."
This means that the rate of block creation will not be impacted by quantum computers (the increase in key generation is proportional to the increase in difficulty, resulting in an overall mining rate of 1 bitcoin block every 10 minutes), but it will drastically increase the mining difficulty, exponentially more than ASIC miner already have. This gives miners with quantum computers (presumably corporations, government agencies, or other power organizations) a major advantage, to the point of being considered a monopoly, on the bitcoin market. 
Unless quantum computers either:
(a) become publicly available
(b) are given their own class for hashing purposes, so as to limit their mining advantage
Then miners with access to quantum computers have an unfair mining advantage, which can (and will be) used to manipulate the value and distribution of bitcoins. Furthermore,

Quantum computer's hashing power can be used as voting power. If a coalition of people with scalable quantum computers could generate enough hashes to comprise over 51% of the total Bitcoin hashes,they could use that power to greatly manipulate the bitcoin network.

As explained in the Bitcoin wiki ("Weaknesses") 
"An attacker that controls more than 50% of the network's computing power can, for the time that he is in control, exclude and modify the ordering of transactions. This allows him to:
Reverse transactions that he sends while he's in control. This has the potential to double-spend transactions that previously had already been seen in the block chain.
    Prevent some or all transactions from gaining any confirmations
    Prevent some or all other miners from mining any valid blocks 
The attacker can't:
Reverse other people's transactions
Prevent transactions from being sent at all (they'll show as 0/unconfirmed)
Change the number of coins generated per block
Create coins out of thin air
Send coins that never belonged to him 

With less than 50%, the same kind of attacks are possible, but with less than 100% rate of success. For example, someone with only 40% of the network computing power can overcome a 6-deep confirmed transaction with a 50% success rate.
It's much more difficult to change historical blocks, and it becomes exponentially more difficult the further back you go. As above, changing historical blocks only allows you to exclude and change the ordering of transactions. It's impossible to change blocks created before the last checkpoint."

However:
"Since this attack doesn't permit all that much power over the network, it is expected that no one will attempt it. A profit-seeking person will always gain more by just following the rules, and even someone trying to destroy the system will probably find other attacks more attractive. However, if this attack is successfully executed, it will be difficult or impossible to "untangle" the mess created -- any changes the attacker makes might become permanent."

All this being said, is it possible for a scalable quantum computer (specially, one that is programmed (like ASIC) to hash blocks) to have an exponential advantage over traditional computers, FPGAs, ASICS, etc.? 
That question is better addressed here: https://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to
There's a lot of mathematics involved, which is a bit above my academic proficiency, but we can derive at least this much:
Most of the algorithms quantum computers are famous for efficiently utilizing (Shor's algorithm, Grover's search algorithm) probably can't be used for hashing Bitcoin blocks. One possible exception noted is the collision attack, which if done using Grover's algorithm, could possibly perform better attacks than conventional computers: 
"Can quantum-computers perform better collision attacks? Actually I'm not sure about it. Grover's algorithm can be extended, such that if there are t items (that is, preimages), the time to find one is reduced to O(N/t−−−−√). But this gives no collision - running the algorithm again might return the same preimage. On the other hand, if we choose m1 at random, and then use Grover's Algorithm, it is probable that it will return a different message. I'm not sure if this gives better attacks."
https://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to
In the event that scalable quantum computers manage to corner the Bitcoin network, new code will be released to patch this vulnerability, so while there would be a long-term breakage of the network in the short term, there's nothing to worry about for Bitcoin users in the long term. 

user2281: You have a good discussion in:
https://bitcointalk.org/index.php?topic=133425.0
Basically, ECDSA is compromised, hashing isn't. With a quantum computer, you could easily deduce the private key corresponding to a public key. If you only have an address, which is a hashed public key, the private key is safe. Anyway, to spend a transaction, you need to send the public key. At that point you are vulnerable, but the attack is not straightforward. 
In general, quantum computers are not exponentially better than classical computers. You cannot access all the states in the superposition, only global properties. You can read http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf to get a good idea of what they can and cannot do.

78: <p>A <em>scalable</em> quantum computer is a quantum computer that is easy to extend - adding more (q)bits of memory is not a fundamentally hard problem, and will happen. Or, alternatively, that it follows Moore's Law - its memory capacity and speed will increase exponentially over the years with technological advancement (the exponent might be relatively low).</p>

<p>Suppose such a Quantum Computer were constructed tomorrow - what would this mean for bitcoin?</p>
 18458: <p>I want to point out a quick possibly important point.</p>

<p>As other answers have mentioned <strong><em>current</em></strong> implementations of Bitcoin could be compromised by a quantum computer.</p>

<p>However, Quantum Computers do not solve <strong><em>all</em></strong> known classically hard problems and so any cryptography that is based on problems that are also difficult for a Quantum Computer to solve should work just as fine as classical crypto which also lives under the existential threat of someone discovering a polynomial time algorithm for factoring and similar problems.</p>
 18526: <p>With the current mining difficulty classical computers need to do 2*10^21 SHA256D invocations in average to find a block nonce. A quantum computer would need to do 4.5*10^10 invocations, which is billions times "faster". This means that the answer is: It would be able to doublespend as many times as the quantum adversary wants.</p>
 5462: <p>Worst case scenario:</p>

<ol>
<li><p>Bitcoin ECDSA algorithm would be broken. Because quantum computers can easily decrypt the private key using the public key, anyone with a quantum computer can extract Bitcoins using the corresponding public key.</p></li>
<li><p>Bitcoin hashing would become exponentially difficult. There's already a predicted escalation in mining difficulty due to the advent of ASIC, and quantum computers would create a spike in mining difficulty to which ASIC mining effects pale in comparison. In the short run, this would lead to hyperinflation, but the long run effects aren't known at this point.</p></li>
<li><p>The hashing advantage of quantum computer will be curtailed by block mining limitations. To quote from the Bitcoin wiki: </p></li>
</ol>

<p>"The difficulty is the measure of how difficult it is to find a new block compared to the easiest it can ever be. It is recalculated every 2016 blocks to a value such that the previous 2016 blocks would have been generated in exactly two weeks had everyone been mining at this difficulty. This will yield, on average, one block every ten minutes. As more miners join, the rate of block creation will go up. As the rate of block generation goes up, the difficulty rises to compensate which will push the rate of block creation back down."</p>

<p>This means that the rate of block creation will not be impacted by quantum computers (the increase in key generation is proportional to the increase in difficulty, resulting in an overall mining rate of 1 bitcoin block every 10 minutes), but it will drastically increase the mining difficulty, exponentially more than ASIC miner already have. This gives miners with quantum computers (presumably corporations, government agencies, or other power organizations) a major advantage, to the point of being considered a monopoly, on the bitcoin market. </p>

<p>Unless quantum computers either:</p>

<p>(a) become publicly available
(b) are given their own class for hashing purposes, so as to limit their mining advantage</p>

<p>Then miners with access to quantum computers have an unfair mining advantage, which can (and will be) used to manipulate the value and distribution of bitcoins. Furthermore,</p>

<ol start="4">
<li>Quantum computer's hashing power can be used as voting power. If a coalition of people with scalable quantum computers could generate enough hashes to comprise over 51% of the total Bitcoin hashes,they could use that power to greatly manipulate the bitcoin network.</li>
</ol>

<p>As explained in the Bitcoin wiki ("Weaknesses") </p>

<p>"An attacker that controls more than 50% of the network's computing power can, for the time that he is in control, exclude and modify the ordering of transactions. This allows him to:</p>

<p>Reverse transactions that he sends while he's in control. This has the potential to double-spend transactions that previously had already been seen in the block chain.
    Prevent some or all transactions from gaining any confirmations
    Prevent some or all other miners from mining any valid blocks </p>

<p>The attacker can't:</p>

<pre><code>Reverse other people's transactions
Prevent transactions from being sent at all (they'll show as 0/unconfirmed)
Change the number of coins generated per block
Create coins out of thin air
Send coins that never belonged to him 
</code></pre>

<p>With less than 50%, the same kind of attacks are possible, but with less than 100% rate of success. For example, someone with only 40% of the network computing power can overcome a 6-deep confirmed transaction with a 50% success rate.</p>

<p>It's much more difficult to change historical blocks, and it becomes exponentially more difficult the further back you go. As above, changing historical blocks only allows you to exclude and change the ordering of transactions. It's impossible to change blocks created before the last checkpoint."</p>

<hr>

<p>However:</p>

<p>"Since this attack doesn't permit all that much power over the network, it is expected that no one will attempt it. A profit-seeking person will always gain more by just following the rules, and even someone trying to destroy the system will probably find other attacks more attractive. However, if this attack is successfully executed, it will be difficult or impossible to "untangle" the mess created -- any changes the attacker makes might become permanent."</p>

<hr>

<p>All this being said, is it possible for a scalable quantum computer (specially, one that is programmed (like ASIC) to hash blocks) to have an exponential advantage over traditional computers, FPGAs, ASICS, etc.? </p>

<p>That question is better addressed here: <a href="https://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to">https://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to</a></p>

<p>There's a lot of mathematics involved, which is a bit above my academic proficiency, but we can derive at least this much:</p>

<p>Most of the algorithms quantum computers are famous for efficiently utilizing (Shor's algorithm, Grover's search algorithm) probably can't be used for hashing Bitcoin blocks. One possible exception noted is the collision attack, which if done using Grover's algorithm, could <em>possibly</em> perform better attacks than conventional computers: </p>

<p>"Can quantum-computers perform better collision attacks? Actually I'm not sure about it. Grover's algorithm can be extended, such that if there are t items (that is, preimages), the time to find one is reduced to O(N/t−−−−√). But this gives no collision - running the algorithm again might return the same preimage. On the other hand, if we choose m1 at random, and then use Grover's Algorithm, it is probable that it will return a different message. I'm not sure if this gives better attacks."</p>

<p><a href="https://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to">https://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to</a></p>

<p>In the event that scalable quantum computers manage to corner the Bitcoin network, new code will be released to patch this vulnerability, so while there would be a long-term breakage of the network in the short term, there's nothing to worry about for Bitcoin users in the long term. </p>
 2281: <p>You have a good discussion in:</p>

<p><a href="https://bitcointalk.org/index.php?topic=133425.0">https://bitcointalk.org/index.php?topic=133425.0</a></p>

<p>Basically, ECDSA is compromised, hashing isn't. With a quantum computer, you could easily deduce the private key corresponding to a public key. If you only have an address, which is a hashed public key, the private key is safe. Anyway, to spend a transaction, you need to send the public key. At that point you are vulnerable, but the attack is not straightforward. </p>

<p>In general, quantum computers are not exponentially better than classical computers. You cannot access all the states in the superposition, only global properties. You can read <a href="http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf">http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf</a> to get a good idea of what they can and cannot do.</p>
