Couldn't you break Bitcoin with a quantum computer?
Quantum Computing Explained
21–30 of 51 posts
Re: Quantum Computing Explained
#22Earlier quoted context omitted.
Re: P != NP, I would say that question assumes a certain architecture, so while it might hold for Turing machines, the real question is is a HyperTuring/Turing machine really all there is? I assume you are familiar with Real Computation? https://en.wikipedia.org/wiki/Real_computation I did note the "if real computation were physically realizable" clause, however, I'm not going to be placing bets. > A scalable analog…
>Re: P != NP, I would say that question assumes a certain architecture, so while it might hold for Turing machines, the real question is is a HyperTuring/Turing machine really all there is? No, P and NP are defined by an architecture, there's nothing to assume about it. E.g., P is defined as "problems solvable in polynomial time on a deterministic Turing machine".
I think that you misunderstood what I meant by assumed. If I replaced it with implies would that clear the confusion?
Re: Quantum Computing Explained
#23Will quantum computing kill Bitcoin by rendering the underlying cryptography obsolete?
If it comes down to that, bitcoin will probably adopt some post-quantum signature scheme for new wallets.
Probably.
Re: Quantum Computing Explained
#24Will quantum computing kill Bitcoin by rendering the underlying cryptography obsolete?
> Will quantum computing kill Bitcoin by rendering the underlying cryptography obsolete?
No, as even if the current underlying crypto falls (for whatever reason), the ledger up to that point could very likely endure in a new form.
Outside of the blockchain concept of itself, the oft-ignored indirect gift of bitcoin's longevity is the way it is providing us a new digital mechanism for the international distribution of wealth as more people join, the ledger proceeds and mined coins are exchanged more widely.
Full-disclosure: no horses in this race yet
Re: Quantum Computing Explained
#25Earlier quoted context omitted.
There is a serious misconception in your claim. Yes, analog computers, whether quantum or classical solve even NP-complete problems in polynomial time. No, they can not be constructed in the real world because analog computing does not permit error correction, and in the real world you have to deal with noise. Only very small analog computers (nothing scalable, nothing solving general problems) can be constructed bef…
Unfortunately I have nothing yet to add to your discussion with parent, but I was wondering if the two of you might peek at the following paper, and let me know if and where it fits into the picture: [1] Jose Luis Rosales, Vicente Martin, "Quantum Simulation of the Factorization Problem", 9 Nov 2016. ( https://arxiv.org/abs/1601.04896 )
Disclaimer: I only skimmed the article.
This is pretty cool, but I think the main point of the article is to show an amazing link between number theory and the theory of quantum mechanics, not to suggest a practical quantum algorithm. Although, for certain hardware implementations what they are suggesting might be easier than Shor's algorithm, just because of technical reasons.
Either way, this is not "continuous variable" or "analog" in the sense discussed above. If you are interested about the distinction, you can also check out Adiabatic Quantum Computing, which also seems continuous on first sight, but it is equivalent to the typical model of quantum circuits (the trick being the existence of a "gap" between the ground state which we are adiabatically evolving and all the other states of the system).
I threw a bunch of terminology without defining them, but I would have to leave googling those to you. I would be happy to attempt to answer questions though.
Re: Quantum Computing Explained
#26IBM lets you poke around one of their quantum machines here for free:
https://quantumexperience.ng.bluemix.net/qx/experience
They also include a brief tutorial on how to program for it too.
Re: Quantum Computing Explained
#27IBM lets you poke around one of their quantum machines here for free: https://quantumexperience.ng.bluemix.net/qx/experience They also include a brief tutorial on how to program for it too.
yes! I've been playing around with this while writing this guidebook, and I highly recommend all readers to try it out too, once you've gotten familiar with quantum gates. I'll very likely be adding quantum circuits and their results (from IBM), in an upcoming guidebook discussing some really cool quantum algorithms.
Re: Quantum Computing Explained
#28We are currently living in an exciting time for quantum computing. Most leading companies like Google and IBM have 20 qubit devices. IBM has a 50 qubit prototype [0]. Google has plans to show quantum supremacy in the next couple of months: where a quantum computer will perform a task that cannot be simulated on a classical computer [1]. These near-term (5-10 year) quantum computers will likely be used for simulating…
Number of physical qubits is not a meaningful measure of computational power, especially since fault tolerant computation has not been demonstrated. (In the limit of large errors, a physical qubit has zero computational power.)
D-Wave has a 2000-qubit machine.
Re: Quantum Computing Explained
#29We are currently living in an exciting time for quantum computing. Most leading companies like Google and IBM have 20 qubit devices. IBM has a 50 qubit prototype [0]. Google has plans to show quantum supremacy in the next couple of months: where a quantum computer will perform a task that cannot be simulated on a classical computer [1]. These near-term (5-10 year) quantum computers will likely be used for simulating…
Number of physical qubits is not a meaningful measure of computational power, especially since fault tolerant computation has not been demonstrated. (In the limit of large errors, a physical qubit has zero computational power.) D-Wave has a 2000-qubit machine.
Yes. The researchers at IBM don't use the number of qubits as a measure of the quality of the computer. They use the quantum volume [0]. I said 50 qubits because I was just parroting the press release. The reason I didn't mention D-Wave's machine is because it is not a universal quantum computer. It is a quantum annealer [1].
Google and IBM want their qubits to be of high quality (high coherence times e.t.c). One of the big obstacles right now is scaling up the number of qubits while making sure that their quality is high.
[0]: https://en.wikipedia.org/wiki/Quantum_annealing
[1]: https://www.research.ibm.com/ibm-q/resources/quantum-volume....
Re: Quantum Computing Explained
#30Will quantum computing kill Bitcoin by rendering the underlying cryptography obsolete?
I understand there are two ways Bitcoin is affected by a crypto quantum-computer:
1) A QC is able to derive the private-keys for a wallet's public address, allowing for the theft of bitcoin
2) A QC able to perform the proof-of-work algorithm to mine new blocks at an order-of-magnitude faster rate than currently possible.
Fortunately for 1) (I think) it currently takes 2^512 (?) operations to break the private/public algorithm which is unfeasible to brute-force on normal hardware but a QC brings it down to 2^128 - but that's still on-the-order-of unfeasible - and in the event it ever does happen the blockchain could be changed overnight to use a new keying algorithm. And for 2) it would cause the blockchain difficulty to be pushed-up so high that people with QC machines would see the same ROI as today's industrial GPU and ASIC miners see - plus given that QC computers are horrendously expensive (think: billions of USD for a 50-bit general-purpose QC) it questions why you'd ever try to break Bitcoin as you'd already be a billionaire.