I just don't get why you would want to use a quantum computer to generate random numbers. Hardware-RNGs are cheap and have existed for decades. Your CPU probably has one built-in. Some even rely on quantum effects such as shot noise, but where is the advantage over using say thermal noise of a resistor? Both are completely unpredictable.
If you want random numbers just for yourself, all of the approaches you mention are fine to use. The difference is that by using a quantum computer, one could generate random numbers and convince others that the numbers are actually random and not rigged.
My impression is that we've recent just maybe gotten to the point where someone has proven that they have a computer that actually is doing quantum computing for something that would be exponentially slower to do on a classical computer.
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.
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.
can you give an example of a linear programming task that is not currently practical to solve on classical computers but could become so with a huge speed up?
I guess. But we already optimize these things. Without any specific domain in mind, I wonder how much better we could get. Like maybe amazon could find the global minimum cost to route, but right now it’s getting pretty darn close.
Or maybe that’s entirely naive and the potential for finding faster solutions to real time problems is huge
it is huge. that's the only reason people are motivated to implement QC- because in principle then we can break crypto, do QM much faster, solve intractable problems, etc.
Day-to-day, we're not really blocked on QC to get important work done.
They have proved that it's physically possible for quantum computers to do things that classical computers can not. In other words, they have proved that quantum supremacy is real.
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.
I'm not taking issue with your definition of quantum supremacy, I'm taking issue with your (implied) definition of "almost useful". Personally, I don't consider the demonstration of quantum supremacy in and of itself to be useful. It is very interesting, but IMHO it is not (yet) fair to say that QCs have done anything useful, even if you hedge with "almost".
Everything you've been posting is technically correct whereas the parent was technically incorrect, but it's still huge progress and an important step. No, they're not at the useful stage yet, but we can see now that it's inevitable, whether it's years or decades away.
Yes, it's huge progress, but huge progress != useful. And getting to useful, while very likely a matter of when and not if, is not inevitable. The number of qbits in current technology is measured in the dozens whereas the number of qbits needed to do something useful is likely in the thousands (because error correction will almost certainly be needed). QCs don't scale like CCs do. There could be some pretty significant obstacles between here and useful. C.f. fusion power, which has been 10 years away from being useful for about 40 years now.
To nitpick your nitpick, we define "computable function" to mean any function that a classical computer can compute in finite time. There are a number of formal models of "hypercomputation" that could compute things that a classical computer can't compute, if they turned out to be physically realizable, but so far we don't have any evidence suggesting that they are, Tao's theorem about exploding coffee notwithstanding, since actually existing fluids are composed of atoms. So it is correct that quantum computation only allows us to, hypothetically, compute more quickly, rather than allowing us to compute things in finite time that classical computers can't compute in finite time. But it's circular logic, and therefore sloppy thinking, to say "CC's are universal. They can compute any computable function."
It is of course true that quantum computers are still far from being practical tools for more rapid computation.
> it's circular logic, and therefore sloppy thinking, to say "CC's are universal. They can compute any computable function."
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.
Well, that's true if by "computable" you mean "possible to compute in practice in the physical universe" rather than "possible for a Turing machine (or the λ-calculus, etc.) to compute." But usually we use "computable" for the second class, not the first. In particular, you were using it to mean "possible for a Turing machine to compute" rather than "possible to compute in a physically realizable computer" when you said that classical computers are just as capable of performing protein-folding calculations and factoring as quantum computers, only more slowly. In fact, it is straightforward to construct factoring problems that cannot be performed by physically realizable classical computers by any known algorithm because it will take longer than the lifetime of the universe — or, at least, the matter in it.
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.
But that's still a relatively short time; yes, it's 10¹³ times longer than the universe has existed so far (and 10¹³ times longer than it will exist if the Big Rip happens, and about 10¹¹ times longer than it will exist if the Big Crunch happens), but it's possible that the universe might last longer than that. The Stelliferous Era is due to end in 10¹⁴ years, so that's a billion times longer than the Stelliferous Era will last, but red dwarfs will continue burning and providing power for another hundred times that long. Still, though, new red dwarfs will be formed from time to time, and perhaps they could power your classical computer for long enough to factor that number.
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, that's true if by "computable" you mean "possible to compute in practice in the physical universe" rather than "possible for a Turing machine (or the λ-calculus, etc.) to compute." But usually we use "computable" for the second class, not the first.
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).
I'm glad we — by which in this case I mean the human body that is typing this message and the human body that presumably typed the message to which it responds — have come to agreement!
The very long number in the code sample above was breaking HN's layout (it's our bug—sorry), so I added some line breaks to it. Anyone who wants to execute that code should take them out.
That's not BS, it's literally what "supremacy" means. Usefulness is an entirely different metric. And Google didn't come up with the term "quantum supremacy" (which is a rather awkward phrasing anyway), it was well established in QC research prior to anyone actually claiming it.
It's not BS at all. It proved that they could use a quantum computer to compute something that would be infeasible for a classical computer to solve in a reasonable time frame. That's huge. It's a toy computation, sure, but that's still a major step.
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.
> It proved that they could use a quantum computer to compute something that would be infeasible for a classical computer to solve in a reasonable time frame.
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.
I've read enough Aaronson to know that he's just too smug of a person for my liking, honestly. It shines through in everything he writes, leaving a nasty sheen on things.
Quantum encryption as in the IEEE Spectrum article is not the same thing as quantum computing, which is what the original post is about. So no, not relevant
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
> 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.
Hi! What do you think the postquantum security story for Bitcoin looks like? That is, if someone starts being able to build big quantum computers, what vulnerabilities does that create in Bitcoin, and is there a way we can solve them in time to keep the whole system from collapsing?
Oh, no doubt, and I bet you could get someone from any of the current QC companies to go hog wild with ideas over a beer or two, but in practical reality what matters is execution and manufacturing - something that Honeywell, Google, et. al. have been scant on but seems to be core to what D-Wave is doing.
What he advocates makes sense. Marketing for classical computers used to make hay about how fast the CPU was in Khz, Mhz, Ghz. This is done less now since people recognize that is just one of several factors when comparing devices. It's still mentioned, just alongside the architecture, ram, GPU, etc. It can be hard to compare if you're not up on all the differences.
People now buy CPUs and GPUs based on primarily one index: how many fps their favorite games can run at their desired resolution and quality. So manufacturers of QCs should do the same by specifying what problems at what sizes their hardware is best at solving.
I think the function should be something like "number of stable QBits which can demonstrably add to an implementation of Shors algorithm"
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.
Why does any reasonable function need to exclude D-Wave by default? Aren't they the only company with an actual, publicly-accessible, realtime production system you can use?
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.
There is no indication (not even from the theory side) that the D-Wave approach can achieve any speed-up over a classical computer. This is one of the reasons why Aaronson and many others in the field are not taking them seriously. Sure, they will gladly sell you a system, but the whole architecture will most likely never be useful for anything.
> There is no indication (not even from the theory side) that the D-Wave approach can achieve any speed-up over a classical computer.
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.
An adiabatic quantum computer is equivalent to the gate model. D-Wave do not have an adiabatic quantum computer, so there is indeed no reason, even theoretical, to believe their hardware provides computational advantage. The word "quantum annealer" is just a confusing term used differently by everyone, occasionally meaning "adiabatic quantum computer" and occasionally meaning what D-Wave have.
You sound very confident of that, but the fact that investors and developers keep moving to the platform shows that there's a good chance you're wrong.
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.
It remains to be demonstrated that D-Wave has an asymptotic advantage over classical optimization algorithms. Even synthetic spin glass benchmarks specifically designed to give the DW an advantage show no advantage.
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
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.
You can't get thousands of variables with all to all connectivity on a quantum annealer. The noise will kill it. I.e. you will never have such a device with reasonable coupler precision.
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.
Intel, AMD, and NVIDIA also have actual, publicly-accessible, realtime production systems you can use, which also compute using quantum effects. But they don't have stable qubits and so they can't run Shor's algorithm. So D-Wave's machines are similar to AMD's and NVIDIA's, and different from quantum computers, in every relevant metric that distinguishes classical computers from quantum computers.
(You don't think transistors use quantum effects? Then what's Boltzmann's constant doing in the Ebers–Moll equation?)
> But they don't have stable qubits and so they can't run Shor's algorithm. So D-Wave's machines are similar to AMD's and NVIDIA's
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.
I don't mean D-Wave's devices are bad. They're just not quantum computers. They might be a better computational architecture than the mainstream ones for something (although, as I understand it, the jury is still out on that). But they can't run the quantum computation algorithms we've developed over the last 35 years, so they aren't "quantum computers" as we've been using the term for 35 years, and they won't have the effects on, for example, cryptography and our understanding of physics, that we've been predicting that "quantum computers" will have. They can't evaluate quantum circuits, they can't solve problems in BQP in polynomial time with the BQP error bound, and the whole simulation question applicable to quantum computers is inapplicable to them. These statements are not errors of reasoning attributable to some bias I might have against quantum annealers; they're just true.
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.
I still don't see how it's at all reasonable to claim that a device which is proven to execute computation using quantum effects is "not a quantum computer". It's "not a quantum gate model computer", sure, but such things are presently vaporware, so why should they get to claim the term?
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.
As I explained above, we already have a term for "a device which is proven to execute computation using quantum effects"; we call it a "computer". All practical computers (since the transition from vacuum tubes to transistors, and arguably before that) depend on quantum effects for their computation. Transistor action is a quantum-mechanical effect, which is why the Boltzmann constant pops up in the middle of the Ebers–Moll equation.
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.
It's precisely because the D-Wave and other like systems are not yet able to run Shor, I proposed "algorithm like shor".
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.
Yeah, I'm just a sysadmin so I don't really get it either, but I've been following them for a while out of a layman's interest. My understanding is that there was already a body of work in the direction of optimization problems formulated as "Ising Hamiltonians", which is some mathematical construct that it's hard to calculate the lowest-energy configuration for; D-Wave took the most practical route to yielding actual working qubits possible, and can solve those Ising problems on there.
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.
It's a marketing problem. Shor's algorithm seems to be extremely hard to run without cheating by "optimizing" the program on a classical computer that already knows the answer. Nobody wants to announce that they barely managed to factor 21 or something like that, while at the same time trying to convince the public that their system is somehow superior to classical computers.
67 comments
[ 2.7 ms ] story [ 96.9 ms ] threadMy 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.
But that's still a relatively short time; yes, it's 10¹³ times longer than the universe has existed so far (and 10¹³ times longer than it will exist if the Big Rip happens, and about 10¹¹ times longer than it will exist if the Big Crunch happens), but it's possible that the universe might last longer than that. The Stelliferous Era is due to end in 10¹⁴ years, so that's a billion times longer than the Stelliferous Era will last, but red dwarfs will continue burning and providing power for another hundred times that long. Still, though, new red dwarfs will be formed from time to time, and perhaps they could power your classical computer for long enough to factor that number.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.)...
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).
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
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.