Bitcoin Forum

http://www.infowars.com/skynet-rising-google-acquires-512-qubit-quantum-computer-nsa-surveillance-to-be-turned-over-to-ai-machines/

Forget for a second that if you are mainstream, that you love Obama and Alex Jones / InfoWars.com is crazy.

So we have 512-qubit Quantum Computer now. After realizing how powerful that is, what affect would that have on BitCoin mining? Would this even make ASIC miners obsolete?

Fuck Alex Jones.
Quantum encryption will come online before Quantum cracking becomes remotely viable.
SHA256 does not fear current quantum computers.
Edit: Sorry for knee jerk nonanswer.
Quantum computers are not as well suited to btc hashing due to difficulty increases.
http://bitcoin.stackexchange.com/questions/6062/what-effects-would-a-scalable-quantum-computer-have-on-bitcoin
http://cs.stackexchange.com/questions/586/could-quantum-computing-eventually-be-used-to-make-modern-day-hashing-trivial-to

Bullshit! (http://www.youtube.com/watch?feature=player_detailpage&v=ejvvPIaYrSo#t=12340s)

A QC is either useless for hashing (if it is too small) or can determine the right nonce for any hash (if it is large enough).
There might be some indeterminate use but since it makes difficulty increases a linear problem out of an exponential one once it is useful it would make difficulty useless soon after.

Great, take Alex Jones out of context and make a lol video.

Ok back on topic, what affect would this new computer have on mining?

Try to explain in plain English for those of us still thumbing through Win95 for Dummies.

Well with traditional computers you would count this way to 1000:
1, 2, 4, 5, ... , 996, 997, 998, 999, 1000

With a quantum computer you would do

(1-9), (10-99), (100-999), 1000

(It's not exactly right since it is bits vs. qbits and I used the decimal system for the example but in principle.)

Quantum computers don't just turn exponential time into linear time. There are certain problems where they're known to be able to do that, but there are a lot of problems where that's not known. Finding a suitable nonce is a lot like reverse phonebook search, and Grover's algorithm operates in order sqrt(N) guesses, instead of the classical N guesses. Assuming this is in fact the best way to use a quantum computer for mining, this has a curious effect. It means that if the difficulty quadrupled, it would take only twice as long to find a suitable nonce – which is effectively twice the hashpower, but still finding blocks slower. The effective hashpower of a quantum computer increases with increasing difficulty, but it still falls behind. The difficulty would still be able to increase to keep up with hashpower, so there's no existential threat to Bitcoin mining.

Pre-order Quavalon mining rig that do 1PH/s on USB power  ;)

It's time to collect interests for a Quantum mining rig project

Doubt it.
How I understand QC its just a matter of what kind of tradeoff you have to take to solve a problem with a computer of a particular size. And if you can even make such a trade-off (currently we can not)
As quantum computers get larger the trade-off can be reduced to the point where it is none existent.

Is there a good resource for the totally uninformed pointing out why this is superior to binary calculations, or what the benefits and drawbacks are in using qubits?

When I try to learn about it, I either get

https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcSchyFeoqooB7jrS1i8rOXdKh8cbiAjkf84szf2iej3IZYuoof3xA
which I completely lack foundational knowledge to understand,

or

"It grabs answers from another dimension."

I think that is as good an explanation as any. But I'm no a physicist.
What works for me is thinking of a quantum computer as an analogue computer with infinite signal/noise ratio.

Can you give some simple examples of algorithms for quantum computers?  What kinds of questions can I ask this magic ball?

Sorry I can't.

Can I ask it 1 + 2?

In my understanding, Quantum computer might not be suitable to do general purpose computing but it is very suitable to solve one specific problem, that's exactly what bitcoin mining requires, to find a correct nonce that match certain criteria

Move the hashing function in ASICs into a Quantum computer and you will reduce the hash time for several magnitudes (And increase the difficulty to same degree :))

There will be some companies provide ASIC to Quantum chips conversion in future, and I don't think there will be much difference, the functional design is the same, and the underlying implementation is invisible

In principle, the first Quantum miner will immediately command 99.99% of the network hashing power, this is very dangerous so better we have several loyal bitcoin hardware companies start to deploy those miners at the same time

But can it play Crysis?

Look like this magic ball can be able to answer question  "Here is public key. What is PRIVATE one ?"

I guess I'm just missing where a superposition would be useful. Why would I want 0, 1, AND 2? How does "both" make for more efficient code, and why wouldn't it be incorporated in instruction sets where it could be useful in general purpose? I guess just a sample of simple instructions, like maybe for an adder, and how it would look, mechanically, in binary logic and quantum - would help.

Right now, I'm thinking of a truth table with "AND" in it, and now there's "yes," "no," and the useless (or I'm just unimaginative) "both." Do there need to be new operators to work with "both," or does "both" just replace "AND" to simplify?

Edit: Or maybe it doesn't log a "2" (some potential state between 0 and 1) but is instead a whole slew of possibilities between 0 and 1? - But it has to compute the probabilities, right? Dammit. Now I need this to click.

Okay, so what exactly's happening here -- something's trying to record the probability of something being on or off, because we can't measure it in certain cases with certain materials. How can it do this without tons of calculations going into determining whether something's "on" or "off" - how could something possibly measure that?

This thing is not a quantum computer, but a computer which uses quantum effects for faster problem solving and has significant differences.

http://arstechnica.com/science/2013/05/d-waves-quantum-optimizer-pitted-against-traditional-computers/

I'm not sure, what the implications are, though.

Here's a very informative TEDtalk on quantum computing.
http://www.youtube.com/watch?v=cugu4iW4W54&feature=youtube_gdata_player
And this:
http://www.youtube.com/watch?v=Kk6LhMcVmwA&feature=youtube_gdata_player
And this:
http://www.youtube.com/watch?v=8bLXHvH9s1A&feature=youtube_gdata_player
Quantum encryption will replace all encryption eventually.
Bitcoin is less vulnerable than anything else using SHA256.

From this article, their chip's calculated a specific problem, 3600 to 10000 times faster than a seven Xeon Quad core system. Suppose that an Xeon Quad have a 30MH/s speed, and 7 of them is 210MH/s, times 3600, that's at least 756GH/s for a single chip, at least 100 times faster than fastest existing ASIC design

So it will be the same impact next time when we go from ASIC to Quantum chips, not that much I thought about

Thanks for the first link, seems they are using existing  silicon manufacturing process to make quantum computer chips, and it is already quite mature. We might see these chips appear in 1-2 years

Except that annoying background energy that requires near absolute zero operating temperatures.

Why do you have to love Obama to not be considered a whackjob?  ???

Thanks for the math, bu the the difference between a quantum computer and a quantum optimizer is unclear for me. Not technically, but from an application point of view. What can an optimizer not do, what a real qc can do?

What's to say the NSA or black budget of some country didn't already secretly build a quantum computer? I'm sure they wouldn't tell anyone so they could take full advantage.

I believe it's already been establish that this is not an actual quantum computer.
I also remember hearing somewhere that the main reason for this is that its 512 qubits are not entangled with each-other or something. Having 512 individual qubits does not allow for quantum algorithms to be executed.

I made pretty much the same thread but it got moved (https://bitcointalk.org/index.php?topic=240411.0).

Grover's Algorithm is the best known SHA2 quantum algorithm. As previously mentioned, all it does is quadruple the difficulty, and then we're back to normal.

The real problem is that Shor's algorithm makes wallet theft by cryptanalysis into something that's actually possible on paper, and the best known quantum-safe digital signature schemes would push each transaction into the tens-of-kilobytes range. Good luck making Bitcoin even work on such schemes without 100MB blocks.

I guess we'll have to wait and see  ;D

Only if ...
a quantum computer capable of implementing Shor's algorithm on a 256 bit key scale (think tens of thousands of qubits)
AND
said computer can break keys in a reasonable timeframe at reasonable cost
AND
only if the public key is known

the last part is relatively simple assurance.  Don't reuse an address. :)

Mm, no good.

See, when you spend from the address, your public key is exposed, but the spend isn't yet committed to the ledger. An attacker will have about a 5-minute window to crack your public key and double-spend your coins (and if they make the window, they're more likely to get into the ledger than you, because they can afford to lose most of the money in transaction fees - you're the one footing the bill, after all). What's worse, they have the ability to attempt a double-spend against every such transaction - against every unconfirmed transaction on the network.

Only way around it is if miners stopped taking transactions from the network, and instead switched to a model where you submit your spends to your favorite (trusted!) pools directly.

And just like that, Bitcoin loses its trust-free property - which was the whole point from the beginning.

Your assumption is that you can break a 256 bit key in 5 minutes, can do so economically even with relatively small sums.  If possible (and that certainly is not certain) a limited trust model could be used only transitionally.

Say one has a large sum of Bitcoins at addresses with an unknown (to the attacker) public keys.  The protocol could be expanded to include new address types which are resistant to QC.  However how does one transfer to the new address. 

Well it could be:
a) ultra paranoid - mine a transaction myself in secret or under contract.
b) send directly to a miner I trust
c) send as multiple transactions each emptying a single address under the assumption that it is not possible or economical to break a 256 bit key in the time to create the next block.*


* On c if one has 10,000 BTC at a single address it may warrant a real-time attack.  However if one has 10,000 BTC spread across 1,000 addresses one could transfer funds more securely one transaction at a time.  An attacker would reveal their intent AND capabilities irrevocably at a loss of only 0.1% of total value.

Nobody said lack of reuse was a magical bullet but combined with the limited attack opportunity, the cost of an attack, and the ability to design more secure addresses NOT reusing an address at least gives one the option to transfer the funds securely or control the risk of a transfer.

DAndT can you find the exact number of qubits we're looking at to be able to use Shor's algorithm against exposed bitcoin public keys?

This link would make it look like it would only take 515 qubits which means the next generation after the current 512 qubit model will certainly be within range.
http://arxiv.org/abs/quant-ph/0601097

Can we prove that we can't do better than Grover's Algorithm with a quantum system?

That paper deals only with integer factorization (like what is used in RSA, factoring primes).  Bitcoin uses ECC which requires one to solve the discrete logarithm problem.  Generally ECC keys are smaller for the same level of security.  



Here is a paper dealing with ECC and Shor's algorithm
http://arxiv.org/pdf/quant-ph/0301141v2.pdf

QC changes that dynamic slightly but generally speaking it requires more qubits to break ECC than RSA for a particular keysize.  ECC requires roughly 6 qubits per bit of key length (nominal)

Note the 1500 qubits to break a 256 bit ECC key (like what is used by Bitcoin) are logical qubits which do not include any error correction so the number of physical qubits would need to be at least one order of magnitude larger.  

Lastly DWave QC isn't a general purpose QC.  AFAIK it can't implement Shor's algorithm for any keysize.  It is designed to solve specific problems only, namely probabilistic modeling.


So to put it all together, if DWave released a next version which has a true Quantum computer and it is general purpose so it could be programmed for Shor's algorithm and advancements in measuring and cooling dropped the error correction to only 20 physical qubits per logical qubit and it could execute 8 million instructions per second and it was more than 30,000 qubits and available at a reasonable cost then it might be possible to break a known ECC key and attempt a replacement before the transaction was included in a block.

Can we prove that we can't do better than brute force with a Turing machine?