This is promising work that may be interesting in the future: https://arxiv.org/pdf/1902.10171.pdf
This also looks like it could be interesting: http://meetings.aps.org/Meeting/MAR20/Session/W17.7 (Gurobi is a CPU solver for integer and linear programming problems, which are some of the most useful to solve quickly.
There is also: https://ai.googleblog.com/2016/07/towards-exact-quantum-desc...
[1] https://en.wikipedia.org/wiki/Simulated_annealing
[2] https://en.wikipedia.org/wiki/Quantum_annealing?wprov=sfti1
Or maybe that’s entirely naive and the potential for finding faster solutions to real time problems is huge
Day-to-day, we're not really blocked on QC to get important work done.
Breaking crypto is one, I guess, but it’s also one that makes everything worse, so I don’t take that as a useful outcome.
My understanding is that this is what Google has recently claimed to have done, and before that no one had published any serious claims that they had done real quantum computing.
As always, Scott Aaronson has a solid article, some of which I can understand: https://www.scottaaronson.com/blog/?p=4317
Is this relevant? Does anyone have thoughts on this?
https://spectrum.ieee.org/tech-talk/telecom/security/china-s...
Even so, HN is all about the non-relevant stuff, so I'll give my two bits on quantum encryption, which is that it is dramatically easier than quantum computing for short distances, yet even so its not practical to replace our entire internet such as to enable its use. And until the quantum computers are built, there's no need for it
Disagree. One of the coolest things about quantum encryption is that any attempt to eavesdrop a communication is instantly detectable. This is extremely useful for communication between conventional computers.
Truly useful as in profitable, maybe not yet, but it's still early days - it would be like asking Von Neumann how he plans to handle microtransactions
There is nothing that a QC can do that a CC cannot. CC's are universal. They can compute any computable function.
What QC's can do in theory is perform some computations much faster than a CC can. One QC has actually done that, but the computation was of a function that cannot reasonably be called "useful".
The potentially useful things that QCs can do is speed up factoring, protein folding analysis, simulation of chemical reactions... no QC has come anywhere near doing any of those things.
It is of course true that quantum computers are still far from being practical tools for more rapid computation.
No, it's not. In fact, it might not even be true. This is the Church-Turing thesis, and it is unproven and probably unprovable, but nonetheless almost certainly true. An actual counterexample would probably be the biggest news in the history of science.
To be concrete, the current factoring record is RSA-240, a 795-bit number that was factored in November. This required about 2.37 × 10²³ steps of computation by my calculation, and was completed in 4000 core-years. I'm not sure how long it took in real time, nor do I remember how parallelizable GNFS is (I seem to recall it has a bottlenecked step.) To take a thousand times as much computation, you need a 1048-bit semiprime; for a million, 1344 bits; for a thousand million, 1685 bits (which, you'll note, gets us close to the age of the universe on one core); for 10¹² times as much, 2075 bits (close to the age of the universe on a thousand cores); for 10¹⁰⁰ times as much, 43687 bits. The Eddington number is that there are about 10⁸⁰ baryons in the observable universe, so if your computing cores are larger than a single proton, it will take you at least 10²⁰ times those 4000 core-years to factor a 43687-bit number with GNFS, that is, about 4 × 10²³ years.
import math
nfsln = lambda ln: math.exp(((64/9)**(1/3)) * ln**(1/3) * math.log(ln)**(2/3))
nfsln(43687*math.log(2))/nfsln(math.log(
12462036678171878406583504460810659043482037465167
88057548187888832896668011882108550360395702725087
47509864768438458621054865537970253930571891217684
31828636284694840530161441643046806687569941524699
3185704183030512549594371372159029236099
))
Skipping over the Black Hole Era (can your computer survive the Black Hole Era?) all the black holes are conventionally predicted to have decayed via Hawking radiation in about 1.7 × 10¹⁰⁶ years. So a semiprime of 161133 bits, which will take about 2.37 × 10²⁰⁶ operations to factor with GNFS, cannot be factored in that time with the GNFS on classical computers as long as every Xeon-speed processor is bigger than a baryon.
But wait! Maybe your processors can run faster; at the scale of nuclear reactions, a Xeon's few GHz is unimaginably slow. But there's still a speed limit: you can't realistically do more than one operation per Planck time, about 5.4 × 10⁻⁴⁴ seconds. So you can maybe get a speedup of up to about 10³⁵ by making your smaller classical processors go faster, using digital logic mechanisms yet unknown, perhaps shockwaves traveling around a neutron star or something. (All the nuclear reactions we know about run enormously slower than this, though.)
Well, if you can run your proton-sized processors at 10⁴⁴ Hz, that means that by the end of the Black Hole Era you can factor a semiprime of 240857 bits or so on a classical computer.
So that's probably pretty much the limit in the physical universe.
If you can build a quantum computer, using Shor's algorithm, you can factor such a number in about 833586709574 operations (8.3 × 10¹¹) times whatever the constant factor is.
shorln = lambda ln: ln**2 * math.log(ln) * math.log(math.log(ln))
shorln(math.log(2) * 240857)
In conclusion, either your use of "computable" and "CC" in your original comment referred to computability in a particular family of abstract models of computation, not in physically realizable classical computers; or your statements in that post about the relative computing power of classical and quantum computers were simply mistaken with respect to current knowledge, because (assuming QCs are physically realizable) physically realizable QCs can compute things that physically realizable CCs are not known to be able to compute.
I say not known to be able to compute because the question of whether BQP = P is still undecided. It might turn out that classical computers can simulate quantum computers in polynomial time, thus providing a polynomial-time algorithm for factoring — although this is unlikely, we don't have a proof that it's impossible. Even if BQP ≠ P, it's possible that integer factorization is in P, and we just haven't found an efficient algorithm for it yet, despite thousands of years of trying. But it's not the way to bet.
It is of course correct that it would be an enormous and improbable breakthrough for someone to find a way to build a physically realizable computer that can compute things that an abstract, theoretical Turing machine cannot. That would be a counterexample to the Church–Turing thesis.
Yes. But usually "we" (see below for an explanation of why that word is in scare quotes) use the word "computable" in a context where quantum computers are not even in play. Quantum computers have only become a thing fairly recently relative to the amount of time that humans have been talking about computation.
This entire conversation turns on the meanings of fuzzily or implicitly defined words like "useful" and "almost" and "we". But the whole point of quantum computers, the only reason they are on the radar, is that they can potentially do something that classical computers can't do for some not-entirely-unreasonable definition of "can/can't do" and (and this is crucial) that WE MIGHT ACTUALLY BE ABLE TO BUILD ONE THAT REALIZES THIS THEORETICAL POTENTIAL. The jury is still very much out on that, but it's looking more promising than many skeptics imagined a few years ago.
You wrote:
> There are a number of formal models of "hypercomputation" that could compute things that a classical computer can't compute
Yes, that's true, but irrelevant because none of these formal models are physically realizable so no one cares about them (except theoreticians).
int('3'
'4'
'5')
You KNOW what quantum supremacy means. Please don’t nit pick my layman’s description we are all adults here. You know what I meant.
It has to be scaled up much more before it can do useful things, and the scaling process is very difficult and costly. But we now have confirmation that the idea is sound.
Yeah, but they were basically computing noise, and it's bloody difficult to say that the ability to do that is meaningful enough to have claimed "supremacy" already. It's a huge premature celebration for a team that has had incredible difficulty trying to scale up beyond a tiny number of noisy qubits; like, good for them, but the purpose of this effort really seems to be to make for good water-cooler conversation among the Google execs than it is to actually do useful science.
Was that a mathematical proof?