5 ms·

Can I run Shors algorithm on this? If not, how many qubits would I need for that? If so, how do I short bitcoin?

benchaney 9y ago
1. Probably 2. Several Thousand [0] 3. You can't, at least not easily [0] https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attacks https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Qu...
- adventured 9y ago
  3. Yes you can easily. The futures contracts have enabled short bets against Bitcoin. A few brokers have set this week or next as a roll-out for that, in the very near future hundreds of different financial companies will enable shorting via futures for their clients. For example, Interactive Brokers is going live with their shorting this week: https://www.bloomberg.com/news/articles/2017-12-12/bitcoin-bears-can-soon-short-futures-through-interactive-brokers https://www.bloomberg.com/news/articles/2017-12-12/bitcoin-b...
archgoon 9y ago
According to this paper: https://arxiv.org/abs/quant-ph/0205095 https://arxiv.org/abs/quant-ph/0205095 You can implement Shor's algorithm to factor an N-bit number with just 2n+3 qubits. So the 20 qubit processor would be able to factor any 8 bit number (not necessarily faster than a classical computer could, or even a human could, mind you).
- garmaine 9y ago
  As the question was about bitcoin, I'm not sure how prime factoring is relevant.
  - deleted 9y ago
    [deleted]
  - archgoon 9y ago
    > Can I run Shors algorithm on this? If not, how many qubits would I need for that? The question was about Shor's algorithm. The question relating to bitcoin seemed like an aside. https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm Given that the original article was about Quantum Computing, I was more interested in answering questions about Quantum Computing.
    - garmaine 9y ago
      Yes, but bitcoin's authentication is via ECDSA. Elliptic curve discrete log is solvable with Shor's algorithm, but the qubit calculation would be different. Wikipedia seems to indicate that 2330 qubits and 126 billion Toffoli gates would be required for elliptic curves with 256-bit group size, although I wonder if the endomorphism of secp256k1 gives an additional speedup.

1. Probably 2. Several Thousand [0] 3. You can't, at least not easily [0] https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attacks https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Qu...

adventured 9y ago
3. Yes you can easily. The futures contracts have enabled short bets against Bitcoin. A few brokers have set this week or next as a roll-out for that, in the very near future hundreds of different financial companies will enable shorting via futures for their clients. For example, Interactive Brokers is going live with their shorting this week: https://www.bloomberg.com/news/articles/2017-12-12/bitcoin-bears-can-soon-short-futures-through-interactive-brokers https://www.bloomberg.com/news/articles/2017-12-12/bitcoin-b...

archgoon 9y ago

According to this paper: https://arxiv.org/abs/quant-ph/0205095 https://arxiv.org/abs/quant-ph/0205095 You can implement Shor's algorithm to factor an N-bit number with just 2n+3 qubits. So the 20 qubit processor would be able to factor any 8 bit number (not necessarily faster than a classical computer could, or even a human could, mind you).

garmaine 9y ago
As the question was about bitcoin, I'm not sure how prime factoring is relevant.
- deleted 9y ago
  [deleted]
- archgoon 9y ago
  > Can I run Shors algorithm on this? If not, how many qubits would I need for that? The question was about Shor's algorithm. The question relating to bitcoin seemed like an aside. https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm Given that the original article was about Quantum Computing, I was more interested in answering questions about Quantum Computing.
  - garmaine 9y ago
    Yes, but bitcoin's authentication is via ECDSA. Elliptic curve discrete log is solvable with Shor's algorithm, but the qubit calculation would be different. Wikipedia seems to indicate that 2330 qubits and 126 billion Toffoli gates would be required for elliptic curves with 256-bit group size, although I wonder if the endomorphism of secp256k1 gives an additional speedup.