Turn down the quantum volume
scottaaronson.com
scottaaronson.com
So it excludes DWave, and the unstable QBits, and focusses on a specific known problem which (I believe) gets closer to e.g. breaking useful real-world unknown value RSA, rather than simply being "how big it is"
As long as a graphics card is just painting pixels its mainly about entertainment. When somebody says "this graphics card can now exhaustively search 20 letter password strings against a known hash string and find your passphrase in under 30 seconds" then its a real issue.
I know it's not gate model, but it does compute using quantum effects, and so any reasonable model of performance has to include for this sort of system.
IIRC D-Wave doesn't like single digit performance indicators, so they're aligned with Aaronson on this for once.
You're wrong about the theory side of things[1, 2], by the way. The discussion around adiabatic quantum computing is weirdly politicized. It's true that D-Wave's computer isn't a universal quantum annealer; but in theory such a thing is equivalent to a gate-model computer.
[1] https://arxiv.org/pdf/1611.04471.pdf
[2] https://iopscience.iop.org/article/10.1088/0256-307X/35/11/1...
From what I can tell, the new hybrid architecture that D-Wave rolled out recently can handle way bigger optimization problems than before, and slice and dice them to fit on the still-fairly-small quantum chip. As long as optimization problems are important (and they seem to increasingly be so), something which can find lower energy states (better solutions) in a shorter time is indeed an advantage.
I for one find it refreshing that they're not always blowing smoke about supremacy the way Google is - instead, they keep pushing forward actual results, like this one published in Nature: https://www.nature.com/articles/s41586-018-0410-x about some spinglass thing I don't understand, but it seems like it's something ideally suited for what they're building.
Furthermore, real optimization problems have high connectivity, high weight cost function terms, and require higher precision than available. The first two will require an unacceptable overhead for fixed topology solvers. DW is not useful for real world optimization problems.
Google on the other hand has actually done something a classical computer can not do
Have you seen their hybrid system they just released? https://www.zdnet.com/article/this-cloud-service-lets-you-us...
Looks like it's a strong contender for people who have bigger, higher-connectivity problems that want to get ready for when the quantum processors are bigger.
The techniques for decomposing a problem and solving the sub problems are a big (exponential) overhead because of frustration effects which require you to look at the entire problem at once.
And for context the PUBO -> QUBO mapping (high order to low order) + topology embedding can blow up the number of variables by an order of magnitude or more. The solution space scales exponentially with the number of variables so a naive solver will again deal with a messy overhead.
(You don't think transistors use quantum effects? Then what's Boltzmann's constant doing in the Ebers–Moll equation?)
I don't see what's "unstable" about a D-Wave qubit; it has an input bias and it has biases about the qubits it is connected to, which you can tune, and quantum coherence is held for long enough for there to provably be tunnelling effects involved in the process of settling down to a ground state.
I think there's a massive lack of understanding about quantum computing that includes a huge bias against these quantum annealers, and it's baffling to me - why wouldn't someone want to see this process work? Certainly their early customers and developers see something there that you might not.
Everyone's obsessed about Shor's algorithm, but it's not the most interesting thing in the world, is it? I mean, do you really want all current encryption to be rendered worthless by whoever owns it? I'm happier to see things go in the direction of solving optimization problems for traffic flow and scheduling instead of military uses, for once.
Calling them "quantum computers" is therefore unhelpful; it is guaranteed to cause people to draw incorrect inferences. It's like describing a slide rule, an op-amp integrator, or a harmonic analyzer as a "computer", except that that was common usage at one time. "Quantum annealers" is fine.
Now, while my comment isn't motivated by any animus against the devices, which indeed might turn out to be useful, I do bear a grudge against the company D-Wave. Specifically, I think they're billing their devices as "quantum computers" precisely because they want people to draw incorrect inferences about them. That is, by using that term, they're intentionally misleading people into thinking their product can do things it can't, in order to get press and investment money. That's a very bad thing to do, and they are bad people.
You ask, "I mean, do you really want all current encryption to be rendered worthless by whoever owns it?" There is a substantial field of "postquantum cryptography", with conferences going back 14 years, that will not be demolished by quantum computers. In particular, SHA-256, AES-256, and things based on them will be fine, and even a lot of cryptographic work from the 1970s will be fine if it uses those modern primitives. There are a number of public-key cryptosystems that should also work, but in most cases, we don't yet have the level of confidence in those that we have in the more conservative designs I mentioned above. The exception is Merkle signatures, which have their own disadvantages.
I have a second, more disturbing objection to your query about what "I want": you seem to be presupposing that my beliefs about D-Wave, and perhaps everyone's beliefs about everything all the time, are determined exclusively by wishful thinking. Consider, perhaps, that this may not be the case — some of the time people may have beliefs that they would prefer to be incorrect, based on, for example, evidence or careful reasoning. In fact, I would assure you that this is true, but certainly you could dismiss that as more wishful thinking on my part.
While it's convenient to attribute people disagreeing with you to "a massive lack of understanding" or to wishful thinking, often it turns out that they instead disagree with you because they know things you don't. Under those circumstances, it can sometimes be more useful to avoid insulting them.
To me you sound like an abacus fan who is waiting for Big Abacus to release an even bigger model, while Turing is labouring away with silly gears and cogs that you see no value in.
Please do not resort to personal attacks on this site. Your repeated insulting remarks do not rise to the standards of behavior we attempt to maintain here.
And its shorthand for "computation which demands more than just inference across the statistical sum of the semi-incoherent output states you see in a sea of things" which as I understand it, is what D-Wave does: it emits all the things, and you do work to find the answer (which usually you knew a-priori btw, another gap in my feelings on QC right now: the worked examples always include for-knowledge of the "right" answer to help decode it from the output states of the QC under consideration)
BTW if I mis-characterize either the state of QC or D-Wave I apologize. I am not in the field. I get this view, from what little I can understand.
What we're forced to imagine is a future 5-10 years from now when they have 10k or 20k qubits, or they're all way more connected together, or something like that; there comes a point at which it will truly be very useful for big problems, and so the speculative player who wants to profit off of this would spend their time trying to actually make working models of something useful in reality which uses such an optimization solver as an engine underneath.
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
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...
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.
[1] https://en.wikipedia.org/wiki/Simulated_annealing
[2] https://en.wikipedia.org/wiki/Quantum_annealing?wprov=sfti1
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.
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 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')
Was that a mathematical proof?
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.
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