512-qubit Quantum Computer

[ktttn]

"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?

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

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.

[johnyj]

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.

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

[johnyj]

"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?

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

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.

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

[notme]

"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?

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

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.

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.

[tinus42]

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

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

[dexX7]

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 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?

[BTCThousandaire]

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.

[symaxian]

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.

[Hyena]

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

[Qoheleth]

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.

[BitSmile]

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 

[DeathAndTaxes]

The real problem is that Shor's algorithm makes wallet theft by cryptanalysis into something that's actually possible on paper

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.

[Qoheleth]

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.

[DeathAndTaxes]

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.

[calian]

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

[Frogcoin]

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

[DeathAndTaxes]

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

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.  

Code:

 80 bit security =   80 symmetric key (AES) = 128 ECC = 3,076 RSA
128 bit security = 128 symmetric key (AES) = 256 ECC = 3,076 RSA
256 bit security = 256 symmetric key (AES) = 512 ECC = 15,360 RSA

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

Code:

algorithm/keysize   # qubits     time
ECC 256                 1500     6.0*10^9
ECC 512                 2800     5.0*10^9
RSA 3072                4096   120.0*10^9	
RSA 15360              30720    50.0*10^9

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.

[Qoheleth]

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

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