The Google Willow Thing
scottaaronson.blog
scottaaronson.blog
I will also note that sometimes when I read HN links and think one thing then read the comments and people know enough to take issue with what is being said and even call it out.
Well, maybe you should just try for the hell of it and see how far you get? Becoming fit seems impossible to a morbidly obese 45 y.o, and it is if that person's expectation is unreasonable, but if they just change it to be more reasonable, break it down into manageable routines, then they can get somewhere eventually.
Find some papers, fill many gaps, dedicate a few years in your spare time, in 6 months you'll be 6 months closer than you were.
Whether there's a reason or not, idk, it's something to do, be curious. Don't forget that by dedicating their life to something, they're naturally not dedicating their life to other things, things that you might be able to do, like climbing mountains, making pizza, or coming up with witty banter in social situations.
Thank you for writing them.
Shor's algorithm is from 1994.
You can in general start with these search keywords: qiskit caterpillar yosys.
https://www.quantumplayground.net/#/home
You don't need a "real" quantum computer to mess around with quantum computing and learn how it works any more than you need a supercomputer to play around with algorithms and learn how they work.
Well... guess it's time I start learning quantum computing then
Simple in theory, juggling plates and knives in practice...
Not to be morbid, but…in 6 months you’ll also have 6 months less of your life left to do those things.
In the past few years, I have felt—-whether due to my aging, the chaos of current events, the mindless march of technology, who knows—-that our time here on earth is a gift that we squander at our peril.
I think some would find that bleak and grim, but I consider it an existentialist battle cry. Make a list of those things that someday you’d like to say you’ve done, or know, or have built, or have given to others…and do one of them.
Yes but - it's up to each individual to decide on their own definition of 'squandering'. Ultimately everything we do is in service of our own search for meaning in life, and learning for its own sake can absolutely fulfil that role.
The time passes anyway.
All the more reason to spend it on things that matter to you. The opportunity cost of six months spent deep in abstract CS papers is six months not spent teaching your daughter to play guitar, visiting that place you always dreamt of seeing, finally finishing that book on your nightstand, etc.
I guarantee thats more time than most people will spend teaching their kids any musical instrument.
Just spend a week mapping out what you do ans how long it takes you every week and I'm pretty sure you can find double digit hours spent somewhere, maybe even right here on HN
For me, four hours a week is sufficient to stay up-to-date on an active research area but making forward progress requires at least twice that.
> You are awake for at least 16 hours of the day, you telling me you cant find 4 hours a week to read a paper? So 4/112 hours or around 3.5% of your week...
Using awake hours as the denominator is misleading because most people have other non-discretionary time commitments besides sleep. For me I'd estimate ~60h/wk sleep, ~50h/wk work/commute, ~30h/wk non-discretionary upkeep of children/relationships/home/body. Assuming 8+h/wk to make progress out of the remaining ~28h/wk of discretionary time means I can handle about three non-discretionary priorities. (Pre-kids I could handle about five.)
Therefore, when someone with a job says "I don't have time" to pick up a hobby, skill, language, outside research area, instrument, volunteer position, etc I don't interpret their statement as meaning it is physically impossible for them to rearrange their schedule to accommodate it. I (and I suspect most people) interpret the statement as them admitting that it's not one of their ~3-5 non-discretionary priorities.
There are legitimately busy people and then there are people who wish they could achieve X if only they had time but don't put any effort into making time for that.
HINT: if research is directly related to your job, allocate time to it during working hours, those aren't 40-45 hours of time a company gets to take from you and also get benefits from your out of work time. I'm reasonably sure your boss would happily let you allocate an hour every now and then to improving yourself as an employee and if they don't, well... The internet has their usual answer to that even though I don't always agree.
Sometimes this is the result of black-hat products hacking their dopamine cycle, in which case screentime or a friend can help. However, I've found that in some cases staying on top of the zeitgeist like this is actually in someone's 3-5 priorities. In that case saying they have "no time" for X is another way of saying that using TikTok is a higher priority than X for them. (Baffling to me, but a valid choice.) I similarly know people who spend a non-trivial amount of time on other "useless" activities like watching TV shows, playing video games, reading novels, learning esoteric languages, growing plants with no utility, commenting on online forums, etc. Who am I to judge if they find it valuable?
So as technically imprecise as "I don't have time" is, I understand why people use the expression. When someone suggests that I should volunteer for a cause, participate in an activity, go to an event, learn a skill, watch a TV show, read a particular book, learn a language, etc and I tell them that it isn't a high enough priority to displace any of my existing priorities, they sometimes get defensive and/or attempt to litigate my current priorities.
> I'm reasonably sure your boss would happily let you allocate an hour every now and then to improving yourself as an employee
Absolutely, this is a major perk that knowledge workers should take advantage of. I'm spending quite a bit more than "an hour every now and then" to learn about LLMs and accessibility because they are in the intersection of my interests and my job responsibilities. However quantum computing (or game design, solar vehicles, gardening, etc) are not in that intersection and would count against one of my discretionary priorities.
I will always try to convince people against mindless media like ticktok, well unless it's in their life goals to be an influencer but that may also be an issue...
Other cauaes though, sure I don't mind if you don't have time to volunteer etc.
At 70 nobody will be proudly say "oh yes I've spent years reading up on this topic!".
Just like I don't know how to build a solar panel or how to do organic chemistry.
When it comes to that category of your own interests, I don't really think one can afford not to spend time on them, lest you hollow yourself out. Whether any one thing is worth the time over another, like grinding papers vs travel, they're not always mutually exclusive; although trying to do both in parallel might be silly, I personally like to shift my attention periodically. I'll go and spend a few months learning, and then go adventure. I don't that much, but I'm happy to meet up with friends and do that too, and it means taking time away from video games or learning, and that's important too.
Not an easy goal, good luck!
I'd use the example of hiking literally all day without the promise of a good viewpoint; I'd invite the person out, with only a plausible estimate of the time required, and they'd want to just find something that takes less time so they can schedule something afterward. Along the way, they'll be rushing to meet that time, because this is just exercise or whatever to them, and in some way they aren't at peace the idea that we're both just here in the forest maybe chatting maybe not, there's no tangible justification for the mission.
Another type of person would replace tangible outcomes with the feeling that they always need to be learning, regardless of what it is, because it's intrinsically virtuous, and they also sometimes fail to be at peace with doing something for no reason, or nothing at all.
I've wavered between these over the years, and now I'll learn something because it's a clear weak spot, or I can imagine how it might be interesting, and if I don't have anything else that's more compelling (including doing nothing) I might give it a go. What's different now than a few years ago is how much I respect serious time involvement. Anything I decide is worth trying to learn is something I need to feel capable of dedicating serious energy to, at least in the first year; if I can't or don't want to, then maybe I won't, and I shouldn't fool myself into thinking I should or will, because I have other things going on. If I'm going hiking, that's my day, that's it, that's the whole activity, if anyone wants to join me then that's great, they need to accept the same mentality or they can stay home. If we happen to get back before the bars close, then that's great too. I might find Swahili interesting too, and if it seemed worth trying, I'd dive in on the basis that I'd just get a sense for how a different language works, and that there might be something surprising along the way, which to me is inherently valuable.
However, that's also exactly why I didn't say anything like "You should learn X", because it's just a curiosity, and there's many curiosities. For example, last year I failed an interview at Apple because they got the impression my hardware-level knowledge of computers wasn't there, and it wasn't, and that convinced me to finally try and work my way through NAND2Tetris, which I'm now about 3/4's of the way through, and feel was incredibly rewarding even though the net benefit is likely nebulous. I was out of work then for about a year and a half, and it helped me pass the time well too, in a much more spirit lifting way than grinding through yet another rest api project or frontend framework.
Eventually a project may come along that I'll feel is compelling enough to dedicate some serious time to AI/Crypto, and I'll consider it then, but if I were to just try and learn it for no reason at all—including innate curiosity—I don't think it'd stick.
https://metacpan.org/pod/Quantum::Superpositions
(Sadly, the Perl Module has to do classical calculations underneath to get the Quantum computing code/functions to execute, but it let you experiment with silly little QC toys - "Look, I factorised 15 in parallel!!!")
Quantum error correction is one of those “wow” moments like euler’s identity, it is worth making the effort to get there.
Any suggestions for where I can learn more about the theory of quantum computation?
You can't know everything but knowing what you don't know and when to rely on someone else to know what you don't know and to confidently quote or use what they know that you don't know, is a skill too.
"Critical thinking", and I suspect you do know how to do that and whilst this blog post might be somewhat impenetrable it is still might be useful to you, even as just general knowledge. Use your skills to determine - for you and you alone - whether it is truth, false or somewhere in between.
Besides, a mental work out is good for you!
Spent yesterday afternoon and this morning learning what I could. I'm now superficially familiar with quantum coherence, superposition, and phase relationships.
In other words, you got this. Now I gotta learn linear algebra. brb.
One thing I did forget to mention is that you can play with this stuff in a "familiar to software developers" way in our VS Code playground at <https://vscode.dev/quantum/playground/> . This is a 'code first' approach familiar to software developers leveraging VS Code integration. The playground is pre-populated with a bunch of common quantum algorithms.
You can also install the extension in VS Code directly (<https://marketplace.visualstudio.com/items?itemName=quantum....>), you don't need to run it in the browser, but even in the browser it has a fully working language service, debugger, evaluator, quantum simulator, package management, etc. It's all written in Rust and compiled to either Wasm for the browser and VS Code extension, or native code for the Python package. (I'm thinking about doing a video on how we build it, as I expect it will interesting to this type of crowd. Let me know if so).
Disclaimer: I work in Azure Quantum on the product mentioned. AMA.
I'm unsure I am even asking the right questions. I'd appreciate any direction you can give me!
What do you hope to be doing in 5 years? Architecting quantum solutions? Reselling or consulting on cloud solutions? Building quantum applications?
I think the quantum space will have quite a bit of progress in 5 years, but I think most experts in the space (of which I'm NOT one) think we're still over 5 years out before there's broad adoption on running quantum programs with significant business value. (i.e, it'll still largely be researchers and bleeding edge adopters).
Opinions are my own, etc.
Linear algebra does seem to be a hard wall I've seen many smart software engineers hit. I'd honestly love for someone to study the phenomenon and figure out why this is.
So, I really agree that it's about timing and curriculum. For one, it appears somewhat abstract until you really understand geometrically what's happening.
So, I surmise that most non-mathematicians don't have quite the mathematical maturity to absorb the standard pedagogy when they first approach the subject.
Yes, but most people, like me, never gain even remotely intuitive understanding of it and quickly forget it after passing a few dreadful exams. Just like with most other math.
For now, people were saying the same thing about mainframes in the 60s
If you want to go deeper into quantum computing, I can highly recommend Scott Aaronson's own book, "Quantum Computing since Democritus"[0]. Although I have a background in physics and math, I found his style lively and engaging with truly unique and compact recapitulations of things I already knew (two come to mind: his description of Cantor's diagnalization argument, and the assertion that QM is the natural consequence of "negative probabilities" being real. The later is a marvelous insight that I've personally gotten a lot of use out of).
It's also useful to understand the boundary of what quantum computing is. At the end of the day what we'll see are "QaaS" apis that give us the ability to, for example, factor large primes. You won't need to know Shor's algorithm or the implementation details, you'll just get your answer exponentially faster than the classical method. I would not expect desktop quantum computers, languages designed for them, or general user software designed to run on them. (Of course, eventually someone will make Doom run on one, but that's decades in the future.)
https://www.alibris.com/booksearch?mtype=B&keyword=quantum+c...
Being part of a highly educated elite group like that has some huge benefits, but they have also shackled themselves to an insanely specialized and highly difficult niche. I can't imagine the stress they are under and the potential for despair when dedicating years to something with so much uncertainty.
I'm wondering if it's time for me to switch professions and give up compsci / software altogether.
Many pre-trained models and libraries that hide most of the complexity.
However, my sentiment is rather this: I wouldn't pass an assembly programming interview, but I know enough about it so that I know what I don't know. Same with embedded programming, fpgas, machine learning stuff, big data, networking, etc etc.
As for LLMs and quantum computing, I don't even know the basics, have no idea about the broader science behind it. Worst is that I don't feel like it interests me, I don't feel excited about it.
I guess if tomorrow I had to work with them, I could learn some "libraries that hide the complexity", but it leaves me with an empty feeling about these new technologies. Hence the existential question if I'm "too old for this" career path at all.
About 15 years ago I became interested in really advanced cryptography, because it was presented at a Bitcoin conference I went to. If you think AI is hard, that's kindergarten stuff compared to the maths behind zero knowledge proofs. And because nobody cared at that time outside of a handful of academics, there were no tutorials, blog posts or anything else to help. Just a giant mound of academic papers, often undated so it was hard to even figure out if what you were reading had been superseded already. But it seemed important, so I dived in and started reading papers.
At first, maybe only 5% of the words made sense. So I grabbed onto those 5%. I read a paper, put it down for a while, re-read it later and found I understood more. I talked to the researchers, emailed them, asked questions. I read the older papers that initiated the field, and that helped. It was a lot of work.
You know what? In the end, it was a waste of time. The knowledge ended up being useful primarily for explaining why I wasn't using those algorithms in my designs. A lot of the claims sounded useful but ended up not being so for complicated reasons, and anyway, I was mostly interested in what you could do with the tech rather than the tech itself. Turns out there's always a small number of people who are willing to dive in and make the magic happen in a nicely abstracted way for everyone else, for any kind of tech. QC is no different. There's, as far as I can tell, very little reason to learn it. If QC does ever "happen" it'll presumably 95% of the time be in the form of a cloud service where you upload problems that fit a quantum algorithm worked out by someone else, pay, and download the answer. Just like LLMs are - another topic where I was reading papers back in 2017 and that knowledge turned out to not be especially useful in regular life.
Learn the details of stuff if it naturally interests you. Ignore it if it doesn't. Being a specialist in an obscure domain can occasionally be like striking the jackpot, but it's rare and not something to feel bad about if you just don't want to.
Here’s a sneak peek from Lecture 6: https://youtu.be/6rf-hjyNl4U
You can sign up via: https://quantumformalism.academy/mathematical-foundations-fo...
to me the whole endeavor smells like a bait and switch or something. I remember about 10 years ago canada or someone had at least a few hundred qubits if not close to 1000 of them, but these were physical qubits, and don't represent anything, really. Google's 105 finally makes a "fast enough" single qubit or at best half of a pair.
https://podcast.clearerthinking.org/episode/208/scott-aarons...
First of all, the formalism/practice gap is real: taking API calls and updating a database correctly has a mountain of formalism around it. And it is not easy to get right! Concurrent sequential processes and distributed systems theory and a bunch of topics have a huge formalism. It is also the case that many (most?) working software engineers have internalized much of that formalism: they “play by ear” rather than read sheet music, but what matters is if it sounds good.
Second, whether it’s quantum computing or frontier machine learning or any other formalism-heavy topic? It’s eminently possible to learn this stuff. There’s a certain lingering credentialism around “you need a PhD” or whatever, I call BS: this stuff is learnable.
Keep hacking, keep pushing yourself on topics you’re passionate about, but don’t consign yourself to some inferior caste. You’re just as likely as the next person to be the next self-taught superstar.
Thing is, I don't know how to get out without on the one side giving up my comfort zone (well paid, doable work), and on the other side gaining responsibility / being looked at as an expert in any field (that's where impostor syndrome and responsibility aversion comes in). I really need a holiday lol.
Why should you? I agree with your sentiment, super advanced quantum physics is probably out of reach for 99% of the population (I'm estimating here but I think it's reasonable to assume that's the average IQ of the physics PHDs who can actually understand this stuff to a deep level). You can probably make the effort to understand something about what's going on there, but it will be very superficial. Going advanced quantum physics takes a huge amount of effort and an incredible capacity for learning complex things. And even the advanced physics guys don't and can't understand a bunch of very elementary things about reality, so it's not as if the feeling of not understanding stuff ever goes away.
React 19 is out and it's time to hit the docs eh to solve the same exact problem we've had for the last 30 years in a slightly better (or NOT) way.
Source: teaching beginners piano for years. Of course sheet music looks like gobbledygook, until you've spent a bit of time learning the basic rules!
I’ve made a list of 4-5 things at which I want to be extremely good at in 10 years compared to where I’m today. Now I just spend time on those. I occasionally wander into something new just for the sake of diversion.
TL;DR: whatever you’re doing, there’s probably someone who wishes they were doing it instead.
> Only an elite few get to touch these machines.
But lately many can run quite a lot of AI models at home. Doesn't require too crazy of a setup.
Why not build something software fun at home that doesn't involve a DB? Maybe using some free AI model?
I did experiment lately: automatically "screenshot" a browser and ask an AI to find the URL and ask if the URL and site looked like a phishing attempt or not. Fun stuff (and it works).
I tried installing one of these "photo gallery" in a Docker container (where you can put all your family/travel pics and let anyone on your LAN [or on the net] browse them). I saw some of these have "similarity" searches features. I also saw that SAM / SAM2 (Meta's Segment Anything Model) was plenty quick: some people are using these to analyze video frames in real-time. So I was thinking about sending all my family pictures through SAM2 (or a similar model: I saw some modified SAM2 to make it even faster) and then augmenting the "similarity search" by using the results of SAM2. For example finding all the pictures about "pool", etc.
And why limit myself to pictures? I could do family vids too: "Find all the vids where that item can be seen".
Possibilities at the moment seems endless: times are exciting if you ask me.
How about solving a problem someone that’s not a quantum researcher would care about. Give me traveling salesmen with n=10. Or factor a 10 digit number. Something.
Until then quantum computers are in the same category as commercial fusion. Long on “breakthroughs”, zero on results.
Look at cancer researchers for a nice contrast. The annual number of “breakthrough that could cure cancer!1!” announcements have dropped to near zero while steady, real progress is being made all the time.
> The next challenge for the field is to demonstrate a first "useful, beyond-classical" computation on today's quantum chips that is relevant to a real-world application.
Getting crypto coins to move over to post-quantum seems to me to be a much harder problem than e.g. rushing out a new version of TLS or SSH.
The key to Satoshi's original coins is a rapidly _apprecicating_ secret at the moment, but paradoxically also one that might immediately crater out if someone actually discovers a generic way to break the crypto involved.
I'm not an expert on this angle of things but: as far as I know, Shor's quantum algorithm breaks both RSA (factoring) and DSA (finite-field discrete logarithms). But I'm not sure if it works the same way against elliptic curves - or at least you'd probably need a bigger computer to attack the same level of security.
It's not clear to me if a quantum computer could effectively attack SHA256, either: Shor definitely does not help, Grover cuts the search space from 256 to 128 bits but that's still not practical to iterate over.
Elliptic curve cryptography is also based on the difficulty of computing discrete logarithms, which makes it vulnerable to Shor’s algorithm. Unfortunately, while the increased difficulty of brute forcing ECC with a classical computer allowed it to use smaller key sizes to achieve security equivalent to older algorithms like RSA, the smaller key sizes make ECC attackable with fewer qubits.
We are decades and decades away from the technology to be able to do that. The problem for Google is trying to find a practically useful use case a bit sooner than that.
The better question may be why the rest of us don’t care about the same things. If we sat here in 2014 and pondered why neural net folks cared about particular problems, I’m not sure where we’d be. Faith and Vision are truly spiritual things, even in tech.
Popular science magazines are quite different. They publicize for views, and nobody cares how accurate they are.
Presentations of a public company are somewhere in between. The target audience is not nearly as qualified as a scientific grant panel, but they can sell shares or even sue the company if it underdelivers on its promises.
We'd been managing around human capabilities since around 2004 in certain tasks.
There were actual industrial applications in 1994.
You'd have to go back to the 1950s to find the type of research in neural networks that was of no practical application to anyone but NN researchers.
Yes. "Quantum computers will revolutionize computing by year 2100" is a claim I can take seriously. "Quantum computers will revolutionize computing real soon now" is a claim I am not taking seriously.
And yes, the 1950s AI researchers also boasted that it would take only months, what ended up taking many decades: https://en.wikipedia.org/wiki/Dartmouth_workshop
How much money should we putting into something with a time horizon longer than the working careers of everyone here?
They didn't solve any new problems. They took old ideas and just cranked the dial all the way up to 11. Then an entire market formed around building the hardware necessary to crank it even further. This all represents a revolution in computing power not in what neural net folks were doing at all.
> Faith and Vision are truly spiritual things, even in tech.
Yea, but money isn't.
The reality is that we had to solve vanishing / exploding gradient problem. That wasn't accomplished by getting faster compute, but by devising better architectures and using activation functions with properties we needed.
That's how ANNs got out of the "somewhat useful" into "really useful" categories. Hardware helped move it even further. But without the work of computer scientists and mathematicians we would never get to the point when the hardware matters.
I was working on an alternative approach of using much smoother activation functions at much higher precision, 64 bits in production using GPUs and 128 in testing using CPUs. It worked well enough that I don't think the field would have slowed down much. The only issue is that we'd be working on networks that are 10 times smaller.
Also, I'm really struggling to identify with the naysaying around this thread. Every year we improve the error correcting (bringing the number of physical qubits needed to represent a logical qubit down), and increase the number of qubits. So what exactly is the worry here? That the secrets the government have dragnetted won't be relevant anymore by the time we crack it, due to the prevalence of Kyber?
(disclaimer: I don't think that's what is going on here, I'd have to dig into it more)
Then they claim it would take a gazillion years to simulate on a conventional computer. Which I’m sure is true.
Really? SAT is the question "I have a set of constraints. Is it possible to obey all of them at once?"
If it were impossible to use that question to answer any other questions, I'm pretty sure there would be a lot of interest anyway.
It's kind of like how a lot of people care about the determinant of a matrix, which is exactly the same question set against a much more restrictive set of possible constraints.
More relevantly, that line of experimentation is specifically to refute the notion that something unexpected will happen with the physics to break the computational scaling.
Nobody with any credibility is claiming that the current experiments are useful for anything practical.
And more importantly, the solution is not actually verified in any way. It might be wrong.
I don't understand (as a complete laymen) why the milestone isn't something classically hard but easily verified (in line with you). I feel like it's weird because people have spent a lot of time telling me how trivially quantum computing will break encryption that defeats normal computers.
They're far from being able to do any such thing, so posing such milestone would make the field look stagnant and thus be a bad marketing and hurt the money stream. The "milestones" are chosen so that they are plausibly reachable in short time relevant to patrons/investors, because people working on this need to constantly demonstrate progress.
That category being: "Technologies We Will Have Unlocked Within 10 Years"
Running the quantum computer causes 'new timelines' to be created. Though so would ordinary atoms just sitting there; the tricky thing about quantum computers is making it so the split is temporary.
So the quantum computer gets split into multiple versions of itself, does some computation in each, and merges the results. This isn't map-reduce; there's a strictly limited set of ways in which you can do the merger, all of which are weird from a classical perspective.
You can argue for MWI based on this, because the computations that got merged still had to happen somewhere. It's incompatible with Copenhagen, more so the bigger and longer-lasting the computation gets. It's not, strictly speaking, incompatible with pilot wave theory; but pilot wave theory is MWI plus an additional declaration that "Here, you see this timeline here? That's the real one, all the others are fake. Yes, all the computation needed to instantiate them still happens, but they lack the attribute of being real."
Though that makes PWT incompatible with computationalism, and hence with concepts such as mind-uploading. Which is a bullet you can choose to bite, of course...
No wait, it’s actually God who exists in the wave collapse, and His divine intervention does the computation.
That's close to retrocausality which is a serious theory/interpretation of quantum mechanics.
The big question being the PR approval process.
There is nothing stopping you putting probability distributions in git and branching them.
That’s what’s stopping you from doing anything continuous in git.
Quantum computing isn't classical computing. It isn't a Turing machine. It is a fundamentally different kind of information processing device, making use of non-classical physical phenomena.
I'm not a defender of Copenhagen, but the wave collapse interpretation has no difficulty explaining quantum computation. A quantum computer creates extremely large, complexly entangled wave functions that upon collapse result in states that can be interpreted as solutions to problems that were encoded in the sequence of operations that setup the entangled wave function. The Everett interpretation is easier to think about in my opinion, and I prefer thinking in terms of MWI when I try to make sense of these results. But it is not necessary.
Computer science is the study of universal Turing machines and their application. But Turing machines are only “universal” in the sense that they can represent any statement of mathematical logic, and that can (we believe) be used to simulate anything we can dream up. But there are intrinsic performance limitations of Turing machines, studied by algorithmic theory, which are artifacts of the Turing machine itself, not physical limitations of the universe we live in. That searching an unordered list with a serial processor takes O(n) time, for example. Grover showed that there are non-Turing machine quantum processes that could be used to perform the same computation in O(sqrt(n)) time. That doesn't mean we need to go looking for "where did that computation actually happen". That doesn't even make sense.
Sorry, my crank meter is dialed to 11 right now and I don't think this is worth spending further time on.
He recently did a great podcast with Kurt Jaimungal [1]. In the interview he explains that every year he searches for a good way to introduce his students to quantum mechanics, and every year he's ended up being unsatisfied with the approach and started again.
One year he decided to attempt describing systems with traditional mechanics, using probabilities (stochastic mechanics). He worked at it and worked at it, assuming that he would eventually have to take some leap to cross the chasm into the world of gauge theory, Lie Groups, and Hilbert spaces. What he found is, to his surprise, the math just seemed to fit together at some point. That is, he found a mapping, just as the path integral is a mapping into the math of the wave function, and it just kind of worked. He had been under the assumption that it shouldn't.
It turns out, that in doing his stochastic mechanics, he had used mathematical descriptions that were indivisible. That is once a given process began, it could not be sliced into smaller and smaller time slices. It had to complete and yield a result. This was what he called a non-Markov stochastic process. Apparently all previous attempts at this used Markov processes, which are divisible like Hilbert vector calculations or the path integral.
It turns out that things like "collapse" of the wave function, and all the quantum weirdness arose from how the math worked with the wave function and Hilbert space, not from anything intrinsic to the mechanics of the universe (at least that's what his equivalent math was telling him). So in his stochastic non-Markov model, there is no collapse, just decoherence. There is always a result, and the intermediate states (where all the quantum oddities live) aren't real.
He mentions being really disappointed at seeing all the magic of quantum mechanics just kind of vanish. From what he could tell, it was just a trick of the wrong kind of math.
That's not quite right. TM's in general are not universal. The "universality" of TMs has to do with the existence of a universal TM which is capable of emulating any other TM by putting a specification of the TM to be emulated on the universal TM's tape. The reason this matters is that once you've built a universal TM, you never have to build any more hardware. Any TM can then be emulated in software. That result is due to Turing.
The relationship between TMs and mathematical logic is of a fundamentally different character. It turns out that any system of formal logic can be emulated by a TM (and hence by a UTM), but that is a different result, mainly due to Godel, not Turing. There is also the empirical observation (famously noted by Eugene Wigner [1]) that all known physical phenomena (with the exception of quantum measurements) can be modeled mathematically, and hence can be emulated by a TM, and hence can be emulated by a UTM. But it is entirely possible that a new class of physical phenomena could be discovered tomorrow that cannot be modeled mathematically.
But here's the thing: no one has been able to come up with any idea of what such a phenomenon could possibly look like, and there is a reason to believe that this is not just a failure of imagination but actually a fundamental truth about the universe because our brains are physical systems which themselves can be modeled by mathematics, and that is (empirical) evidence that our universe is in some sense "closed" under Turing-equivalence (with quantum randomness being the lone notable exception). That is the kind of universality embodied in the idea that TM's can emulated "anything we can dream up". It's called the Church-Turing thesis [2] and unlike the universality of universal TM's it cannot be proven because a counterexample might be discovered at any time.
[1] https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness...
[2] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
Of course you can model quantum measurements! And Wigner certainly knew so.
No, you can't. You can statistically model the results of multiple quantum measurements in the aggregate but you cannot model the physical process of a single measurement because there is a fundamental disconnect between the physics of quantum measurements and TMs, namely, TMs are deterministic and quantum measurements are not. There is a reason that the Measurement Problem is a thing.
> Is the wavefunction epistemic or ontological?
https://news.ycombinator.com/item?id=42383854
Now we're talking about measurements which are indisputably a part of the territory.
Presumably measurement involves interaction with 3 or more degrees of freedom (i.e., an entangled pair of qubits and a measurement device). This is something, for most types of interactions (exclude exactly integrable systems for the moment), classical or quantum, we cannot analytically write down the solution. We can approximately solve these systems with computers. All that to say, is that any solution to any model of an 'individual' measurement will be approximate. (Of course, one of the key uses of quantum computing is improving upon these approximate solutions.) So what type of interaction should you pick to describe your measurement? Well, there is a long list and we can use a quantum computer to check! I guess part of the point I am trying to make, is when you open the box of a measurement device, you enter the world of many body physics, where obtaining solutions to the many-body equations of motion IS the problem.
Yes, but with quantum measurements you cannot even approximate. Your predictions for e.g. a two-state system with equal amplitudes for the two states will be exactly right exactly half of the time, and exactly wrong the other half.
"probabilistic Turing machines can be defined as deterministic Turing machines having an additional "write" instruction where the value of the write is uniformly distributed"
I remember that probabilistic Turing machines are not more powerful than deterministic Turing machines, though Wikipedia is more optimistic:
"suggests that randomness may add power."
Does a probabilistic Turing machines needs aleatory uncertainty? (would have called this ontological but (1) disagrees)
Epistemic uncertainty would mean her:
We don't know which deterministic Turing machine we are running. Right now, I see no way to use this in algorithms.
(1) https://dictionary.helmholtz-uq.de/content/types_of_uncertai...
BTW, see this:
https://arxiv.org/abs/quant-ph/9906015
for a valiant effort to extract randomness from determinism, and this:
https://blog.rongarret.info/2019/07/the-trouble-with-many-wo...
for my critique.
You do if you want to model individual quantum measurements.
But he hasn't met my Dungeon Master...
For example in statistical mechanics you work with ensembles of microstates. That doesn't mean thermodynamics is fake and only F=ma is real. Models are tools for understanding the behaviour of systems, not a glimpse into god's simulation source code where the hidden variables are.
If we assume that the experimenter has free will in choosing the measurement settings, so that the hidden variables are not correlated with the measurement settings, then it can be shown.
https://en.wikipedia.org/wiki/Bell%27s_theorem#Superdetermin...
But it we are less strict on the requirement of the free will assumption, then even local hidden variables are back on the menu.
Note also that superdeterminism is unfalsifiable. Since we are finite beings living in a finite universe, we can only ever have access to a finite amount of data and so we can never experimentally rule out the possibility that all experimental results are being computed by some Cosmic Turing Machine churning out digits of pi (assuming pi is normal). But we also can't rule out the possibility that the moon landings were faked or that the 2020 election was stolen by Joe Biden. You gotta draw a line somewhere.
BTW, you might enjoy this: https://blog.rongarret.info/2018/01/a-multilogue-on-free-wil...
I think the many worlds interpretation of quantum mechanics is also unfalsifiable. The annoying thing about quantum mechanics is that any one of the interpretations of quantum mechanics has deep philosophical problems. But you can't choose a better one because all of them have deep problems.
Yes, that's true.
> all of them have deep problems
Some are deeper than others.
How do you know this? What is the model? Can an AI come up with the Incompleteness Theorems? It can be proven ZFC that PA is consistent. Can an AI or Turing Machine or whatever do the same?
EDIT: I’m equating “our brians” with consciousness.
Consciousness so far appears to be something that can’t be modeled mathematically. Can a Turing Machine conclude that while it can’t prove the consistency of the axiomatic system it works under if one embeds that system in a larger system then it could be possible to prove consistency?
Aren’t you assuming super determinism? What if consciousness is not “computable” in any meaningful way? For example suppose the theoretically most efficient mathematical model of consciousness requires more variables than the number of particles in the observable universe.
That doesn't tell us anything though: Almost every single physical phenomenon we can start to model mathematically looked impossible at some point in history. Just because something's hard is not a reason to expect it's magic.
If consciousness is somehow un-model-able, that will most likely be for a different reason, where the premise itself is somehow flawed, like how we can't bottle phlogiston or calculate the rate of air turning into maggots.
Something that is impossible to accurately be modeled mathematically is not magic.
But we are now way off topic.
I don't. But it seems like a plausible hypothesis, and I see no compelling evidence to the contrary.
> Can an AI or Turing Machine or whatever do the same?
Can you?
If a Turing Machine can’t prove that it can’t prove the consistency of its axiomatic system from within that system but that it could from within a larger system but I can then this is evidence against your belief. At least as I see it.
I have the minority view that the Incompleteness results (the proof of them) are a limitation of artificial intelligence.
OK, but note that you've moved the goal posts here. Your original question was:
> Can an AI come up with the Incompleteness Theorems?
There is a difference between coming up with those theorems, and being able to reproduce them after having been shown how. There can be no doubt that an AI can do the latter, it's not even speculative any more. ChatGPT can surely recite the proof of the consistency of PA within ZFC.
> I have the minority view that the Incompleteness results (the proof of them) are a limitation of artificial intelligence.
Yeah, well, there's a reason this is the minority view. How do you know that the incompleteness results don't apply to you? Sure you can see that PA can be proven consistent in ZFC, but that is not the same thing as being able to see the consistency of the formal system that governs the behavior of your brain. You don't even know what that formal system is. It's not even clear that it's possible for you to know that. It's possible that your brain contains all kinds of ad-hoc axioms wired in by millions of years of evolution, and it's possible that these are stored in such a way that they cannot be easily compressed. Evolution tends to drive towards efficient use of resources. So even if you had the technology to produce a completely accurate model of your brain, your brain might not have the capacity to comprehend it.
History is full of people making predictions about how humans will ultimately prove to be superior to computers. Not a single one of those predictions has stood the test of time. Chess. Go. Jeopardy. Writing term papers. Generating proofs. Computers do all these things now, and they've come to do them in the span of a single human lifetime. I see absolutely no reason to believe that this trend will not continue.
While I personally may not have come up with the Incompleteness results humans did. The discussion is about human intelligence in general (particularly applied to bright people) not about my own intelligence and its limitations.
The second order Peano Axioms are categorical while the first order Peano Axioms are not. The first order axioms are used precisely because it was the dream of Hilbert and others to reduce mathematics to a computable system. The dream can not be realized. We humans can prove things like Goodstein's theorem. A statement that is true in the second order PA. How will a computer prove such a thing? There is no effective, computable means, for determining if a given statement is an axiom in PA.
I don't know anything about the chess algorithms but my understanding is that they rely, essentially, on searching a vast number of possible outcomes. Can a computer beat Magnuson with the number of computations the computer can do limited to within one order of magnitude of what a human can do in the allotted time?
Thanks for the discussion. I'll contemplate what you've written and any response you care to make. I won't respond further since I'm delving into areas I know little about.
No. Not humans. One human.
> The discussion is about human intelligence in general (particularly applied to bright people) not about my own intelligence and its limitations.
OK, but if you're going to talk about human intelligence in general then you have to look at what humans do in general, and not what an extreme outlier like Curt Godel did as a singular event in human history.
> particularly applied to bright people
And how are you going to measure brightness?
> How will a computer prove such a thing?
I have no idea. (I was going to glibly say, "The same way that humans do", but one of the lessons of AI is that computers generally do not do things the same way that humans do. But that in no way stops them from doing the things that humans do.) But just because I don't know how they will do it in no way casts doubt on the near-certainty that they will do it, possibly even within my lifetime given current trends.
> I don't know anything about the chess algorithms but my understanding is that they rely, essentially, on searching a vast number of possible outcomes.
Yes, that's true. So?
> Can a computer beat Magnuson
I presume you meant Magnus Carlsen? Yes, of course. That experiment was done last year:
https://www.youtube.com/watch?v=dgH4389oTQY
> with the number of computations the computer can do limited to within one order of magnitude of what a human can do in the allotted time?
What difference does that make? But the answer is still clearly yes because the computer could simply emulate Carlsen's brain. A 10x speed advantage would surely be enough to win.
Your response here implicitly admits there’s difference in human thinking and computer “thinking”. A chess program that just searches a vast number of possibilities and chooses the best one is not thinking like a human. It’s not even close.
* > How will a computer prove such a thing? I have no idea*
If you knew about these things you’d know that it isn’t possible to have an algorithm that halts in a finite number of steps that determines whether or not a given statement is an axiom in 2nd order PA. A computer is incapable of reasoning about such things.
Earlier you wrote:
> Can a computer beat Magnuson with the number of computations the computer can do limited to within one order of magnitude of what a human can do in the allotted time?
If a computer can't emulate a person's brain then how are you going to assess whether or not the number of computations it's doing is "within one order of magnitude of what a human can do"?
> A computer is incapable of reasoning about such things.
You want to bet on that? Before you answer you'd better re-read your claim very carefully. When you realize your mistake and correct it, then my answer will be that humans aren't guaranteed to be able to determine these things in a finite number of steps either. There's a reason that there are unsolved problems in mathematics.
Yes.
> and its operation must be analyzable as a finite series of elementary instructions that are analogous to those of a Turing machine
Analyzable, sure. MWI is fine as an analytic tool in the same way e.g. virtual particles and holes are. Nothing here requires that any of these analytic tools are physically corresponded to.
Sure. But it also shouldn’t be glorified as adding anything to an old debate—every QCD calculation has this dynamic of lots of classical “computations” happening seemingly simultaneously.
The question is then how could we efficiently multiply Turing machines? One way could be by using rays of light to do the computations. Rays of light operate in parallel. Light-based computers don't need to be based on quantum mechanics, just plain old laser-optics. They multiply their performance by using multiple rays of light, if I understand it correctly.
SEE: https://thequantuminsider.com/2024/03/19/lightsolver-laser-c...
So using multiple rays of light is a way to multiply Turing Machines economically, in practice, I would think.
I assume quantum computers similarly just multiply Turing Machines -like computations, performing many computations in parallel, similarly to light-based computers. That does not mean that such computations must happen "somewhere else", than where the quantum processes occur. And that does not require multiple universes, just good old quantum mechanics, from Copenhagen.
The distinction between the total operations and the total time is important, because your energy requirements scale with the time complexity of what you try to compute, not with the total time it takes.
An optical computer, for example, has a limit on how densely it can pack parallel computation into the same space, because at some point your lenses overheat and melt from the sheer intensity of the light passing through them. It's possible QCs are subject to similar limitations, and despite the math saying they're capable of computing certain functions polynomially, that doing so requires pushing exponential amounts of energy into the same space.
I'm wondering is there a universal definition of "computing"? Saying that "Conmputing is what Turing Machines do" somehow seems circular. :-)
If I have a magic box that will instantly calculate the Nth digit of the busy beaver number of any size, that can be modeled by a Turning machine. AFAIK there is no constant time algorithm though, which is what our magic box does. So a Turing machine can’t match the performance of our magic box. But no where is it written that a Turing machine puts a an upper bound on performance!
That’s what quantum computers are. They solve certain problems faster than a classical computer can. Classical computers can solve the same problems, just more slowly.
While QM and QC theory is well-established, there has been very few experiments that confirm that quantum computing actually works as theorized. There are quantum computers that are "working", but some of them (esp. the older ones) are just the kind of "quantum computers show that 15 = 3 * 15 (with high probability)". From what I read on Scott Aaronson's blog, very few of those experiments show "quantum supremacy" (i.e. classical computing physically cannot compute the results in reasonable time). This is why the Google Willow thing is considered a breakthrough.
So basically empirical "proof" that quantum computing actually works as predicted in theory is rather recent stuff.
If the QC isn't doing any meaningful computation, if it's not actually executing an algorithm, then it's not possible to compare their respective efficiencies. Or rather it is possible, but the answer you get is meaningless. Let's make it fair. How long would it take a ~100 qubit quantum computer to simulate at the physical level a smartphone's SoC running for 1 second?
>If you think that quantum computers won't work, then either (1) all the theorists studying them for the past half century have somehow screwed up their basic maths, or (2) our understanding of quantum mechanics is wrong in ways that experiments have already ruled out.
You know this thing called science? Its goal is not to know things, it's to learn things. If we already knew everything there is to know about quantum mechanics people would have built a perfectly functioning quantum computer at the first try (or they would have known from the start it was impossible). Physicists are trying to build quantum computers partly because in doing so they learn new things about quantum mechanics, and because they want to learn if it's possible to build them. Quantum computers are themselves also an experiment about quantum mechanics.
If you read the original article, you'd see that the idea of experiments about quantum supremacy is an important issue. The whole reason they want to conduct such experiments is to prove that quantum computing actually works empirically.
The question is not whether "I think" quantum computers won't work. I don't "think" anything, I'm not an expert in the field and as such what I personally think is irrelevant. Scientifically, there aren't enough empirical experiments to conclusively prove whether they work. Whatever I "think" or you "think" are pure speculation. The chances of QC working and scalable to non-trivial number of qbits might be pretty good, but they haven't built a machine that can break RSA yet for example.
And yes of course the theorists could be working on the "wrong" theory all the time. It happened with Newtonian physics. You can't build accurate GPS systems with Newtonian physics without taking into account relativity. Similarly, we already know QM does not take gravity into account. Is it possible that quantum-computers-as-we-know-it are not possible under a gravitational field? Unlikely(?), but it's possible. You can't just take your personal speculative belief as truth and call everyone else flat earthers.
Light follows a geodesic. Atomic reactions tend to minimize energy. Rivers follow the most efficient path to the sea. Where does any of that computation "happen"? Why is it any stranger that an electron "knows how" to follow a gradient in an electric field than that a quantum computer "knows how" to perform a random circuit sampling?
First, I also think the “this favors the Everett interpretation” argument is incoherent, but for different reasons. I won’t be defending that view. But I can try to answer your question about the nature of computation and “where” that computation is taking place.
A quantum computer is essentially a random number generator, but with a non-uniform distribution that can be programmatically controlled.
Let’s start with the random part: a qubit can be either a 1 or a 0. When first initialized, when you then read it you will get either a zero or a one with 50% probability. (I am oversimplifying to the point of error! This is technically incorrect, but please excuse me for the purpose of a simplified explanation that makes sense to computer scientists rather than quantum physicists.) In the Copenhagen interpretation the wave function randomly collapsed in a way that can be measured as a 0 or as a 1 with 50% probability for either outcome. In the Everett interpretation there are two universes (really, two disjoint sets of universes): one where you see a 0, and the other where you see a 1, and your likelihood of ending up in either is 50%.
For example, with three qubits you can read a random value between 0 to 7, where each qubit provides a 0 or 1 of a classical 3-bit binary value. If you're making a D&D simulator, you can take three of these registers (9 qubits total) and read them to get three values between 0 to 7, then increment each and add together to get the simulated value of three 8-sided dice, for the attack value of some game weapon.
But so far we're assuming even and independent odds for a 0 or 1 in each qubit. A quantum gate operation lets you modify that probability distribution in interesting ways. Specifically you can take multiple qubits and entangle their state such that the eventual outcome (still random) is constrained to a non-uniform probability distribution. (The details don't matter, but it has to do with the fact that you can add wave amplitude, which is complex-valued and therefore can constructively or destructively interfere.)
So instead of reading three separate 1d8 registers and adding them together, we can use quantum gate operations to perform the addition: entangling the state of a new 4 qubit register (large enough to hold the sum of two 3 qubit registers) such that it represents the sum of two separate, randomly chosen with independent probability values between 0..7. The combined sum will be a random value between 0 and 14, but with the value 7 being most likely, 6 or 8 next most likely, etc. (You can see the probabilities here: https://anydice.com) We then add in the third 3-bit register, getting a 5-qubit result. For good measure, we then add a constant 3 value using quantum gate operations so the result will be what we expect for adding 3 dice rolls, which start counting at 1 rather than 0. Now we have a great random number generator for D&D games. It's a 5-bit register that when you read it will give you a value between 3 and 24, with exactly the probabilities you would expect of three rolls of a fair 8-sided die.
You can interpret what this means in Copenhagen vs Everett, but there isn't a way in which it makes material difference. I will say that the Everett interpretation is easier to think about: you setup the entangled operations such that there simply isn't a universe in which the register reads 31, or some value not representative of a 3d8 dice roll, and if you count the number of possible universes under the born rules and holding the rest of the multiverse constant, the counts match the 3d8 dice probability distribution. So you don't know which universe you will end up in when you finally read the register and, under the many worlds interpretation, split off into one of many possibilities. But you know it will be a good 3d8 dice roll for your D&D game.
Now imagine you have two 1,024 qubit registers (each with random probability for each bit), and you run a full set of shift-adders to multiply them together into a 2,048 qubit register. If you read the result, it'll be a random non-prime number. Why? Because it's necessarily the product of two 1,024 composites. What's interesting is that you can kinda do the reverse, as Peter Shor figured out how to do in the 90's: start with a 2,048 bit register, run the shift-adder in reverse (really, the method of continued fractions, but I'm going for an intuition pump here), then read the two 1,024 registers. What you will get is two values that when multiplied together will result in the input, the factors. If you put "60" in the input, you will maybe get the outputs (15, 4), or (5, 12), or (2, 30), or (1, 60). It's random which will pop out, but what you get WILL be a factorization of 60.
Now put your bank's SSL public key in the register, and read the factors out. The factors are the private key.
I don't think any talk of multiverses is needed to understand this. It's simply mucking around with the probability distribution of a random number generator in clever enough ways that the random number generated, whatever it is, will be A solution (perhaps one of many) to your problem. You do this by destructively interfering the register with wave functions that represent non-solutions, and keep doing this until only solutions are left as possible values. Then you read your random number register and know the result is drawn from the solution set.
Other, weaker forms of Copenhagenism scarcely even qualify as a real metaphysical interpretation of what is going on. I do think building big things in superposition does seem suggestive that there is no 'collapse upon interaction with observer' effect in metaphysical reality.
Why? The mathematics of quantum mechanics describes perfectly well what is going on in these systems, to exactly the same level of accuracy. There is no predictive difference between Copenhagen and Everett interpretations.
This is a philosophical argument, not a physical one.
The principle of parsimony, imo, favors an everettian explanation - and constructing larger contraptions with QM effects puts increasing parsimony pressure on why observers like humans are not simply getting entangled with the system they are observing when we see 'collapse.' The mathematics of QM does not describe collapse or how that occurs from wavefunction evolution or why observers are relevant.
I don’t quite agree with this characterization. You end up in both universes with 100% certainty, but there will then be two of you, one in each universe. Where the likelihood again comes in, is when one of the two yous wonders in which branch they are located, and tries to predict (retrodict?) based on information collected prior to the branching, it will be a 50/50 likelihood. Of course, if they are able to look at the outcome of the experiment, it will become clear in which branch they are located.
This concept of probability in the context of MW is known as “self-locating uncertainty”: https://www.journals.uchicago.edu/doi/10.1093/bjps/axw004
Shor’s algorithm is where the rubber meets the road for me. Synthetic benchmarks like what Google made just aren’t that useful imo.
There’s even a case to be made that all the work needed to make quantum computing reliable negates the supposed advantage and makes it no more unscalable than conventional computing. I don’t subscribe to that, but a successful Shor’s Algorithm attack on RSA (with enough bits) would certainly prove that wrong.
Most of the debate over interpretations boils down to the mind projection fallacy. For each of us one interpretation is so clearly easier to think about, and everyone else must be bonkers for thinking otherwise. In reality one makes sense to me, the other makes sense to you. That’s fine.
Right. I’m definitely a layman here but as a CS generalist this rings out as narrow-minded to me, biased towards the way we designed physically and then mathematically formalized “computation”.
Not that I have anything against multiverses but.. if I had to choose between “Turing-style computation happened, but needed parallel universes to do so” and “what happened is something counter-intuitive and insufficiently understood about the universe we inhabit” I would bet on the latter.
Question then becomes, how do you build such non-constrained machines? Also, how do you confirm that such machines—or even small scale prototypes—are not constrained by classic laws of physics?
You mean, like... transistors? ;-)
https://en.wikipedia.org/wiki/History_of_the_transistor (search for quantum)
True, but no exciting plot twists either. :(
Like the bubble analogy, new Everettian universes are local, small, and the total amount of probability density (water in this analogy) is conserved.
I'm often tempted to argue quantum computers at least clearly favor ontic interpretations (ones where quantum states are real). Because good luck computing things by subjectively having a computer instead of actually having a computer. But, as far as I know, you don't see quantum-bayesianism-ists having any qualms with quantum computers. I think because if you're already biting the bullet of interpreting diagonally polarized light as subjective, and Bell tests as subjective, then interpreting a computation as subjective isn't fundamentally different. It's just more in your face about it.
I do agree quantum computers disprove local hidden variable models. Because they can run Bell tests, and local hidden variable models can't violate the Bell inequalities.
Superdeterminism is an interpretation of quantum mechanics where they can:
https://en.wikipedia.org/wiki/Bell%27s_theorem#Superdetermin...
But, anyway, as I grasp it so far... nature already makes it possible to look like one can "take multiple paths" when one is coherent, i.e. isolated from entanglement with environment during that path, i.e. where the "which path" is not already decided via e.g. measurement. For example, the Lamb shift is the consequence of the fact that the universe really doesn't know which paths of particle creation and annihilation, if any, the force carriers between the electron and the proton took. So, it is able to take all of them. Why should it rather be our expectation rather than how nature says it can work? It seems like a mental contortion is needed - but nature really does operate based on possibility because it's the consequence of the more fundamental fact that there being no one / nothing in the entire universe, including the particle itself, that "knows" what state it's in or going to be in, during a certain span of the system's evolution.
At the moment there is such a record keeper, the influence of "possibility" diminishes.
Start by at least having a universe for each possibility so that every code path is computed. Then add a mechanism to create many more universes when a correct result is hit.
So each wrong result has 1 universe and the correct result alone has 2^300 a universes. Run this. You now end up with the correct result 99.99999% of the time.
I’m not arguing on the above take or not fwiw, it’s just that it easy to see how this could happen in many worlds. Effectively error correction just becomes a mechanism to create more universes for correct answers than incorrect answers and it all works. In fact it’s very reasonable to think of quantum error correction this way (it really is a mechanism to favour correct answers being observed and in many worlds that means it creates more correct answer universes).
Simple count has not much to do with the outcome observed, IMU each branch in a split is not equally likely. If you finely sub-divide a low-probability branch into 2^300 sub-branches, so what. Instead, you need to merge multiple high probability branches back into a single outcome that is observed "99.99999% of the time".
The result is the same in all universes. There's a kind of scatter-gather/map-reduce feel - each universe computes part of the problem, then you add up all their results to get the final one (in all universes).
The argument works for me, although I already believed the conclusion so I'm biased.
But then I actually saw some of the math (very basic Hisenberg uncertainty equations) and good comparisons to classical wave mechanics and wave interference. Everything made more sense.
As a layman with some very rudimentary understanding of the math, I would ignore ALL talk about "farming out" and "parallel universrs" and similar concepts. I think thise ideas are charged with too many interesting but fantastical elements which you probably don't find in actual quantum mechanics.
This is inherent to the problem of attempting to describe something that fundamentally does not work like the macroscopic world, using vocabulary rooted in that macroscopic world.
It would help to call the "Everettian" interpretation by the original title given by Everett: the theory of the universal wave function.
Ignore the techno-babble about the multiverse. The way I understand Everett is simply as taking the math literally and seriously to its logical conclusion.
I don't understand that part, can someone explain? There should be plenty of problems that take a long time to solve, but are trivial to verify? Like for example factoring extremely large numbers that are the product of a few very large primes? Maybe not on the order of 10^25 years, but still?
This nerd sniped a bunch of us, because it sounds like "oh we proved P!=NP", the keys to understanding are A) hanging onto the this in "this computation" (this is easier when you're familiar with the computation and it's contextual history in the field) B) remembering prime factors as a plausible application of QC.
Then faced with the contradiction of B, it's neatly resolved by "yes, but the quantum computer isn't big enough to do prime factorization yet"
As noted somewhat sideways in the blog, if someone has a computation that is A) not classically computable in a reasonable timeframe B) is computable on a miniscule quantum computer C) can be verified on a classic computer in a reasonable timeframe, a lot of researchers will be excited.
FWIW:
There were some really cool comments on the last article re: Willow.
One of them being, a reference to a apparently well-known "roadmap" of quantum scaling that apparently got written up a few years back.
Apparently the Willow result was the 2026 baseline projection.
So their message was "well...not too big a deal, we achieved 2026 at ~2025." Also said that the same roadmap would have that achieved in 15-20 years.
Just vague ideas like: it could be useful for quantum simulations or optimisation or maybe ...
If tomorrow we have a full running quantum computing what would we run on it? We are in a vacuum.
The only hope is a breakthrough in quantum algorithms. Nothing in sight, not much progress on this side.
Oh yes, Zapata Computing, the best funded company in quantum algorithms just went under this year.
It's kinda hard to make money by developing algorithms for imaginary magic computers.
There are plenty of quantum algorithms.
Willow, Our Quantum Chip
a) error-correction needs small level of errors to begin with to amplify signal - we finally got to that point, and larger correction setup deals with more errors
b) "standard" benchmark problem now 100% computes something uncomputable with classic chips (in practice) - the problem is that it's so quantum, neither it is verifiable with classic chips anymore
I'll keep this short.
- Google’s Willow quantum chip significantly outpaces current supercomputers, solving tasks in minutes that would otherwise take billions of years.
- Hypothesis: Accelerating advancements in tech and AI could lead to quantum supremacy arriving sooner than the 2030s, contrary to expert predictions.
- Legacy banking systems, being centralized, could transition faster to post-quantum-safe encryption by freezing transfers, re-checking processes, and migrating to new protocols in a controlled manner.
- Decentralized cryptocurrencies face bigger challenges:Hard forks are difficult to coordinate across a decentralized network.
- Transitioning to quantum-safe algorithms could lead to longer transaction signatures and significantly higher fees, eroding trust in the system.
- If quantum computers compromise current cryptography, tangible assets (e.g., real estate, stock indices) may retain more value compared to digital assets like crypto.
Thoughts?
> - Google’s Willow quantum chip significantly outpaces current supercomputers, solving tasks in minutes that would otherwise take billions of years.
billions of years you say? Just what kinds of "computing tasks" we talkin about here?
I genuinely want to learn and figure out what is the truth and what is the best route of action when it comes to securing a portfolio.
As Google's own team report "Google will only consider itself to have created a “true” fault-tolerant qubit, once it can do fault-tolerant two-qubit gates with an error of ~10-6". That's two logical qubits.
The general consensus is that to have a practically useful quantum computer we'd need one with about a million physical Qubits. That's not just 1,000 of these 105 qubit chips because those wouldn't be entangled, but one chip with about a million entangled physical qubits and therefore 1,000 logical qubits.
I'm all ears
> where to invest
and like that, you lost me
Did Google's experiment encounter problems when trying to run RCS on the full 105 qubits device?
Before saying that the computation invoked parallel universes, first I'd like to see that the computation couldn't be explained by the state being encoded classically by the state of the particles in the system.
Is it really?
There's only ~500,000 grains of sand in an egg timer.
I don't know anything here, but this seems like something that shouldn't be impossible.
So I'm curious. Why is this impossible?
What am I missing?
So while we can - for something as simple and regular as an eggtimer - come up with some workable approximations, the approximation would surely fall short when it comes to the detail (an analytical solution for the path of every single grain).
This is the basis for example Monte Carlo simulation, it simulates real world with random numbers it generates.
Now it's obvious to me that you would have to simulate exactly what the universe is doing down to the smallest level to get a perfect simulation.
Thanks.
Is it really impossible to get a very close approximation without simulating down to the atomic level, though?
Every approximation will by definition deviate from what really happens - I suppose that's why we talk of "working approximations", i.e. they work well enough for a given purpose. So it probably comes down to what the approximation is being used for.
There is the idea that we are all living in a simulation; if so maybe if we look closely enough at the detail all the way from the universe to atoms then we'll start to see some fuzziness (well, of course there's quantum physics....).
What is calculation anyway we may ask. Isn't it just term-rewriting?
Pi is just a description used for calculating perfectly/near-perfect spheres. A sphere is nature's building block, since every point on it's surface is the same distance from the centre.
Does it? In what sense the result is "correct"? It's not because it's perfectly regular, or unique, or predictable, or reproducible. So what's "correct" about it?
Completely out of my depth here, but maybe there is a difference between evolution of a physical system and useful computation: and maybe there's much less useful computation that can be extracted from a physical system than the entire amount of computation that would be theoretically needed to simulate it exactly. Maybe you can construct physical systems that perform vast, but measurable, amounts of computation, but you can extract only a fixed max amount of useful information from them?
And then you have this strange phenomenon: you build controlled systems that perform an enormous amount of deterministic, measurable computation, but you can't make them do any useful work...
From the same school of thought, to simulate the path of a single particle seems it should require a device comprised of more than a single particle. Therefore, if the universe is a simulation, the simulator must have more than the number of particles in the universe.
In the tautological sense.
I wonder why, byte has 8 bits and the Hamming error correction code uses 7 bits.
oh right - that's because *the scheme* requires 3-7-15-... bits [0] and 7 is the largest that fits
Same with surface error correction - it's just the largest number in a list. No need for conspiracies. And no connection to manufacturing capabilities, which determine qubits on a single chip
This claim makes little sense. There are many problems that are much easier to verify than to solve. Why isn't that approach ever used to validate these quantum computing claims?
Well, really it can't run them at all, but a more-general computer this size which could, still wouldn't be large enough.
Hossenfelder’s linked tweet addresses this head on [1]. We need four orders of magnitude more qubits before a QC can simulate anything real.
In the meantime, we’re stuck with toy problems (absent the sort of intermediate test algorithms Aaronson mentions, though the existence of such algorithms would undermine the feat’s PR value, as it would afford cheap takedowns about the QC lacking supremacy).
For example, isolate two molecules in a vacuum and predict its future state. Now make it 5, now 100, etc...
I suggested simulating the experiment of n molecules in a vacuum, another experiment might be a chaotic system like a double pendulum. Although there would need to be a high level of precision in setting up the physical parameters of the experiment.
Try "I don't understand this claim"?
(1) They're picking problems domains that are maximally close to the substrate of the computation device, so they can hit maximum problem sizes (like 10^25). For many (all?) fast-verifiable problems they can't currently handle impressively large problem sizes. In the same way that GPUs are only really good at "embarrassingly parallel" algorithms like computer graphics and linear algebra, these quantum chips are only really good at certain classes of algorithms that don't require too much coherence.
(2) A lot of potential use cases are NOT easy to validate, but are still very useful and interesting. Weather and climate prediction, for example. Quantum chemistry simulations is another. Nuclear simulations for the department of energy. Cryptography is kinda exceptional in that it provides easily verifiable results.
(0) For a quantum algorithm/simulation to be classically verifiable, it needs additional structure; something that leads to a structured, verifiable output despite the intermediate steps being intractable to simulate classically. That additional structure necessarily adds complexity beyond what can be run on current devices.
To pick an arbitrary example I'm familiar with, this paper (https://arxiv.org/abs/2104.00687) relies on the quantum computer implementing a certain cryptographic hash function. This alone makes the computation way more complex than what can be run on current hardware.
And they’re not actually solving weather problems right now, I think. That was just an example. What they are actually solving are toy mathematical challenges.
Also I doubt that a quantum algorithm is possible that provably solves the Navier-Stokes equations with known boundary and initial conditions. At least you need some discretization, and maybe you can get a quantum algorithm that provably converges to the real solution (which alone would be a breakthrough, I believe). Then you need some experimental lab setup with well controlled boundary and initial conditions that you can measure against.
In any case the validation would be at a very different standard compared to verifying prime factorization. At most you can gain confidence in the correctness of the simulation, but never absolute certainty.
For example: "Calculate whether we'll have El Niño this year"
The validation will not need to be run on a machine, but on the real world. Either we have el niño or we don't.
I laughed at this. If I understood more than literally 2 words of that, then yes - no doubt I would ask about that.
It is like we are still figuring out whether it’s better to use vacuum tubes or semiconductors or what. Google used superconducting circuits for Willow, which can be fabricated with computer-chip-style lithography etc, but needs to be kept extremely cold and the connectivity is obviously etched permanently into the circuit. Other technologies have different pros and cons.
What's the largest number it can factor using Shor's algorithm? What's the largest hash it can compute a pre-image for using Grover's algorithm?
Imagine a ball falling on the ground.
Simulating the O(10^23) atoms in each one with a classical computer would take (say) 10^23 times the amount of work of simulating a single atom. Depending on the level of detail, that could easily take, you know, many, many years...
We don't call the ball a supercomputer or a quantum computer just because it's so much more efficient than a classical computer here.
I presume that's because it can't do arbitrary computation this quickly, right?
So in what way are these quantum computers different? Can they do arbitrary computations?
But nevertheless, many of these 'beyond-classical' demonstrations feel a bit arbitrary in the way you describe, and there's good reason for this. Logical operations are still quite noisy, and the more you apply, the more output quality degrades. To get the most 'beyond-classical,' you run the thing that maps most readily to the physical layout and limitations of the hardware.
As things improve, we'll see more and more demonstrations of actually useful computations. Google and others have already performed lots of quantum simulations. In the long run, you will use quantum error correction, which is the other big announcement this week.
This might have been part of the history of classical computers as well, except that it turns out to be pretty easy to do classical operations with very high fidelity.
Hopefully large-scale, verifiable demonstrations become viable in the near future. But current they're just too hard to implement.
There's some probablistic programs that we run that not only don't need determinism, but are actively harmed by it.
For example deep learning training would probably work fine if there was a 1% destructive noise, as long as there were a massive increase in compute.
A ball falling on the ground can be converted into a math problem. To get the conversion exactly right you will need to write down the exact state of the ball. But you will invariably incur small inaccuracies while doing this. For example, maybe the mass you write down is off by 1 part in a trillion. The math problem is the ground truth, so any conversion inaccuracies are now errors in the ball. In practice these inaccuracies will prevent even the original ball from solving the written down problem much better than you could with a computer.
In the case of random circuit sampling, the written down problem is a tensor network [1] (that happens to also be a shallow quantum circuit). Fundamentally, a tensor network just specifies a bunch of matrix multiplications to do. It's not even that big of a problem: only a few kilobytes of information (whereas the exact state of a ball would be gargantuan). All you have to do is perform the specified multiplications, interpret the result as a probability distribution, and sample from it. The obstacle is that these multiplications create intermediate values that are really really large. The quantum computer bypasses this obstacle by executing the tensor network as a circuit.
I don’t recall enough of the conversation (circa 2019) to remember anything about the properties of the problems it helps solve, so I can’t help generalize. Sorry.
Essentially, they argue that unless strong algorithmic breakthrough happens (e.g. having cubic speedup, instead of quadratic), the only practical problem for which quantum computer will be useful, are those where you get exponential speed up:simulation of quantum systems (and breaking of RSA encyrption if you count that). Even those are challenged by other (approximate) simulation by Classical Deep Learning. There will be some quantum models for which quantum supremacy will be useful and Deep Learning wont. The question what classes of systems.
One obvious problem is cooling. We can't cool million qubits in a single fridge, so we will need to split them between fridges and communicate. Also, the wiring is really complicated already and hard to scale (one reason IBM has heavy hex is to have more space).
Another problem is connectivity. For transmon qubits connectivity is fixed. Applying gate to two far qubits requires a lot of swaps, which is expensive. This is less of a problem for ions or cold atoms because they can couple any two qubits; but they likely wouldn't be able to for large amount of qubits.
Another thing is classical control, because the classical data needs to be processed at high speed. Some companies develop specialized hardware for that.
None of these is necessarily fundamental, but these problems need to be solved, in addition to usual scaling (it is hard to manufacture these devices and it becomes harder with each qubit).
I'm sure there are lots of complicated problems ahead, but i don't think we are waiting for someone to discover "new" physics.
This is not totally fair; it is possible given certain independence assumptions. But they are likely not physically realizable.
It is almost certain that even within our understanding of quantum systems it is simply not possible to have a quantum computer (much less create one). The assumptions necessary to produce a completely uncoupled system are likely invalid; we have yet to produce a compelling experiment to indicate otherwise. [1]
> Goal 3: Create distance-5 surface codes on NISQ circuits that require a little over 100 qubits.
> The argument presented in the next section asserts that attempts to reach Goals 1-3 will fail.
Goal 3 is exactly what Google has recently achieved with Willow. Actually, they did even better, reaching a distance-7 surface code (with a little over 100 qubits). Q.E.D.
To be clear, I do think your article is interesting and was valid at the time, but it goes to show how fast the field is advancing.
Can anybody explain me why it is hard to find a problem that can be solved only by a basic quantum computer within a short timespan and can be easily verified by a normal computer? I thought there are so many algo's out there for which one direction is fast and the reverse takes ages.
(spooky action at a distance)
The problem with this line of reasoning is that, even though a quantum system might have many possible states, we only observe a single one of those states at the time of measurement. If you could somehow prepare a quantum system such that it encoded the N equally-likely solutions to your classical problem, you would still need to rerun that experiment (on average) N times to get the correct answer.
Broadly speaking, quantum computing exploits the fact that states are entangled (and therefore correlated). By tweaking the circuit, you can make it so that incorrect solutions interfere destructively while the correct solution interferes constructively, making it more likely that you will measure the correct answer. (Of course this is all probabilistic, hence the need for quantum error correction.) But developing quantum algorithms is easier said than done, and there's no reason to think a priori that all classical problems can be recast in this manner.
I think that all classical problems can be cast as quantum computations because quantum computation is just computation - I believe that one can implement a turning machine using quantum gates, so arbitrary computation is possible with quantum gates.
The superpolynomial speedups are the thing.. I wonder if these will be limited to a class of computations that have no physical realization - just pure maths.
They never talk about what this computer is actually doing.
It seems the whole quantum computer thing only made people like him excited because it's a different kind of computer, not because there is any strong evidence that it will be practically useful.
It reminds me of nuclear fusion: Sounds cool, but it is highly doubtful whether it could ever compete economically with nuclear fission.
This is an extremely limited system, different in capability but in the grand scheme of things conceptually similar to implementing the quantum equivalent of a single binary digit.
No nuance, just yes or no.
not for the next 5 years for sure.
I got that ‘Google has been talking about Willow for ages, this isn’t new’ blah blah blah. The problem is the public only started talking about it yesterday.
This is progress towards quantum computing but no where near progress towards a real practical quantum computer that could break Bitcoin's algorithms. If progress continues it could be an issue in the future, check back in next time Google publishes a paper.
Also Willow can’t even factor 15=5x3 you are good for a very long time.
QC companies are selling quantum AI and quantum finance and other hand wavy stuff. Yet, I don't see any algorithms that has a proven advantage in these domains over classical ones running on clusters of GPUs.
I only wonder what it means for cryptography.
The letters "crypt" don't appear in the text.
but it already passed "1920s" with "only radios" - analog, non-digital devices
stability tech is almost here (check quanta magazine), next is the scaling up
If you want to make a classical computing analogy, it's like we're struggling to make transistors with more than a single 9 of reliability, and obviously you can't do complex computation with a circuit where every step gives garbage 1-in-10 times.
Except it's not's obvious. 90% reliability could probably be made to work with silicon transistors with bog standard error correcting logic at the hardware level. Quantum error is a little bit more troublesome to work with, but there are also no known theoretical reasons error correction wouldn't work at existing error rates. We just need better algorithms, which might very well exist.
Or, the next generation of chips would offer more 9's reliability, and even with existing error correction just a few more sigma in reliability would put us over the tipping point of being able to make reliable large-scale systems.
universal computation was not a thing yet
So if you want to make analogies between quantum and classical computers, QCs aren't even at the level of early 19th century technology. They're still trying to figure out what's even necessary to build devices of a practical size.
Quantum computing, especially right now, is simply focused on getting reliable input/output idempotency. It will be a really long time before it has insane and crazy math skills, and when it does, traditional CPU architectures will probably outperform it.
TL:DR - if the Texas Instrument calculator didn't put you out of a job, neither will quantum computers.
If they can find some synergies between the two, that could be THE major development. Make better AI by using Quantum Computers, and make better Quantum Computers by applying AI.
AI – being practically applied in many areas where it doesn't seem to be working well
I really do hope these aren't our best lanes of progress
https://www.seattletimes.com/business/technology/google-intr...
Accurate weather forecasts save money. Doing them on super-computers costs a lot of money. But with Google's AI solution that gets cheaper.
As for QC I'm not saying it does much useful things yet, but companies are starting to use it and there is progress going on.
What in your view are better lanes of progress than QC and AI?
It's very true that there are many areas of ML where considerable progress has been made and is delivering value
Are companies using QC? It's not like it can do much currently, as I understand it
We're making a lot of progress all over the engineering side of computing. A lot of it is incremental, but a faster or more energy efficient processor is very practically useful in a way that QC isn't yet. We might well get optical interconnects on cpu dies before we get anything tangible from QC
The Google benchmark with random circuit sampling is fascinating from a theoretical perspective, but it’s hard to see how this translates into solving problems that matter outside the quantum research community.
The lack of practical applications is a glaring issue. Sure, it's cool that Willow can outperform Frontier on this obscure task, but where’s the real-world impact?
Cryptography, optimization, drug discovery—these are the kinds of problems quantum computing needs to beat if it’s going to justify the investment. Until that happens, it feels like we’re stuck in a cycle of overpromising and underdelivering, with flashy press releases but no tangible results.
And let’s talk about scalability. Even if Willow hits the error-correction frontier, the number of physical qubits needed to build a truly practical quantum computer seems astronomical. Millions of qubits just to factor a number?
It’s hard to see how this scales in a way that makes economic or scientific sense. Right now, it feels like quantum computing is a field for researchers who are okay with not seeing practical outcomes in their lifetimes.
Maybe I’m too cynical, but this smells like another example of tech marketing getting ahead of the science. Maybe we can admit that we’re still decades away from quantum computing having any real-world relevance?
And the investment required to produce such a machine is undoubtedly in the XX billions.
Not necessarily. There's two interpretations to the question: 1. QC would be very efficient and mine efficiently. 2. QC would break SHA and would be able to reverse the hashing function at O(1).
In scenario 1. The difficulty would increase. The mining rate globally always stays the same. And the voting power would be distributed amongst the holders of the new compute, this has happened before with ASICs. Usually there's some graduality to it, and the capital is distributed so that there is never a 51% monopoly. It's especially relevant how big the jump is, if the new computer is stronger than all of the existing miners combined, then they get 100% theoretically (although with malice). In that case there would probably be a fork or as you put it, BTC would collapse. However, if you have that power, holding BTC is probably not that important anyway. The actual compute is worth more.
On scenario 2. Yes BTC would crash, but then again the actual compute power would be more impactful. BTC would crash but so would encryption, and planes and the world.
Sad to see Bitcoin advocates use this dismissive argument.
Centralized systems will update their software as the threat increases. Meanwhile, there are no serious proposals for a quantum-resistance Bitcoin. Some are estimating the update will require a hard fork and take 1 year to update.
https://www.deloitte.com/nl/en/services/risk-advisory/perspe...
Bitcoin private keys will become vulnerable with knowledge of the public keys.
There is a way to mitigate this - because a bitcoin address is a hash of a public key, a bitcoin protocol change can occur whereas the public key becomes a secret and the signature is a zero-knowledge-proof (ZKP) of the prescribed transformation of secret -> address. These signatures are going to be big however, and so the fees will be very high.
If they all mostly agree, that's your answer.
And it's almost always what you assumed anyways from the news, because this stuff isn't rocket science.
So for all practical purposes, yes actually you usually do know, whenever a stock movement is large enough that it's clearly outside the normal noise of day trading.
I mean, can you prove the reason with 100% mathematical certainty? No. But can you be 99% sure? Of course.
I definitely read this first pass and thought 'damn the CEO is hitting its own quantum supercomputer with bug reports'. that's cold. It just came out.
The post reiterates some facts from the original statement, which are pretty vague for most, I believe. The only useful clarification is that simulation results are indeed unverifiable, lol (as some might have suspected, but still nice to have a definitive confirmation from somebody who is supposedly an expert on this).
Then it addresses the cringeworthy "Everettian multiverse" statement discussion. Granted, it indeed was one of the most discussed things on the previous thread, but I have honestly assumed that it's so obviously moot that one can simply ignore it. Everyone knows that at least one of top-3 threads on HN comments must be either a lame joke or some sort of bikeshedding argument.
And that's pretty much it. "This blogger said this usual generic words, that reporter asked for an interview, but I declined, also, kudos to Google team for amazing work, it's unclear if it's any good, but it surely isn't bad!" Uh, ok, thanks for the clarification, man.
I get it that this post was written in a hurry, but given all that "fish-handing" stuff and all these commenters in this very thread complaining about how they don't know the difference between "trapped-ion or neutral-atom" qubits (as if this distinction was the very essence of the post, which author paid much more attention to than to his responses to NYT journalists) it just doesn't deliver.
...So, what did I expect? Well, I didn't expect anything, but let's state the obvious. Google's benchmark was to produce some very specific (and unverifiable) random distribution (which, BTW, he kinda says, but waaay less clearly than it could have been said). Obviously, nobody cares about that. Everyone cares about when they will be able to run Shor's algorithm on Google's Chip, and factor primes and deprecate RSA into oblivion. Obviously. Some may wonder why it's not possible to do it on that Willow thing, others may suspect that it may have something to do with the fact they need a ton of "physical" qubits to emulate logical qubits because of error-correction. Also, it is widely advertised, that the very thing that is special about Willow is vastly better (and somehow "more promising to scale") error-correction. So, what people really want from a generous and skillful fisherman is obviously some critical, appropriately-speculative, ELI5-style analysis of the updated state of the art. What does Willow have, what does it need to become practical, what are some realistic projections on when we can get there. Where is all of that? Where is the fucking fish?!
For 20 years I’ve been trying to teach the world how to fish in Hilbert space, but (sigh) I suppose I’ll just hand out some more fish.
...which ancient miracles are you possibly alluding to here?