7 ms·
The fact this prize exists is admitting that no one has figured out a use for quantum computers. I have heard this mentioned several times in the last decade o
by fooker 3y ago
The fact this prize exists is admitting that no one has figured out a use for quantum computers.
I have heard this mentioned several times in the last decade or so : "The only thing a quantum computer definitively does better than a classical computer is simulating a quantum computer."
Whether this capability is useful is up in the air.
Note that in practice, classical computers are going to be better at factoring numbers for the foreseeable future.
- becquerel 3y agoEinstein did not have GPS in mind when he was developing his theories of relativity.
- fooker 3y agoSurvivorship bias. There is a lot more science that has not panned out. I'm not saying quantum computing won't pan out, but if it has to there's some fundamental piece that is missing so far. In contrast this effort is trying to imagine and monetize GPS before relativity is discovered.
- leononame 3y agoThat's not the point. The point is that a lot of discoveries and inventions wouldn't have happened if it weren't for researching just for curiosity's sake. Research results will often be useless for product development or capitalism in general. However, focusing research on achieving specific goals only might actually take you further away from your goals. You can't focus on something you don't know exists, you have to discover it first. Maybe, when we have quantum computers, one nerd makes an accidental discovery that enables us to build a room temperature superconductor, and maybe not. But if we don't let people research freely what they're interested in and only things that will pan out, we're going to lose out on a lot of things.
- fooker 3y agoI agree. I didn't say quantum computing research is useless. My point is that we are not at stage that we can offer a small prize and find monetizable uses for it. Fundamental research requires a lot more funding than this.
- vtomole 3y ago> In contrast this effort is trying to imagine and monetize GPS before relativity is discovered. The theory of relativity was discovered decades before GPS. Similarly, the theory of quantum computing was discovered in the 1990s. I agree with the sentiment: trying to find applications for a technology (Large fault tolerant quantum computer) that doesn't exist yet. I just think relativity is the wrong comparison. I do not think that this effort if not worth it due to not having fault tolerant quantum computers. Theory alone can take one very far.
- Sesse__ 3y agoThe theory of relativity does not in any way enable GPS. GPS is subject to (some) relativistic effects, but that is merely a source of bias, which could be corrected for with just an experience-based correction factor even if we did not understand relativity. If relativity did not exist as a physical concept, GPS would be easier, not harder or impossible. (I guess this misconception comes from xkcd in some form?) A perhaps more relevant example: Einstein did not have the cell phone camera in mind when developing his theory of the photoelectric effect.
- karmakaze 3y agoHow could he? there were no cell phones.
- jlev1 3y agoYes, that was the point of the parent comment.
- karmakaze 3y agoThanks for reaffirming Poe's law. I was amused by how 'cell phone' was taken as a given, when talking about a CCD sensor.
- adrian_b 3y agoI believe that most, if not all, cell phone cameras have cheaper CMOS sensors, not CCD sensors (which have a lower image noise, but they need a more expensive manufacturing process, less compatible with modern digital logic and more similar to the manufacturing processes used for DRAM). AFAIK the CCD technology continues to be used only in large-area expensive sensors inside some professional video cameras, in applications like astronomy, microscopy, medical imaging and so on.
- karmakaze 3y agoQuite true even full-frame DSLRs typically use CMOS sensors for some time now. CCD was the first thing that came to mind as 'charge' is right in the name. Out of curiosity, looked up invention dates for CCD 1969 and CMOS 1963 and CMOS sensor 1993 (quite a gap). I was playing with DRAM light sensitivity in the lab in the late 80's. I'm guessing CMOS had too much noise to be useful for a long while or something.
- tgsovlerkhgsel 3y agoWouldn't the D-Wave kinda-but-not-really quantum computer that came out a decade ago be ideal for AI? Annealing sounds like exactly the kind of problem that needs to be solved for ML training?
- pyinstallwoes 3y ago[flagged]
- eru 3y agoWell, but to be useful, it would need to be better at this annealing than a classical computer that just uses good old (pseudo) random numbers.
- versteegen 3y agoI can't find mention of it online, but back in 2013 Lockheed Martin purchased a D-Wave machine because they wanted to use it for "AI", which it turned out meant software verification (of fighter jets?) I believe by searching for the possibility of some kind of invalid program state in a large program, which IIRC they couldn't manage to solve with standard solvers. But in that case the number of qubits in a D-Wave machine appears to me far too few for that to be possible, although I don't know the task exactly. If by "AI" you include operations research (as opposed to statistical machine learning), yes, adiabatic quantum annealing makes sense for certain optimisation problems which you can manage to naturally formulate as a QUBO problem. By 'naturally' I mean it won't blow up the number of variables/qubits, as otherwise a far simpler algorithm on classical computer would be more efficient. I know someone who published QUBO algorithms and ran them on a NASA D-Wave machine, while I myself was using a lot of annealing for optimisation, I didn't want to get involved in that field. But if you want to do machine learning on a large amount of data using quantum annealing, no, that's terribly badly matched, because the number of physical qubits needed is proportional to the amount of data you want to feed in.
- iaseiadit 3y agoThere have been XPRIZE competitions for vehicle efficiency, oil spill technology, more efficient rockets, health sensors, AI systems, genomics, etc. Whether or not quantum computers have practical applications, the prize itself is not evidence of that.
- throwup238 3y ago> There have been XPRIZE competitions for vehicle efficiency, oil spill technology, more efficient rockets, health sensors, AI systems, genomics, etc. All of which are based on existing technologies that have been delivering for decades if not an entire century (vehicle efficiency). Even something as nebulous as "AI systems" has been around for twenty years in the form of Google's original semantic search capabilities. This "Quantum AI" prize, however, is a solution in search of a problem.
- pyinstallwoes 3y agoAlso hilariously they mark stage 3 as "useful quantum computation" as in, none has happened yet. Because, no quantum computer actually exists yet.
- sebzim4500 3y agoI don't get the joke. Has Google ever said anything to imply their current quantum hardware can do anything useful?
- deleted 3y ago[deleted]
- amarcheschi 3y agoI had a guy I knew in a PhD in quantum computing and he told me that he was working on making an algorithm to perform edge detection on an image in O(1), apparently it's possible to do some operation much quicker with quantum computing A paper i found on edge detection https://arxiv.org/html/2404.06889v1#:~:text=Quantum%20Hadamard%20Edge%20Detection%20(QHED,mainly%20works%20for%20binary%20images https://arxiv.org/html/2404.06889v1#:~:text=Quantum%20Hadama....
- fooker 3y agoThis might be a good candidate for Google's prize, unless I'm missing something?
- amarcheschi 3y agoI have literally 0 experience in this field, so I can't comment
- dudeinjapan 3y agoIt's a "solution looking for a problem." Nothing wrong with that. Lasers were theorized in 1917 by Einstein and invented at Bell Labs in 1958, but it took another 20 years before anyone had any idea what the heck to do with them. Now they are the backbone of the internet, among thousands of other applications. Patience, grasshopper.
- DiogenesKynikos 3y agoFrom Feynman's 1982 talk on quantum computing: "[N]ature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy." 0. https://s2.smu.edu/~mitch/class/5395/papers/feynman-quantum-1981.pdf https://s2.smu.edu/~mitch/class/5395/papers/feynman-quantum-...
- fooker 3y agoYou can simulate quantum mechanics with classical computers pretty well, as long as you stick to the copenhagen interpretation.
- DiogenesKynikos 3y agoFeynman's lecture explains why classical computers are terrible at simulating quantum systems. The basic problem is that the number of states grows exponentially with the size of the system. You very quickly have to start making approximations, and it takes an enormous amount of classical computing power and memory to handle even relatively small systems.
- eru 3y agoYes, you have to make approximations and deal with (estimates of) errors. However, quantum computers also have to deal with noise and errors. So far, that's not very different. (If we manage to build error-correcting quantum computers, that might change.)
- DiogenesKynikos 3y agoThe approximations don't just introduce small errors. To simulate quantum systems classically, you need to make drastic assumptions that fundamentally change the nature of the system. This is very different from, say, an approximation that adds in a small amount of noise that you can estimate. The approximations in simulating quantum systems classically can radically change the behavior of the system, in ways that you might not understand or be able to easily estimate.
- throwaway63467 3y agoThe big one is simulation of quantum systems, I don’t get how that’s not enough by itself? Classical computers will never be able to simulate quantum systems efficiently so we need quantum computers for that. In general achieving arbitrary precision control of quantum states is something that will open avenues in many areas like sensing as well, so just from that angle alone a working quantum computer would open a new branch of technological progress. But yeah it’s not guaranteed or even likely that quantum computers will be very useful for many computer science problems, though I’m also optimistic about that given the progress made in the last 30 years. Physics / science isn’t guaranteed to be easy or progress at a steady pace.
- eru 3y ago> In general achieving arbitrary precision control of quantum states is something that will open avenues in many areas like sensing as well, [...] And developing new materials.
- jncfhnb 3y agoWhat does it mean to “simulate” a quantum system and why is that useful
- throwaway63467 3y agoSimulate roughly means designing a quantum computer that mimicks the dynamics of a real quantum system and then run a simulation of that to learn how it would behave under certain conditions e.g. to optimize its parameters. Similar to how we simulate planes or complex circuits today. Quantum systems are everywhere e.g. lasers, cold atoms, transistors or other complex semiconductors, superconductors, enzymes, … I’d say if we don’t develop the ability to understand these systems through simulation we will never progress beyond a certain technological boundary, and quantum computers are a necessary technology for that, just like classical computers were instrumental for the past scientific revolution.
- jncfhnb 3y agoThat sounds… wrong. A simulation of a plane is a model, implemented by humans, of how physics works. A simulation of a quantum system is still a human implementation of mechanics. A quantum computer per my understanding should not be able to add anything to that. You’re not able to just say well this thingy has quantum mechanics and this is a quantum computer so it’s better able to do that. Quantum computers are about speeding up calculations by structuring specific problems such that wrong answers are not calculated. Not emulating quantum mechanics and then pulling the answer from the ether. So… what am I missing here? How could quantum computer aided search spaces specifically aid simulating quantum systems that are not quantum computer aided search spaces?
- fragmede 3y ago"better". There currently isn't a practical way to brute force factor a 4k rsa key with classical computing. doesn't shor's algorithm on a quantum computer make that feasible? that would be a big driver for quantum computing though maybe my understanding is off.
- adrianN 3y agoIt is still open whether we can build quantum computers with sufficiently low noise to run Shor‘s algorithm.
- sgt101 3y agoI've been going down this rabbit hole for a few weeks. Here is what I now think. Cai 2023 (https://pages.cs.wisc.edu/~jyc/Shor-Algorithm-with-Noise.pdf https://pages.cs.wisc.edu/~jyc/Shor-Algorithm-with-Noise.pdf) showed that there is a definite noise floor for Shor's and gave a way to determine this. New algorithms are better than Shor's the in that they are smaller in space and time and more resilient to noise. The state of the art is Ragavan et-al https://arxiv.org/abs/2310.00899 https://arxiv.org/abs/2310.00899. The insight in Cai's about the QFT applies to this algorithm but is less damaging as is scales the noise floor at n^3/2 not n^2. It does seem that it is believed that error correction can be implemented to bring the effective noise down, but it seems that this will be very expensive for large numbers - probably at the scale of previous estimates that indicate that more than 20 million gates will be required to be operational for about 8 hours. The gates required will have to be much better than the current ones (my reading is about an order of magnitude) but this is believed to be on the table for the future. I think these two assertions by the community are debatable but honestly these folks are the experts and we have to go with what they say and respect them on this until it turns out that they were wrong. From what I read it was never the case that Shor's was thought to be any more noise tolerant than other algorithms, but Cai proved it, which is different. There is some debate about the insight, because a chunck of the community is like "this is not helpful and will make us even more misunderstood than we already are" but personally I find this attitude really irritating becuase it's part of the gradual reveal that QC people do about the practicality of the tech. I have no respect for anyone working in QC who doesn't say something like "there is no chance of a practical application in the next 30 years and it's likely that there will be no practical application for 50 years at least. But, this is really interesting and important physics and the techniques we are developing may help us build new classical devices or other quantum devices in a shorter life time." This rider should be mandated for all grant applications and in every popular interview. Instead of which we hear (repeatedly) "whooo whooo QC will crack RSA any day now and help us do machine learning better than you can ever imagine". These folks say "whelp I never said that" but the reality is that they use the idea to seduce politicians and CEO's to give up significant money that they would not if they had a clear idea of the technical problems with QC and which could be used to do a lot of good if spent on things like feeding kids and stopping climate change. This is introducing new security issues because things like QKD and post quantum are problematic in new ways. QKD has end points that are silently vulnerable to people with guns, pliers and evil intents. Post quantum is very computationally expensive and errr suspicious in errr various ways. Introducing it is going to create gaps, and those gaps are unnecessary if current encryption is not threatened. Quantum ML is another thing that make me really annoyed. The algorithms need data to be loaded (surprise) which is extremely problematic and slow, and they need quantum memory - which exists only on a very small scale and the tech used just seems wildly impractical to me. Yet, folks are out there talking about it as if it's coming in the next 5, 10, 20 years! The reality is that we are about 6 major breakthroughs from doing this and once we have those 6 breakthroughs expect that this is going to take 10 years for a practical implementation at least Again - I have no problem with the theoretical exploration of the topic, but to simulate circuits and make claims about how they will work without mentioning that you don't have a clue how to implement the system that will implement it is pretty bad behaviour. All they need to do is put a single line in the paper like "This technique has theoretical interest in Computer Science and Physics but major open questions prevent it being practical for real world problem solving in the near or medium term." I have total respect. 100%. And I think that the work is interesting But no, because "want money" and "don't give a shit about the damage we are doing".
- eru 3y ago> I have heard this mentioned several times in the last decade or so : "The only thing a quantum computer definitively does better than a classical computer is simulating a quantum computer." And, hopefully, other quantum systems in general! I can see that helping with material science. That can have huge multiplier effects on the rest of the economy. But I agree with you, that other serious applications of quantum computers seem to be thin on the ground.
- jacobsimon 3y agoI thought one of the main advantages of QC was that it could (theoretically) solve existing problems that have exponential time complexity with more efficiency. Isn’t the idea that it could make everything faster? Or did I fall for the marketing.
- jncfhnb 3y agoThe basic idea is that for a certain class of problems, you can have the quantum computer skip certain incorrect paths on the calculation by having their probability amplitudes cancel each other out.
- eru 3y agoWith emphasis very much on '_certain_ class of problems'. It's only a precious few problems quantum computers actually help with as far as we know, even theoretically.
- edgyquant 3y agoThis is true in theory but don’t think it’s ever been proven in practice
- eru 3y agoWhich theory are you talking about? See https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3
- 3y ago
- thomk 3y agoTher are plenty of well documented uses for quantum computers, the hardware is just too nascent to fully accommodate them. The most powerful quantum computers today still only have just over 1,000 qbits.
- germandiago 3y agoWhat is the benchmark to have something useful for real-world use in number of qbits?
- vtomole 3y ago20 million physical qubits to break RSA 2048: https://quantum-journal.org/papers/q-2021-04-15-433/ https://quantum-journal.org/papers/q-2021-04-15-433/.
- ziofill 3y agoPhysicist here. It highly depends on a bunch of factors (the type of qubits, the error correcting code, the error rate, the algorithm…), but a ballpark number for practical usefulness is 1 million physical qubits. Keep in mind that qubit requirements keep tumbling down as people work hard to squeeze out as much as possible from a limited number of qubits.
- thegrim33 3y agoAssuming what the public knows about is the state of the art, of course, which I doubt is a good assumption to make. I'm sure major governments have been funneling billions for years into secret projects to be the first to be able to break the (non-post-quantum) communications of everyone else.
- fooker 3y agoI don't think this is totally accurate. If you have significantly better quantum computers, you can solve realistic problems, yes. But what's not being spelled out here is that as far as we know classical computers will still totally smoke them unless you allow a large probability of inaccurate results. And if you are fine with inaccurate results, classical randomized algorithms make it a much more difficult deadline to beat.
- CuriouslyC 3y agoQuantum computers SHOULD destroy regular computers at knapsack style problems and other combinatorial explosions. The problem there is that decomposing real world problems into 128bit combinatorial selection is really hard.
- cwillu 3y agoThere's no reason to think that quantum computers will have any fundamental advantage at knapsack problems; the √n advantage from grovers is not substantial when classical computers are going to be many orders of magnitude bigger than quantum computers for the foreseeable future. If a problem can be reduced to efficiently sampling from the summation of an exponentially large numbers of FFT's, then a quantum computer will destroy a classical computer. It's largely an open research problem whether there are useful quantum algorithms between those two problem classes.
- fooker 3y ago>Quantum computers SHOULD destroy regular computers at knapsack style problems and other combinatorial explosions. You can get a Turing award if you can show this, even theoretically.
- breck 3y ago> no one has figured out a use for quantum computers. It is my understanding that a use is very straightforward: quickly solving problems in the Big(O) Factorial Class (n!). I could be misunderstanding QC though.
- tsimionescu 3y agoYes, you are. Quantum computers are only believed to be faster than classical computers for a handful of very specific problems. And even those are not 100% proven (we don't have a proof that a faster classical algorithm doesn't exist for any of them, except Grover's search, which is only a quadratic speedup, not an exponential one).
- breck 3y ago> only believed to be faster than classical computers for a handful of very specific problems But aren't these problems all in the factorial and exponential classes?
- tsimionescu 3y agoI think they are believed to be, but the opposite is not true. There are a lot of exponential or factorial problems that have no efficient QC algorithm, and are not beleieved to be likely to have one. Also, at least the most famous problem which has an efficient QC algorithm, integer factorization, has no proven lower complexity bound on classical computers. That is, while the best algorithm we know for it is exponential (or, technically, sub-exponential), it is not yet proven that no polynomial classical algorithm exists. The problem isn't even NP-complete, so it's not like finding an efficient algorithm would prove P=NP.
- maxboone 3y agoThe origins of quantum computing give it a clear use: simulation of many-body systems. Number factorization and anything else in BQP is also an use for them.