Topic: 512-qubit Quantum Computer (Read 5340 times)

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

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 Grover's Algorithm with a quantum system?

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

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.

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.

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.

I guess we'll have to wait and see 

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 made pretty much the same thread but it got moved (https://bitcointalksearch.org/topic/--240411).

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.

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.

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?

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

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

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

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

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.

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.

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?