15 ms·
IBM casts doubt on Google's claims of quantum supremacy
- unnouinceput 7y agoQuote 1: "The Google group reiterates its claim that, in 200 seconds...." Quote 2: " ...by tweaking the way Summit approaches the task, it can do it far faster: in 2.5 days." Well, it's still 200 seconds vs 2.5 days, so I'd say the claim kinda stands. I know I would definitely buy the computer with 200 seconds vs the one with 2.5 days.
- Graphguy 7y agoQuantum supremacy is more about quantum computers being able to do something that classical computers could never do (1). I think that's the heart of the controversy. I'm quite sure Quantum has already proved faster for certain use cases already (2) 1. https://twitter.com/NatureNews/status/1186969282632134656?ref_src=twsrc%5Egoogle%7Ctwcamp%5Eserp%7Ctwgr%5Etweet https://twitter.com/NatureNews/status/1186969282632134656?re... 2. https://arxiv.org/abs/1904.05803 https://arxiv.org/abs/1904.05803
- apawloski 7y agoNobody is denying that the quantum system performs the task faster. The question is whether it performs a task that can't feasibly be performed by a classical system. That is what the researchers are specifically referring to when they say "quantum supremacy." 2.5 days is feasible. 10,000 years is not feasible.
- theon144 7y agoNot sure it's that clear cut, as per the blog post[0] linked elsewhere in this thread[1]: > Recall that a quantum supremacy demonstration would be an experiment where a quantum computer can compute in 100 seconds something that requires a classical computer 10 hours. (Say.) >The Google experiment actually showed that a quantum computer running for 100 seconds PLUS a classic computer that runs 1000 hours can compute something that requires a classic computer 10 hours. 0: https://gilkalai.wordpress.com/2019/10/13/the-story-of-poincare-and-his-friend-the-baker/ https://gilkalai.wordpress.com/2019/10/13/the-story-of-poinc... 1: https://news.ycombinator.com/item?id=21334403 https://news.ycombinator.com/item?id=21334403
- Veedrac 7y agoAccording to Scott Aaronson this claim is incorrect. > Next he said that the experiment is invalid because the qubits have to be calibrated in a way that depends on the specific circuit to be applied. Except, this too turns out to be false: John Martinis explicitly confirmed for me that once the qubits are calibrated, you can run any circuit on them that you want.
- bigYahnz 7y agoIf the WebSphere shit heads are able to beat out Google on this...
- IshKebab 7y agoNot really though - they just said it wasn't quite as supreme as Google said.
- iherbig 7y agoIBM's response to Google called "On 'Quantum Supremacy'" has this to say: "Because the original meaning of the term “quantum supremacy,” as proposed by John Preskill in 2012, was to describe the point where quantum computers can do things that classical computers can’t, this threshold has not been met." In other words, "quantum supremacy" is not being used as just a buzzword. So yeah, IBM is casting doubt on Google's claims of "quantum supremacy" because "supremacy" doesn't just mean "better than everything else."
- excalibur 7y agoBut it's still pretty fuzzy. If we agree that 10,000 years on a classical system is supremacy but 2.5 years isn't, where's the cutoff? 25 years? 250? An average human lifespan? Edit: Thanks guys for pointing out where I misread the article, leaving mistake intact so the replies make sense.
- fourthark 7y ago2.5 days, as reported by IBM, is more clearly feasible. But you’re right, it is a subjective judgement.
- htfu 7y ago2.5 _days_, not years. A still fuzzy and arbitrary but imo somewhat elegant cutoff would let feasibility be set by the market and technological development, in the sense of something not being worth throwing compute at _now_ because the timescale of work is slow enough that future classical efficiencies will progress (much) quicker.
- AlexCoventry 7y agoFor market forces to be meaningful, the calculation would need to provide value to someone. At the moment the desired output is simply "a distribution which is hard to simulate classically," so assessment in terms of market value would be very premature.
- deleted 7y ago[deleted]
- nautilus12 7y agoSaying that it evokes "white supremecy" is kind of a pathetic move.
- lm28469 7y ago> IBM's researchers argue that the term "supremacy" is in danger of being misunderstood by those outside the rarefied world of quantum geeks. Supremacy means exactly what it's supposed to mean for everyone outside and inside of science. What's the next step, google can't call its pixels "Just Black and Clearly White" because people would be confused about if it is racist or not... The world truly is becoming a weirder place by the minute.
- fourthark 7y agoOr a more boring place as our language shrinks.
- K0SM0S 7y agoEdit: I am definitely wrong about my interpretation (see child post by DashAnimal) ____ Original comment for reference: I really don't think IBM implied the social (and definitely modern, circumstancial) figurative meaning of supremacy. Any tech geek, or history major for that matter, would just read it as "crushing domination", with a strong implication that others won't be able to catch up, ever. You know, like Kings and Empires impose their supremacy on other, lesser powers. In that sense, the expression "quantum supremacy" (QS) is indeed ambiguous insofar as: - it's a convention, a simple "we agree to say that QS means <mathematical definition>" (not a very clear one at that, the concept lacks boundaries). - "supremacy" in QS refers to "quantum", i.e. it's the domination of Q computers versus classic computers; and absolutely not that of the company behind the tech —a recent history of the Fortune 500 makes it emphatically clear that there is no such thing as definitive supremacy for companies. In fact, a certain IBM... [snip] Big blue is apparently vexed, here; but disingenuous linguistically? Not so much in my opinion. More like downplaying —that is their pettiness if you ask me: why not salute the engineering feat, and look at yourself asking "OK guys, how do we win the next step?" In other words, play it fair.
- akjssdk 7y agoThe main takeaway here is figure 1 in this article: they show that for an increasing circuit depth, computation time (on a classical computer) scales linearly. Google claims, on the other hand, that a classical calculation would scale exponentially. This is the basis for the graph in the Google blog [1], which seems to suggest that the Quantum computer can easily reach points (such as qbits=50, cycles=25) which the classical computer would never be able to reach. This is not true, if IBM is right. Their linearly scaling graph proves that they are not nitpicking their input, I would say. [1]: https://ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html https://ai.googleblog.com/2019/10/quantum-supremacy-using-pr...
- AlexCoventry 7y agoSo if they increase the number number of qubits they'll be have a classically infeasible calculation again? Should be interesting.
- lallysingh 7y agoIf the problem is linear, then frankly I don't think anyone cares if there's a QC implementation.
- AlexCoventry 7y agoMy impression is that the difficulty is linear in the depth of the calculation, exponential in the number of qubits.
- deleted 7y ago[deleted]
- Symmetry 7y agoThere are many problems where the best known quantum algorithm is asymptotically better than the best known classical algorithm but, as far as I've heard, nobody has ever found a case where the best quantum algorithm can be proved to be better than the best classical algorithm. So there's always going to be a danger of this happening no matter what problem you attack.
- nevi-me 7y agoI'm a layman on this, but reading IBM's rebuttal, it seems that they're saying "you can't say that a conventional supercomputer would take 10'000 years because you haven't accounted for spilling to disk and other optimisations". I understand that some of these optimisations might be on the processing logic, but doesn't this end up being like comparing apples to oranges? I understand that there's also what seems to be technicalities around what is "quantum supremacy", but I assume that on a 'processor against processor' basis, this is still significant. Am I oversimplifying things?
- apawloski 7y agoThey're saying explicitly: >We argue that an ideal simulation of the same task can be performed on a classical system in 2.5 days and with far greater fidelity. and therefore >Because the original meaning of the term “quantum supremacy,” as proposed by John Preskill in 2012, was to describe the point where quantum computers can do things that classical computers can’t, this threshold has not been met.
- sanxiyn 7y agoNo, the point is that spilling to disk allows you to run classical algorithm linearly, so there is no exponential speedup. I elaborated this in detail here: https://news.ycombinator.com/item?id=21334025 https://news.ycombinator.com/item?id=21334025
- cjbenedikt 7y agoPretty rich by IBM to voice any criticism after its "Watson" disaster.
- CJefferson 7y agoThis had been a consistent problem with quantum computers - - they come up with a quantum computer that can basically do one thing and compare it against a general piece of software not tuned for that problem. Once the software is tuned for the exact problem it is much closer in performance to the quantum computer. The same thing arises with dwave.
- tarsinge 7y agoYes « Tuned » with 250 Petabytes of storage
- CJefferson 7y agoTo be fair, that exact computer is, I believe, what Google originally composted against.
- mellosouls 7y agoRepeating my question from the other thread: If IBM can cast doubt by describing a 2.5 day classical run, why not just do that instead, and blow the claim out of the water? There were a couple of responses (thanks) but I still don't understand - it looks like it's not as easy as they imply.
- hktuotroi 7y agoThey didn't say 2.5 days on a laptop. They probably mean on a bunch of datacenters together. That is expensive. Google implied their supremacy over all of the world computers combined together.
- Invictus0 7y agoThey are talking about 2.5 days on the world's most powerful super computer, which Google had previously claimed would take 10,000 years to complete the task.
- ehsankia 7y agoThese calculations of 2.5 day and 1000 years, they're calculations based on specific parameters, right? Could they just prove it on a smaller version of the problem instead? Can they do a version of the problem which takes maybe 1m on with IBMs algorithm and 1 year with Google's?
- joshuamorton 7y agoAaronson's blog goes into this. The problem is exponentially difficult to simulate in the number of qibits. Each quibdit doubles the storage required. 25 quibits can be done on a laptop. 50 requires a supercomputer. 53 is just small enough to fit on the biggest supercomputer. 55 doesn't fit. There's also an alternative algorithm that requires less space, but it takes longer.
- mannykannot 7y agoSuch a demonstration would prove nothing of importance, partly because the issue is not how fast a particular run takes, but how running time grows with the size of the problem. More significantly, the issue is whether the paper's argument for its original claim is sound, and that would be best addressed by showing where it goes wrong. For a brief and clear explanation, read this excellent post: https://news.ycombinator.com/item?id=21334025 https://news.ycombinator.com/item?id=21334025 If you don't follow what is being said there, reposting your question will not help.
- stevespang 7y agoFrom 10,000 years, down to 2.5 days on your classical box - - - is still not 200 seconds that Google claims to have achieved - - - IBM'ers
- deleted 7y ago[deleted]
- akimball 7y agoEmbarrassing for IBM (the snarky quote of Dario Gil) and for Science (the snarky headline).
- ace_33 7y agoIs 200 seconds not faster than 2.5 days?? I don't see the argument here
- sanxiyn 7y agoThe key claim is linear scaling. IBM: "The runtime of our simulation method scales approximately linearly with the circuit depth". That directly contradicts what Google wrote in the paper: "... algorithm becomes exponentially more computationally expensive with increasing circuit depth".
- altares 7y agoSupremacy does not mean simply faster. That is already proven. It means impossible to do on a classical computer.
- djhaskin987 7y agoI'm sure you mean infeasible. "Impossible" goes back to a problem's decidability. If a problem is undecidable, there's no way you're going to find its solution by switching computational models; classical computers can do anything a quantum computer can do, just "slower".
- akvadrako 7y agoNot if they use up all the energy in the visible universe or they need so much power they collapse and form a black hole. Real quantum computers should be able to do calculations that are that powerful, assuming we can prove the best classical algorithms are really exponential.
- ascii_only 7y agoIt is difference between with this quantum chip we can brake encryption that would take 100000 years in 30 minutes or it would take us 50 years.
- orbifold 7y agoThe quantum circuit based simulation actually has much worse accuracy. A classical computer can simulate the class of circuits they are proposing with linear increasing runtime (as opposed to exponential as Google claims) and _much_ higher accuracy according to IBM.
- andrewla 7y agoWe should probably amend the link to point to IBM's actual blog post, https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/ https://www.ibm.com/blogs/research/2019/10/on-quantum-suprem...
- deleted 7y ago[deleted]
- lisper 7y agohttps://news.ycombinator.com/item?id=21334307 https://news.ycombinator.com/item?id=21334307
- dang 7y agoOk, changed from https://www.sciencemag.org/news/2019/10/ibm-casts-doubt-googles-claims-quantum-supremacy?rss=1 https://www.sciencemag.org/news/2019/10/ibm-casts-doubt-goog.... Thanks!
- perseusprime11 7y agoI wish IBM chose their words carefully here.
- poelzi 7y agoI know they don't understand λ_spm, I know their quantum orbit is totally fucked up. I know that they don't understand short magnetic field condition. I know their particle sizes are all off. (Reason you can' unify QM and GR btw). They are lacking the relativistic micro-curviture sourrounding the nucleus. I know they don't understand superconductor correctly, thats why the fractional quantum hall effect is a mystery. Superposition does not mean what they think (over interpretation). Most of the ideas about Quantum-Computers can never be done. You can run certain optimizations when you can model some applications as energy states, but very limited spectrum of applications.
- andrewla 7y agoAlso of note is Gil Kalai's updated take on the experiment [1]. The heart of the complaint is that the quantum computer's solution to this problem relies on a calibration process, which is done on a classical computer and requires resources orders of magnitudes higher than the quantum portion of the computation: > The Google experiment actually showed that a quantum computer running for 100 seconds PLUS a classic computer that runs 1000 hours can compute something that requires a classic computer 10 hours. EDIT: Just as a note, lest you dismiss Kalai as an outsider/crackpot, you can look at the researchers who show up in the comments on the blog post. [1] https://gilkalai.wordpress.com/2019/10/13/the-story-of-poincare-and-his-friend-the-baker/ https://gilkalai.wordpress.com/2019/10/13/the-story-of-poinc...
- mantap 7y agoIf I understand his point correctly, it's not the calibration per se that is problematic, but whether the calibration means that it only performs for a small subspace of inputs, which raises the question how large is that subspace?
- andrewla 7y agoMy understanding is that the calibration could only be feasibly carried out for smaller circuits where simulating the circuit classically was possible. At issue is whether the calibration is generalizable; whether the calibration carried out for a particular small circuit C was reused to simulate another circuit C', or whether fresh calibrations were carried out. Page 17 of the supplemental data [1] shows the calibration process in schematic, and appears to indicate that the calibration was necessary for each input circuit C, since the graph showing the fidelity improving with iterations of the calibration is labelled "b, Data from a two-qubit XEB experiment." The water is admittedly muddy, and hopefully clarification will be forthcoming from some quarter to determine whether Kalai's particular critique has substance. [1] https://static-content.springer.com/esm/art%3A10.1038%2Fs41586-019-1666-5/MediaObjects/41586_2019_1666_MOESM1_ESM.pdf https://static-content.springer.com/esm/art%3A10.1038%2Fs415...
- zaroth 7y agoCrucial question - is the calibration a one time effort where the same calibration can be used to calculate any number of results within the calibrated space? In other words, can you amortize the calibration cost across 1,000 runs and come out an order of magnitude ahead?
- rokalakt1337 7y agoIs IBM still relevant?
- jfengel 7y agoThey are doing a whole bunch of research, including in quantum computing. It's hard to tell what's really "relevant" in research; if you knew, it wouldn't be research. IBM stands as good a chance as anybody to produce a real-live quantum computer, and they've hired the people who are in a position to judge what Google really has and hasn't achieved thus far.
- nickpsecurity 7y agoI’m with them. My two problems when reading the original argument: They rigged the benchmark to be something quantum-specific before saying classical computers couldn’t do it. I get why. I’d just rather it be something they both could do, classical having great algorithms, and quantum one outperforms it many-fold. An old example was factoring. I’m sure there’s other examples out there. Maybe try to simplify them for low-qubit circuits. The biggest gripe: basing the argument on what classical computers can’t do. Can’t is an assumption that’s been dis-proven about so many things so many times. Who knows what new algorithms people will come up with down the line doing what we previously couldn’t do. I want an argument that’s instead based on what can and has been done vs the new thing being done. I similarly preferred constructivist logic to classical since the latter was assuming things didn’t exist. Universe surprises me too often for that stance. Another thing about these is the comparison to supercomputers. Me personally, I don’t care if the quantum computer outperforms supercomputers. I’m looking at practical QC like anything else: does it do the job more cost-effectively than alternative solutions? That cost includes hardware, any leasing/licensing, maintenance, specialists, etc. If it does, then they’ve achieved something for me. If it doesn’t, then QC was an implementation detail for a system that didn’t make the cut. FPGA’s are already an example of how this might play out. They’re friggin amazing with all kinds of potential. I’d love to have a desktop loaded with them with libraries using them to accelerate my apps. Them being invented and improved wasn’t enough for that, though. The duopoly, esp supported by patents, has kept prices of high-performance FPGA’s way too high. It would be better if they were priced more like flash memory with the synthesis software being more like mass-market A/V software. We’d see an explosion of use. Instead, the legal system allowed the inventors to keep competition and innovation at low levels to maximize profit. I expect the same with practical QC for at least 20 years. I’ll still be using a mix of NUMA, GPU’s and FPGA’s while early adopters mess around with quantum computers.
- sanxiyn 7y agoYour biggest gripe can't be solved. P vs PSPACE is a great unsolved problem in computer science (almost as big as P vs NP), and since PSPACE can simulate quantum computer, any solution to your gripe immediately leads to resolution of P vs PSPACE.
- ajay-d 7y agoIBM's head of research had a pretty confident statement the other day: "I’m convinced there are more quantum computers working here than the rest of the world combined, in this building," Dr. Gil said. [1]https://www.nytimes.com/2019/10/21/science/quantum-computer-physics-qubits.html https://www.nytimes.com/2019/10/21/science/quantum-computer-...
- nappy-doo 7y agoIsn't Google's result published in Nature -- a peer reviewed journal? Shouldn't IBM just do the same with their refutation?
- sanxiyn 7y agoI am sure this exact rebuttal is already sent to Nature and under review and will be published in the next issue.
- deleted 7y ago[deleted]
- kerng 7y agoSeeing this be published on Science Magazine is interesting by itself. Its like IBM and Google at a high level work on different problems. IBM is focused on research and public discussion of the problem space. Google on the other hand is focusing on marketing using fancy terms like "supremecy" that can easily be misunderstood by the public.
- d0ne 7y agoIf a worst case to simulate on a classical computer is 2.5 days (per IBM's blog) then they should either: 1. Actually preform the experiment per their approach, compare the results, and provide tangible proof in the coming days. or 2. Retract their claims. In either case, exciting times ahead. [Edit: Yes, I read their published paper[1] which only claims it is possible to achieve and does not perform the same experiment. 1. https://arxiv.org/pdf/1910.09534.pdf https://arxiv.org/pdf/1910.09534.pdf]
- reikonomusha 7y agoThey need the world’s most powerful supercomputer to do that, and it may not be available for them to use.
- snops 7y agoThe linked paper shows the "classical system" is the Summit supercomputer[1], using 128 petabytes of disk. Still, its remarkable that the choice of a different simulation algorithm by IBM that trades memory for CPU usage cuts the time from 10,000 years to only 2.5 days. [1] https://www.olcf.ornl.gov/olcf-resources/compute-systems/summit/ https://www.olcf.ornl.gov/olcf-resources/compute-systems/sum...
- justicezyx 7y agoI believe this is a healthy exchange. Boom & bust cycle appears wasting more resources and progressing slower overall than a steady refinement.
- knzhou 7y agoFollowing the quantum supremacy controversy is very frustrating. It gets constantly framed as a decisive step that changes everything, which is wrong. But then there's also an opposite and equally wrong reaction that any challenges to the claim prove that quantum computing doesn't work at all. The reality is that quantum computing technology has been improving at the same steady pace for decades, and quantum supremacy was recently invented as a concrete but not very useful goal that people could realistically aim for in the near term. That is a totally standard and legitimate way of guiding technological progress. The problem is that quantum supremacy is vaguely defined (what does "infeasible on any classical computer" mean? what computers can you use, and for how long?) but it is presented to the public as a sharp boundary -- which means that every company in the field has a huge incentive to claim they are the first. This IBM claim is not a fundamental objection. Given that everything they say is correct, Google could still achieve quantum supremacy by their standards just by incremental improvement, slapping a few more qubits on. So why even bother disputing Google's claim? Because it will set them back a few years, and that's enough time for IBM to make a claim of its own. That's why academics, who have no stake in what company gets the hype, will just consider this whole episode rather distasteful.
- sanxiyn 7y agoQuantum supremacy is a big deal. It is a goddamn experimental evidence against Extended Church-Turing Thesis. If you never believed ECT (for example, all physicists seem to think ECT is obviously false) it may not matter to you, but it still is a serious claim. Yes, Google probably can achieve quantum supremacy by slapping a few more qubits. But a few more qubits were, in fact, not slapped yet. So quantum supremacy is very much not achieved, and Google should not claim so.
- knzhou 7y agoIt is serious, but as I said, it's also vaguely defined. We can continue quibbling over details for decades to come. Suppose Google does slap on more qubits so the time estimate goes up from 2.5 days to 25000 years. Is that quantum supremacy yet? Well, maybe if you used literally every classical computer in the world in parallel, and also used a very optimized algorithm, it would only take 2.5 years, which isn't that long if you're patient. So you could say that Google needs to slap on yet more qubits. That's why arguing over whether it's really quantum supremacy is just not useful. People can always move the goalposts, so we might as well ban that word from discussion. The underlying fact, which nobody is debating, is that quantum computers are regularly doing tasks that are harder and harder for classical computers to. And yes, the ECT is obviously false -- or at the very least, not obviously true. I'm surprised at how many CS people think it is some unassailable principle. Most CS courses devote precisely zero time to non-classical models of computation. If you've never studied a model of computation that could challenge ECT, then how can you be so sure of it? This is like being absolutely certain that I am the tallest person in the world, and refusing to ever leave my house to check.
- readams 7y agoScott Aaronson now has a detailed analysis and covers the IBM claims as well: https://www.scottaaronson.com/blog/?p=4372 https://www.scottaaronson.com/blog/?p=4372 The high order bit is that the IBM claims do not cast much of a shadow over the claims of quantum supremacy and still show the same exponential difference.
- dang 7y agoThere's a thread discussing Scott Aaronson's post here: https://news.ycombinator.com/item?id=21335907 https://news.ycombinator.com/item?id=21335907
- c3534l 7y agoI don't trust anything IBM says. They have a long history of lying and misleading that continues to this day. It's about as trustworthy as Facebook saying you shouldn't be concerned about privacy on Facebook.
- rahuldottech 7y agoDo you have any sources that elaborate on your claims of IBM being misleading?
- thesz 7y agohttps://pdfs.semanticscholar.org/9725/c12506f1d77a3e3b1587cd25a06dfc9e3dd7.pdf https://pdfs.semanticscholar.org/9725/c12506f1d77a3e3b1587cd... Quotes: "Fear, uncertainty and doubt (FUD) is a tactic used in sales, marketing, public relations,[1][2] politics and propaganda." and "FUD was first defined (circa 1975) by Gene Amdahl after he left IBM to found his own company, Amdahl Corp.:"FUD is the fear, uncertainty, and doubt that IBM sales people instill in the minds of potential customers who might be considering Amdahl products.""
- jaredtn 7y agoSummary: - Google overhyped their results against a weak baseline. This seems to be commonplace in academic publishing, especially new-ish fields where benchmarks aren't well-established. There was a similar backlash against OpenAI's robot hand, where they used simulation for the physical robotic movements and used a well-known algorithm for the actual Rubik's Cube solving. I still think it's an impressive step forward for the field.
- a_imho 7y agoAlso AlphaZero vs Stockfish, the setup has/had a big question mark over it as well.
- comnetxr 7y agoThere seems to be a lot of confusion here about the complexity, for example calling the simulation here "in the linear regime" due to IBMs result. This is inaccurate. A source of this confusion is that we need to discuss space and time complexity simultaneously. In the algorithms for quantum simulation (and many other algorithms), there is a trade off between space complexity and time complexity. ELI5: You don't have to store intermediate results if you can recompute them when you need them, but you may end up recomputing them a huge number of times. For the quantum circuit, the standard method of computation gives exponential memory complexity in number of qubits (store 2^N amplitudes for a N qubit wavefunction) and time complexity D2^N, i.e. linear in circuit depth and exponential in number of qubits. For example, under the IBM calculation, 53 qubits at depth 30 use 64 PB of storage and a few days of calculation time, while 54 qubits use 128 PB and a week in calculation time. Adding a qubit doubles the storage requirements AND the time requirements. Under google's estimation of the run time, they were using a space time memory tradeoff. There is a continuous range of space-time memory tradeoffs - USE MAX MEMORY as IBM does, MAX RECOMPUTATION (store almost no intermediate results, just add each contribution to the final answer and recompute everything) and a range of in-between strategies. While I don't know the precise complexities, the time-heavy strategies will have time complexity exponential in both N and D ( 2^(ND) ) and space complexity constant.That's why googles estimate for time complexity is so drastically different than IBMs. Side note: IBM also uses a non-standard evaluation order for the quantum circulation, which utilizes a trade-off between depth and number of qubits. In the regime of a large number of qubits, but a relatively small depth, you can again classically simulate using an algorithm that scales N*2^D rather than D2^N, using a method that turns the quantum circuit on its side and contracts the tensors that way. In the regime of N comparable to D, the optimal tensor contraction corresponds to neither running the circuit the usual way or sideways but something in between. None of these tricks fundamentally change the ultimate exponential scaling, however. As an extra step, you could also run compression techniques on the tensors (i.e. SVD, throwing away small singular values), to make the space-time complexity tradeoff into a three-way space-time-accuracy tradeoff. You wouldn't expect too much gain by compression, and your accuracy would quickly go to zero if you tried to do more and more qubits or longer depth circuits with constant space and time requirements. However, the _real_ quantum computer (as Google has it now, with no error correction) also has accuracy that goes to zero with larger depth and number of qubits. Thus, one can imagine that the next steps in this battle are as following: If we say that Google's computer has not at this moment beaten classical computers with 128PB of memory to work with, then google will respond with a bigger and more accurate machine that will again claim to beat all classical computers. Then IBM will add in compression for the accuracy tradeoff and perhaps again will still beat the quantum machine. So this back and forth can continue for a while - but the classical computers are ultimately fighting a losing battle, and the quantum machine will triumph in the end, as exponentials are a bitch.
- dang 7y agoThere are three threads. The others are: Google's post https://news.ycombinator.com/item?id=21332768 https://news.ycombinator.com/item?id=21332768 Scott Aaronson's post https://news.ycombinator.com/item?id=21335907 https://news.ycombinator.com/item?id=21335907
- 2OEH8eoCRo0 7y agoJudging entirely by my experience with IBM- put up or shut up. Every interaction I've had with IBM the last few years has been shit. It's to the point that all of my confidence in the entire organization is gone, regain my confidence. Put up or shut up IBM.
- papln 7y agoPart of this controversy is reminiscent of the Higgs Boson "God particle" nonsense, where an unscientific catchphrase created by scientists got picked put by the media and a misinterpretation overshadowed the real scientific issue.