4 ms·
I'm just wondering, can we run shors algo yet or no? :)
by exabrial 2y ago
I'm just wondering, can we run shors algo yet or no? :)
- ionwake 2y agoHow would we know
- deleted 2y ago[deleted]
- MattPalmer1086 2y agoNot on a d wave processor, it's not a general purpose quantum computer.
- andyjohnson0 2y agoThe systems made by D-Wave do quantum annealing, not general purpose quantum computation. As such, they are very useful for optimisation problems but they can't run Shor's algorithm.
- bee_rider 2y agoCan they be used to train DNNs?
- dooglius 2y ago> they are very useful for optimisation problems Do you have a source? The HN consensus whenever they've come up in the past is their stuff is useless from both a theoretical and practical perspective, easily outperformed by normal computers, and there's nothing but dishonest marketing going on. If this has changed that seems like a big deal. Ex: most recent thread I found https://news.ycombinator.com/item?id=34217218 https://news.ycombinator.com/item?id=34217218
- cwillu 2y agoNothing has changed. https://scottaaronson.blog/?p=431 https://scottaaronson.blog/?p=431 still applies as much as it ever did.
- abtinf 2y agoWtf, that post is from 2009. 15 years on and this company is still playing the same game and the public is still being taken in by it?
- boothby 2y agoMuch more has been written on the topic in the intervening years, including by Aaronson. I'd challenge cwillu's statement that "nothing" has changed, but I'm a D-Wave employee* so I don't tend to wade in. More specifically, I'm not terribly concerned with what "the public" thinks about our computers. Academic and industrial partners are much more reliable judges of quality. * I do architecture, algorithms and circuit design; not marketing. That said, I'd encourage you to compare our marketing budget against those of IBM, Google, Microsoft, and the other big players in the field -- if the public is to be swayed, it'll follow the splashy marketing.
- cwillu 2y agoSo long as they talk about the number of “qubits” their machines have without prominently clarifying that they're using a heterodox definition of “qubit” and “quantum computer”, I will continue to maintain that nothing has changed.
- GuB-42 2y agoWe have quantum computers that can run the Shor algorithm, we managed to factor the number 21 (=3x7) with it in 2012, I am not aware of any improvement to this day. D-Wave has been used to factor larger integers, but not using the Shor algorithm as it can't do that, it is not a general purpose quantum computer but a specialized "quantum annealer". All of these attempts have involved some kind of trickery, and even the largest numbers claimed to have been factored are all ridiculously small compared to what we can do with classical computers. This is why these attempts are not taken very seriously: the preprocessing steps done with classical computers take much more time than what it would take for that classical computer to find the solution.
- t34h32l4j233l4 2y agoThey used the fact that 21 = 7 x 3 in order to reduce gate-count. The full-Shor has never been run on a hardware device IIRC. (quite-funny when you see everyone and their mom hyping QC).
- odyssey7 2y agoAppear weak when you are strong.
- gosub100 2y agoThis. TLAs have probably had this for years and want to keep the illusion up as long as possible, while also projecting uncertainty to their rivals that maybe they have it. Maybe their communications aren't safe....maybe?
- krastanov 2y agoFrom someone actually working on developing this type of hardware: no, there is no entity in the world that is anywhere close to building a device that can run Shor's algorithm. We will have standardised post-quantum algorithms long before there is a machine to run Shor's algorithm.
- 1024core 2y agoNSA is always 20 years ahead of anybody else, so ....
- jeffhuys 2y agoI really don’t believe that.
- krastanov 2y agoTwo quick points on this: - D-Wave do not claim to be building a general quantum computer (although they willfully muddy the water on this). Their machines in principle can not run something like Shor's algorithm. It is not clear whether in general they will ever be able to run anything better than a competitive classical computer. They are just interesting analog computers that happen to use some quantum effects (almost incidentally). - Shor's algorithm can only run on an error-corrected quantum computer. This will most certainly not be the first "engineeringly useful" algorithm to run on a quantum computer. The a more informative milestone would be "can they run error correction over many rounds of computation". All cutsie examples of a quantum computer running Shor's algorithm on numbers like 21 are just cutesie tech demos that have no chance of scaling. Simulation of quantum systems (drugs, new materials, solar cells, batteries) is a much more plausible near-term application of a quantum computer. If it ever happens it will probably happen many years before Shor's algorithm successfully runs.
- vlovich123 2y ago> D-Wave do not claim to be building a general quantum computer (although they willfully muddy the water on this) While currently the machines they are talking about are quantum annealing only, there is some indication they’re working towards a universal QC [1] [2]. > During the Qubits 2021 conference held by D-Wave, it was announced that the company is developing their first universal quantum computers, capable of running Shor's algorithm in addition to other gate-model algorithms such as QAOA and VQE. As for your other point, > Simulation of quantum systems (drugs, new materials, solar cells, batteries) is a much more plausible near-term application of a quantum computer. If it ever happens it will probably happen many years before Shor's algorithm successfully runs. Isn’t this exactly the kind of stuff that annealing can be applied to? [3] [1] https://www.theregister.com/2021/10/05/dwave_quantum_computer/ https://www.theregister.com/2021/10/05/dwave_quantum_compute... [2] https://en.wikipedia.org/wiki/Quantum_annealing https://en.wikipedia.org/wiki/Quantum_annealing [3] https://www.nature.com/articles/d43747-023-00021-3 https://www.nature.com/articles/d43747-023-00021-3
- krastanov 2y ago> Isn’t this exactly the kind of stuff that annealing can be applied to? Yes, but there is just no evidence that annealers are better at this kind of stuff than classical algorithms. They are "just" an interesting analog computer that can be applied to this type of problems, without a reason to believe that they will be drastically better (in terms of complexity theory). On the other hand, circuit-based digital quantum computers and error-corrected adiabatic quantum computers (which are similar but sufficiently different from annealers) can run algorithms that are better than all known classical algorithms at this kind of stuff (modulo the fact that such computers do not exist yet).
- echelon 2y agoWhen we start to see bitcoin wallets around the world empty, we'll know.
- whynotminot 2y agoThe value of something is contingent upon someone being willing to pay for it. If bitcoin gets broken so obviously by a quantum computer, who would buy the coin? Seems like the least profitable way for someone to announce their new creation. (Unless destroying bitcoin is the whole point, I suppose)
- echelon 2y agoIf your tech can destroy Bitcoin, then it's already over. It's only a matter of time. May as well capitalize or use it as a marketing stunt.
- vdvsvwvwvwvwv 2y agoYou short it (or better short or buy puts on stocks correlated like COIN and MSTR). Then empty exhange hot wallets - people will assume they got hacked as part for the course.
- freetonik 2y agoIt's really a shame that popular media made Shor's algorithm the pinnacle of quantum computing. After 3 years in the industry, I've yet to meet a single scientist, engineer, or organization who's truly interested or does active research in implementing Shor's algorithm. Even Grover's algorithm is more "popular", there are actual demos and small prototypes. But neither are actually the focus of the majority of active development. It's as if the whole world would believe, for some reason, that the goal of AI is to produce punk songs in Farsi, and every news article about AI would be filled with comments "but can it make Farsi punk yet?" Not to downplay the importance of Shor's algorithm, but it's just weird.
- deleted 2y ago[deleted]
- l33tman 2y agoMaybe that says more about the QC field than pop media though? Shor's algorithm truly implies both an algorithmic and practical breakthrough (if possible to implement, the small if). But what other algos are there? It's this, quantum fourier transform, and Grover's like you say. What else can be cool and useful? What is the bulk of the active development, except error correction codes? What should someone start with now if they just enter the QC field?
- freetonik 2y agoOne of the most interesting fields are not algorithms in this common sense, but optimization problems and reliable simulations of quantum systems. For example, certain car manufacturers are investing in on-premise quantum computers not because they want to break encryption or compute timetables, but because they want to develop novel electric batteries, and it's difficult unless you can simulate materials, chemical interactions, etc. Similar motivations exist in pharma (developing drugs), agriculture (developing additives, pesticides, etc.). Another field is quantum sensing, from highly scientific (detecting particles/matter/etc.), to highly down-to-earth (e.g. military). Some properties of QCs can be used to improve the precision of quantum clocks. There are so many exciting fields and applications, where progress is made and will be made before general purpose QC is developed on which you'd run Shor's and Grover's (if ever, in our lifetime). The truth is that QCs are best at niche unique applications related to quantum mechanics, and not so good at general-purpose computing. Sure, pop media is not the source, it's being fed by industry spokespeople, who are ultimately concerned about funding. Many people in the industry do believe that quantum winter is coming. But it's kind of a self-destructive cycle: to continue progress we need funding, to get funding we make promises, to make them efficiently the industry gravitates towards easy-to-blow-your-mind topics like breaking encryption or solving traveling salesman, but chances are we won't have a QC capable of practically useful Shor in the decade or two at best, and by that time funding may decrease significantly because, well, "we can't Shor yet". Examples like PsiQuantum raising almost 1B from partially public sources, and then delaying their ambitious plans does not help anybody. If they fail, the general public and the policymakers would, again, confirm their suspicions that "QCs are a scam".
- sampo 2y ago> can we run shors algo yet or no? Progress with Shor's algorithm: year 2001: 15 = 3 × 5 (IBM) year 2012: 21 = 3 × 7 (University of Bristol) year 2019: factorization of 35 attempted, failed (IBM) https://en.wikipedia.org/wiki/Shor%27s_algorithm#Physical_implementation https://en.wikipedia.org/wiki/Shor%27s_algorithm#Physical_im...
- xhkkffbf 2y agoSPOILER ALERT: It's 7 x 5.
- pclmulqdq 2y agoD-Wave makes ising machines. They will never run a QFT or Shor's algorithm no matter how big the computer gets. It's an analog computer for a specific kind of global optimization problem, not a "quantum computer."