Staggering toward quantum fault-tolerance
Happy Hanukkah! I’m returning to Austin from a Bay Area trip that included the annual Q2B (Quantum 2 Business) conference. This year, for the first time, I opened the conference, with a talk on “The Future of Quantum Supremacy Experiments,” rather than closing it with my usual ask-me-anything session.
The biggest talk at Q2B this year was yesterday’s announcement, by a Harvard/MIT/QuEra team led by Misha Lukin and Vlad Vuletic, to have demonstrated “useful” quantum error-correction, for some definition of “useful,” in neutral atoms (see here for the Nature paper). To drill down a bit into what they did:
- They ran experiments with up to 280 physical qubits, which simulated up to 48 logical qubits.
- They demonstrated surface codes of varying sizes as well as color codes.
- They performed over 200 two-qubit transversal gates on their encoded logical qubits.
- They did a couple demonstrations, including the creation and verification of an encoded GHZ state and (more impressively) an encoded IQP circuit, whose outputs were validated using the Linear Cross-Entropy Benchmark (LXEB).
- Crucially, they showed that in their system, the use of logically encoded qubits produced a modest “net gain” in success probability compared to not using encoding, consistent with theoretical expectations (though see below for the caveats). With a 48-qubit encoded IQP circuit with a few hundred gates, for example, they achieved an LXEB score of 1.1, compared to a record of ~1.01 for unencoded physical qubits.
- At least with their GHZ demonstration and with a particular decoding strategy (about which more later), they showed that their success probability improves with increasing code size.
Here are what I currently understand to be the limitations of the work:
- They didn’t directly demonstrate applying a universal set of 2- or 3-qubit gates to their logical qubits. This is because they were limited to transversal gates, and the Eastin-Knill Theorem shows that transversal gates can’t be universal. On the other hand, they were able to simulate up to 48 CCZ gates, which do yield universality, by using magic initial states.
- They didn’t demonstrate the “full error-correction cycle” on encoded qubits, where you’d first correct errors and then proceed to apply more logical gates to the corrected qubits. For now it’s basically just: prepare encoded qubits, then apply transversal gates, then measure, and use the encoding to deal with any errors.
- With their GHZ demonstration, they needed to use what they call “correlated decoding,” where the code blocks are decoded in conjunction with each other rather than separately, in order to get good results.
- With their IQP demonstration, they needed to postselect on the event that no errors occurred (!!), which happened about 0.1% of the time with their largest circuits. This just further underscores that they haven’t yet demonstrated a full error-correction cycle.
- They don’t claim to have demonstrated quantum supremacy with their logical qubits—i.e., nothing that’s too hard to simulate using a classical computer. (On the other hand, if they can really do 48-qubit encoded IQP circuits with hundreds of gates, then a convincing demonstration of encoded quantum supremacy seems like it should follow in short order.)
As always, experts are strongly urged to correct anything I got wrong.
I should mention that this might not be the first experiment to get a net gain from the use of a quantum error-correcting code: Google might or might not have gotten one in an experiment that they reported in a Nature paper from February of this year (for discussion, see a comment by Robin). In any case, though, the Google experiment just encoded the qubits and measured them, rather than applying hundreds of logical gates to the encoded qubits. Quantinuum also previously reported an experiment that at any rate got very close to net gain (again see the comments for discussion).
Assuming the result stands, I think it’s plausibly the top experimental quantum computing advance of 2023 (coming in just under the deadline!). We clearly still have a long way to go until “actually useful” fault-tolerant QC, which might require thousands of logical qubits and millions of logical gates. But this is already beyond what I expected to be done this year, and (to use the AI doomers’ lingo) it “moves my timelines forward” for quantum fault-tolerance. It should now be possible, among other milestones, to perform the first demonstrations of Shor’s factoring algorithm with logically encoded qubits (though still to factor tiny numbers, of course). I’m slightly curious to see how Gil Kalai and the other quantum computing skeptics wiggle their way out now, though I’m absolutely certain they’ll find a way! Anyway, huge congratulations to the Harvard/MIT/QuEra team for their achievement.
In other QC news, IBM got a lot of press for announcing a 1000-qubit superconducting chip a few days ago, although I don’t yet know what two-qubit gate fidelities they’re able to achieve. Anyone with more details is encouraged to chime in.
Yes, I’m well-aware that 60 Minutes recently ran a segment on quantum computing, featuring the often-in-error-but-never-in-doubt Michio Kaku. I wasn’t planning to watch it unless events force me to.
Do any of you have strong opinions on whether, once my current contract with OpenAI is over, I should focus my research efforts more on quantum computing or on AI safety?
On the one hand: I’m now completely convinced that AI will transform civilization and daily life in a much deeper way and on a shorter timescale than QC will — and that’s assuming full fault-tolerant QCs eventually get built, which I’m actually somewhat optimistic about (a bit more than I was last week!). I’d like to contribute if I can to helping the transition to an AI-centric world go well for humanity.
On the other hand: in quantum computing, I feel like I’ve somehow been able to correct the factual misconceptions of 99.99999% of people, and this is a central source of self-confidence about the value I can contribute to the world. In AI, by contrast, I feel like at least a thousand times more people understand everything I do, and this causes serious self-doubt about the value and uniqueness of whatever I can contribute.
Update (Dec. 8): A different talk on the Harvard/MIT/QuEra work—not the one I missed at Q2B—is now on YouTube.
Follow
Comment #1 December 7th, 2023 at 2:57 pm
It is admirable to try and evaluate what you work on based on what usefulness or good it does for the world. Keep trying to do that! But another thing to keep in mind is we have very little hope of success of actually figuring out the full ramifications or future consequences of what we do/don’t work on. So no need to stress too much about it. Let humility lead the way into chilling out and know that the mere intention you have to orient your work in this way is itself 99% of it.
I remember when my twins were about to be born reading an article in the New York times to the effect that what you do after they are born is very poorly correlated on life outcomes for the kids. In other words, parents actions after the preliminary action of contributing DNA and a base socioeconomic status had very little to do with outcomes later in life. For some this was seen as a revelation that they could just chill and love their kids while others took it to be an existentially devastating revelation since they couldn’t *do* anything. Maybe there is some similarity here to your question.
For me, I’d say concentrate on whatever you find the most intellectually stimulating and/or whatever you think you might be able to make the most interesting progress. You asked for advice so that is my worthless two cents.
Comment #2 December 7th, 2023 at 3:49 pm
What about working on getting AI to do theoretical computer science research?
Comment #3 December 7th, 2023 at 3:58 pm
Amir #2: That seems hard to separate from just making AI generally more capable—at math, reasoning, planning, the works—which of course is one of the central things that hundreds of engineers at OpenAI, Google, and Anthropic are spending billions of dollars to try to do. It’s very far from obvious what edge I’d have compared to them.
Still, yes, I’ll continue periodically asking GPT theoretical computer science questions and seeing how well it does!
Comment #4 December 7th, 2023 at 4:00 pm
The 60 Minutes story was pretty bad. A quantum computer would solve a maze by trying all solutions simultaneously, quantum computers can solve impossible problems, that kind of stuff.
Here’s an idea to help you decide between QC and AI. Hold an AMA that is strictly dedicated to QC / AI (AMAAQCOAI), answer the questions, and then think about which questions you preferred answering. That will at least tell you where your heart lies.
Since it is my idea, I will take the liberty of asking the first question. What is the latest that is known about the relationship between BQP and NP? Especially, what sorts of problems are thought to possibly be in BQP but not NP?
Comment #5 December 7th, 2023 at 4:11 pm
How would you compare this milestone with Google’s February milestone announced at https://www.nature.com/articles/s41586-022-05434-1? My understanding is that Google only demonstrated the surface code for single logical qubits, and they used significantly fewer physical qubits (49) and so reached a smaller code distance (Google’s d=5 vs. QuEra’s d = 7), but they also demonstrated improved logical qubit performance (in their case, as measured by coherence time) with scaling. I believe that Google only simulated logical-qubit gate operations but did not demonstrate any experimentally, correct? How big of a marginal advance would you say that this new milestone represents compared to Google’s February announcement?
Comment #6 December 7th, 2023 at 4:16 pm
I am no expert, but you can and do clearly contribute an outsized amount to TCS, including some rather seminal and unique ideas and insights. What kind of a contribution to AI progress/safety research have you managed so far, expect to make in the near future, and how unique is it? On the surface, it seems like the main thrust of the AI development these days is in the hands of the ML practitioners, not CS theorists. If you keep working on the AI-related topics, in what area would your contributions provide the most impact? How would this impact compare with what you would counterfactually contribute to QC?
Comment #7 December 7th, 2023 at 4:31 pm
Nick Drozd #4: The relationship between BQP and NP is as open as it was when the question was raised 30 years ago, and I’d say that the last major advance on the question was Raz and Tal’s oracle separation between BQP and PH in 2018, which in particular shows that relative to some oracles (based on my Forrelation problem), P=NP≠BQP. (Though see also the followup work by me, Ingram, and Kretschmer.)
I’d say that the circumstantial case that NP⊄BQP remains nearly as strong as the circumstantial case that P≠NP (not just the oracle separation, but the failure of 30 years of quantum algorithms research to get us beyond Grover’s algorithm for problems like CircuitSAT).
For a problem in BQP but not NP: if you’re satisfied with an oracle problem I can give you Forrelation and the like (which isn’t even in PH by Raz-Tal); if you’re satisfied with a promise problem then I can presumably give you simulation of quantum systems (which is PromiseBQP-complete). If you insist on a conventional language in BQP but not NP, then I’d say we still don’t have a good candidate and I’m on the fence about whether one even exists.
Comment #8 December 7th, 2023 at 4:41 pm
Ted #5: Good question, thanks! Just updated the post to (briefly) answer it.
Comment #9 December 7th, 2023 at 4:48 pm
Congratulations to all of the experimentalists! I saw a slide suggesting that 100 logical qubits with six to eight 9’s of fidelity may be foreseeable in a couple of years – that has *got* to cause some salivating, if not at least some genuine excitement.
I’m still confused about and like to think about obfuscating circuits and tests for peakedness, though. In particular, in your presentation you ask:
“Are there poly-size quantum circuits that implement the identity, but take exponentially many rewrites to simplify to the identity (or to any classical circuit)?”
But, doesn’t this follow necessarily from the QMA-completeness of identity check (and the reasonable assumption that QMA is not in NP?) If you have a polynomial-size circuit that simplifies to the identity then generically wouldn’t it necessarily take a superpolynomial number of classical rewrites to prove it as such (otherwise, your NP certificate could merely be the poly-size list of rewrites?)
Even simpler, wouldn’t it necessarily take a superpolynomial (exponential) number of implications to prove some generic tautological statement? (Otherwise, wouldn’t NP=coNP?)
Comment #10 December 7th, 2023 at 5:03 pm
There were assertions of logical qubits “with gains” also from the Yale group. In 2022 https://arxiv.org/abs/2211.09116 , and earlier in 2016 https://arxiv.org/abs/1602.04768 .
Comment #11 December 7th, 2023 at 5:23 pm
AWS also just announced a logical qubit using cat qubits, we look forward to reading the paper.
And if you consider coming back in quantum, and want to work on such an hardware-efficient, noise-biased, approach to FTQC using superconducting cat qubits, you’re welcomed at Alice&Bob, (see architecture: https://arxiv.org/pdf/2302.06639.pdf with improved version further reducing overhead coming up in January).
Comment #12 December 7th, 2023 at 5:31 pm
Google, in their February Nature paper, was pretty clear that (1) they didn’t achieve break-even, and (2) they weren’t operating below threshold, even though d=5 outperformed d=3 slightly (nontrivial analysis here!). I think the general consensus is that they didn’t get “advantage” from QEC.
Quantinuum’s 2-logical-qubit experiment got very close IIRC, but their physical gate error rates were (ironically) too good to claim break-even.
So this might be the first “advantage from QEC” milestone, except AFAIK they got advantage from QED (detection), not correction.
Comment #13 December 7th, 2023 at 6:10 pm
Have you thought about getting into quantum computer safety? 🙂
It might be interesting to work with cryptographers (not sure about your background there) on understanding the ways that quantum computing may or may not affect cryptography. Right now our asymmetric algorithms are deeply at risk from any reasonably powerful quantum computer. There are new algorithms that aren’t susceptible to *known* quantum algorithms, but of course there may be exciting new ones. Quantum-safe cryptography could be an interesting field for you.
Comment #14 December 7th, 2023 at 6:56 pm
Robin #12: Thanks!! Edited the post accordingly.
Comment #15 December 7th, 2023 at 7:03 pm
Tim McCormack #13: Not only am I familiar with post-quantum cryptography, I contributed to it 22 years ago by proving the quantum lower bound for finding collisions. To my mind, working on PQC would just be continuous with returning to quantum computing research, or to “normal” theoretical computer science more broadly (as opposed to AI safety). It’s conceivable, but if it would require mastering lattice-based cryptography (or worse, isogeny-based cryptography), I personally know several dozen people who have a gigantic leg up on me!
Comment #16 December 7th, 2023 at 7:41 pm
Gil #10: The cat code demonstrations are not universally viewed as “true quantum error correction”. (My feeling is that a majority of QEC researchers have that view, but I’m guessing here). There’s tremendous diversity of belief, and of ascribing meanings to words, within the community, but IMO a loophole-free demonstration of QEC requires (1) protecting against a full noncommuting set of errors and (2) quantifying success by comparing error-per-gate, rather than wall-clock time. So, e.g., repetition codes don’t count because they only protect against one kind of error.
Cat codes protect specifically against one kind of error. So they *can’t* achieve arbitrarily low error rates by themselves — you need to concatenate with a “real” QEC. The Schoelkopf papers you linked use cat codes and wall clock time, so IMO the “first real QEC beyond breakeven” trophy remains unclaimed. (Maybe the Lukin group has a claim now, but IIRC they didn’t do repeated syndrome extraction).
Comment #17 December 7th, 2023 at 8:45 pm
Scott, I think your work will benefit humanity more if you stick with quantum computing. Also relevant: Which way will you have more fun?
Comment #18 December 7th, 2023 at 9:08 pm
Depending on which variant of the Church-Turing thesis holds, your quantum computing work can only shed more light on the limitations of hypothetical future artificial superintelligence.
Comment #19 December 7th, 2023 at 9:47 pm
Robin#12 — IIRC the people in Quantinuum marginally improved the fidelities of the encoded qubits above the physical ones, but can’t find the reference now
Scott — In my opinion AI is “messy” and would be sort-of-like doing biology rather than computer science or physics. I find it interesting but not exciting. But that’s me! The decision is yours and you should go towards what is most exciting for you!
On the other hand, if you really find both exciting, and hence you would like an external motivation, consider this. You’ve worked in QC a fairly long time, how likely it is that you’ll find a breakthrough? (the answer can go either way: you’re experienced, so you are likely to be able to move quickly in the field, make connections among results and find new ones — or you’ve already found everything that you could have found in that haystack). On the other hand, you are a relatively newcomer in the very-crowed AI field, how likely it is that you’ll find a breakthrough? (again the answer can go either way, with basically the reverse of the previous argument).
If you are still undecided, why not merge the two interests together? There are many people making bold claims about quantum computing revolutionizing machine learning and AI, but very substantiated research (couple of exceptions: https://discover.lanl.gov/news/0705-quantum-machine-learning/ ) — Perhaps this is the field for you that:
a) you could enjoy and move between these two interests
b) doesn’t have enough (serious) researchers who understand both fields
c) very little exploration has happened and there might be juicy low hanging fruits waiting to be picked
In any case, best of luck from someone who made a similar side switch in his career!
Comment #20 December 7th, 2023 at 10:16 pm
Scott, for whatever my advice is worth (what you paid for it), the answer is completely clear: Quantum Computing (only in regards to impact, not general personal feelings). There, you’re a distinguished academic in a real field, making contributions which are solid knowledge. By contrast, “AI safety” is a mess even at the most charitable, and it’s not clear how much if anything is at a scientific level of more than trying to find the right incantations and materials to protect against summoned demons (how much deviation is acceptable in drawing a pentagram? is chalk required or will pencil be OK? does it matter if you use common table salt or pink gourmet salt?). In a way, it’s the “AI doomer” model calculation writ small. That is, potentially redefining the field of AI safety might have a much greater impact on the world than more incremental advances in Quantum Computing. But the probability of doing such big contributions to AI is much less than making (relatively) smaller contributions to QC. The flaw in much “Effective Altruism” type calculation is in those probabilities.
Also, do take into account that AI safety (xrisk) as a field is full of lunatics and Useful Idiots, and a large part of it is funded just as a smokescreen for rapacious capitalists. There’s some hype-mongering in QC as of course you know, but in AI it’s just orders of magnitude larger. That may not be a deal-breaker, but it’s a problem if you ever do something which is contrary to the money behind it.
Comment #21 December 7th, 2023 at 11:54 pm
After your great contributions to QC and a try to do something in AI, I think it is time for you to finally turn to physics 😉 !.
Comment #22 December 7th, 2023 at 11:56 pm
Such a nice summary for this “hot” paper published 2 days ago. In my opinion, the fidelity of the two-qubit gate on the IBMQ system is still so bad (some CR error rates for their 128-qubit system are even 1.0) so I am kinda worried about this new system fidelity.
About your question whether to stay in the AI or focus your research quantum? I think you are a great educator and an inspiration for the quantum community, so it would be great to see you come back and stay focused on the field. There are many interesting challenges and problems that I believe you can make an impact on. I would love to see you involved more in the quantum complexity, and come up with fantastic post-NISQ algorithms or trainability of variational schemes. However, it is up to you and your motivation and I believe you gonna do a great job in both field.
Comment #23 December 8th, 2023 at 1:04 am
lame
It’s been like 8/9 years since I first posted on this blog that scalable Quantum Computing is unlikely to be possible, reason being that we live in an Anthropic Universe which only just allows our existence after a few billions of years “by accident”
Any idea that PURE Quantum Mechanics really exists is for the fairies and Disney.
Evolution on this planet has probably done the best it can with “quantum effects”, after billions of years experimenting, with Photosynthesis sped up a little and European Robins having a better magnetic compass (good luck when the poles flip) and maybe other stuff.
Pure QM existing would be ridiculous anyway – why not a Quantum Computer simulating another QC then? Ad infinitum. Where is the collapse in such a ridiculous construction of multiple levels of Quantum Computers simulating another Quantum Computer?
Proof via ad absurdum or whatever the math people call it
Comment #24 December 8th, 2023 at 3:38 am
I disagree that “correlated decoding” is a limitation. When you perform a transversal gate between two logical qubits, you are copying over any errors that are not yet corrected. There will always be some errors that are not yet corrected, due to decoding taking time and due to measurement errors delaying when you learn about data errors.
Having your decoder account for error-spreading is making good use of the information you have available. That’s not a limitation; that’s competence. Ideally they’d be using even more correlation information! For example, Y errors introduce correlations between the X and Z decoding problems.
The main caveat on these results, from a quantum error correction perspective, is that all the results are single-round results. Single round experiments are a lot easier than multi-round experiments. There’s two reasons for this: they require fewer experimental capabilities (e.g. don’t need to continuously reload atoms) and they have higher thresholds because the decoding problems are 2D instead of 3D (2d space + 1d time). The difficulty of multi-round experiment is apparent if you look at the history of QEC experiments. Check out Table IV near the end of https://arxiv.org/abs/2207.06431 . Multi-round experiments (of things other than repetition codes) only started happening in 2019.
Comment #25 December 8th, 2023 at 5:02 am
John Preskill #17:
“Which way will you have more fun?”
this!
Comment #26 December 8th, 2023 at 5:46 am
Scott: “Do any of you have strong opinions on whether … I should focus my research efforts more on quantum computing or on AI safety?”
I don’t have an opinion on where you should focus your research efforts overall. But I would be interested to see you rigorously study Vanessa Kosoy’s stuff (Infra-Bayesianism, etc), at least to the point where you had an independent, well-founded opinion of its significance, because it is the most formal approach to AI safety around.
Comment #27 December 8th, 2023 at 6:10 am
What probability would you give for bqp=p?
Comment #28 December 8th, 2023 at 7:03 am
Johnny D #27: 10%?
Importantly, though, I’d give a lower probability (4%?) for PromiseP=PromiseBQP, and a lower probability still for all quantum sampling problems to be classically easy (which, if the simulation is exact, would imply the collapse of the polynomial hierarchy). In other words, even if P=BQP I think it’s likely that there’s “quantum supremacy” for tasks other than deciding languages.
Comment #29 December 8th, 2023 at 7:17 am
Craig Gidney #24: Thanks! I had thought that the reason why correlated decoding belonged in the “limitations” column was that the computational complexity of doing it might scale exponentially with the number of code blocks — am I wrong about that?
Comment #30 December 8th, 2023 at 7:19 am
I have a somewhat better understanding of research in QC than in AI, but I am an outsider in both, so what I am about to say is somewhat speculative. My personal sense is that in comparison with QC, AI (at the level and in the domain that you are working) is more intellectually stimulating at the moment. The precise formulation (let alone solution) of some of the most fundamental questions appears to be still in its infancy and given the number of adjacent low-lying fruits (picking which is way more lucrative) these fundamental questions seem to attract the sustained attention of a relatively small number of theoretical researchers operatnig at the highest levels of depth and rigor. Also, I think it is healthy and rejuvenating to change the field of focus after decades of sustained involvement.
Comment #31 December 8th, 2023 at 9:31 am
I can only echo what Seth said earlier. In international economics we talk about Comparative Advantage. You’re a far better AI Safety person than most and a (far) better QC than most. But one can train any unemployed Philosophy PhD to be an adequate AI Safety Expert(tm). You are uniquely gifted in conceptualizing, theorizing, and also explaining QC in a way that only a tiny handful in the world can.
On the other hand, if Google hands you a sack of money to bless their AI, then do what you need to for your family. Life’s full of tradeoffs.
Comment #32 December 8th, 2023 at 9:34 am
Del #19: Quantinuum (arXiv:2208.01863) appears to have gotten *really* close to meaningful breakeven, but not quite there. TL;DR is that their logical SPAM operations were much better than physical (0.05% logical failure vs 0.3% physical failure), and that allowed them to run a short circuit with less overall error (0.4% logical vs 1% physical), but if you isolate the critical CNOT gate, it looks the logical was a little worse (0.35% logical vs 0.25% physical).
I’ll quote that paper’s summary paragraph because it’s almost unimprovably clear and descriptive: “These results do not suggest our system is capable of executing arbitrary algorithms at the logical level with higher fidelity than algorithms executed at the physical level, or that we have achieved the so-called break-even point. Nevertheless, these measurements conclusively show that the sequence of state preparation-CNOT-measure operations is done with higher fidelity at the logical level than at the physical level, marking an important milestone in the march toward the break-even point. However, we note that the inclusion of QEC cycles along with more careful measurements will be crucial components in a “fair” comparison between the performance of physical and logical qubits.”
Scott #29: *Optimal* decoding of N syndrome bits scales horribly with N — it’s generally NP-complete. Therefore, scalable architectures use decoders that are suboptimal by an O(1) factor but scale polynomially (linearly is nice) with N. Once you restrict to low-polynomial-complexity decoders, the extra expense of jointly decoding multiple code blocks (correlated decoding) is moderate, and constitute a good tradeoff in situations like Craig describes.
Comment #33 December 8th, 2023 at 9:36 am
In my opinion as a lay person, it is good for the world that you continue to work on AI safety.
This is because you are a thoughtful person who cares about the world deeply. Your judgement about this new world with AI and safety issues are valuable because of that.
You also seem excited about it.
Comment #34 December 8th, 2023 at 10:19 am
Robin #32:
*Optimal* decoding of N syndrome bits scales horribly with N — it’s generally NP-complete. Therefore, scalable architectures use decoders that are suboptimal by an O(1) factor but scale polynomially (linearly is nice) with N. Once you restrict to low-polynomial-complexity decoders, the extra expense of jointly decoding multiple code blocks (correlated decoding) is moderate, and constitute a good tradeoff in situations like Craig describes.
Thanks, that makes sense!! I guess the deeper issue is just that, the more “degrees of freedom” there are in the choice of decoding strategy, the more one worries that the experimeters fiddled with things until they could claim a net gain. As long as
(1) one fixed the decoding strategy in advance and
(2) that strategy is efficiently scalable to arbitrarily many code blocks,
then there’s no objection.
Comment #35 December 8th, 2023 at 10:26 am
I’ll be truly surprised when a quantum computer will have a Hilbert space bigger than the number of particles in the quantum computer. With Avogadro’s number at 10^23=2^76, I’ll be truly surprised and convinced when we get ~80 qubits quantum computer (logical or physical, so long as the fidelity is high enough).
My bets are that quantum computers will scale well, error correction will work, everything will appear fine so long as the Hilbert space is smaller than the degrees of freedom in the system, but once you pass that threshold, no error correction will be able to correct for the fact the physical system doesn’t have enough degrees of freedom. So I’m predicting everyone hitting a brick wall right around the corner and failing to breach it.
I’m convinced that an ensemble of 10^23 particles can behave like a quantum computer of 48 qubits. The comparison with existing classical computers is misleading. Everyone’s dancing around quantum computers with 50 physical or logical qubits but nobody is demonstrating 80 qubits with good fidelity. I bet they can’t, the limit is just around the corner and the success so far is because Avogadro’s number is huge.
There are rumors that Google’s 70 bit new quantum computer is having issues. I want to see an 80 qubit quantum computer performing a random unitary and its inverse with good fidelity. I bet they will all fail. And it’s a huge problem that we’re not hearing about the failures because I think we’re at the peak and we don’t realize it yet.
Comment #36 December 8th, 2023 at 10:32 am
Hal Elrod #31:
On the other hand, if Google hands you a sack of money to bless their AI, then do what you need to for your family. Life’s full of tradeoffs.
For whatever it’s worth, I’ve already turned my back in life on the large sums of money that could be available to me for “blessing” things (like QC startups) that I don’t really believe in. I only accepted the OpenAI position because it seemed not like a sinecure, but like a serious opportunity to engage with a central new frontier of CS. And after a year and a half, I remain at least as excited about that frontier as I was when I was started! My biggest uncertainty, as I said, is just how much a complexity theorist like myself can contribute to it.
Comment #37 December 8th, 2023 at 10:47 am
Physics student #35: I respect that you’ve made a clear, falsifiable prediction. Unfortunately, your prediction seems already falsified. The Harvard/MIT/QuEra experiment that we’re currently talking about, for example, used neutral atoms — so, a tiny number of particles, not 1023. Yet it demonstrated IQP sampling with 48 logical qubits, presumably requiring a 248-dimensional Hilbert space.
Comment #38 December 8th, 2023 at 10:51 am
Quantum Computing now suprisingly feels more mature. It is based on Physics, experimentally verifiable and progress happens in small increments.The hypetrain has moved on, there are no more claims, it will change everything.
Now the hypetrain has stopped at AI. We have seen huge advances in media generation (pictures, texts, …), but it attracts all the wrong people. Snake salesmen, Copyright scandals, Apocalypse cults, bored Billionaires, inEffective Altruists, Crypto Apes, etc. All the people you wouldnt want to associate with.
I am sure they will move on, and we will see changes in media consumption and better Siri, but will there be enough for a really changed world? I personally doubt there will be many positions like your current one in 10-20 Years. Quantum still has such positions.
Alternatively, you can see it another way: You already have advanced humanity total knowledge in small steps. Some of it even with mathematical proofs, the safest type of knowledge. Does your current work allow similar results? Might there be a future, where a good percentage of AI systems have an Aaronson module, improving their capability? Based on your current work? Realisticly, i know in wishful Thinking every AI has a “Tobias Controler” forcing it to do only metaphysically good deeds.
On a related note: how sucessful is your work? Iremember something about output watermarking, does this produce better checks than the tool they published for a day and took down because it was 25% correct? There is demand for a way to identify a text as ChatGPT vs student homework.
Lastly, is there a chance to comdine both fields? In old SF, the electron brain is a prototype of a quantum brain. In some biologist speculation, the brain needs quantum randomness to create free will. can such research answer basic questions like P=NP or objective collapse vs many worlds? These answers would be way more fundamental than a language based GAI, bpt could you research them as QC professor or AI engineer?
Sorry if I’m rambling, but the train is on strike and the bus is slow and i have time for some thoughts. Thank you for the quantum updates I nearly understand and good luck with the future job.
Comment #39 December 8th, 2023 at 11:10 am
It looks to me what about 25% to 50% of the QC comments on this blog are about getting you to comment on some development in the news — e.g. IBM’s latest work, or what D-Wave is up to. They are afraid that the press releases are hype and are concealing things that invalidate the achievement.
And, coincidentally, some fraction of your audience will come to view your AI posts in a similar way. They think Google or OpenAI is faking them out, having read an endless stream of criticisms on social media, and being unable to sort through it all to see who is right. And they think the same thing about many prominent academics in ML like Yann Lecun (because he is a senior researcher at Facebook / Meta he is considered tainted).
So you have credibility as an independent, third-party adjudicator of claims in QC and AI put out by corporate labs, and this credibility means these 25% to 50% of people will continue to come to see what you have to say about both fields. (I don’t have any advice on which fields to continue posting about.)
….
Given that I think it’s only a matter of a small number of years until AI will be able to generate original research in QC, math, other computer science, physics, and more, AI will soon be discussed quite a lot even by people in these other fields that currently think of it as “just engineering” instead of “theory, which is what’s *really* important”. Among other things, people will want to discuss how their sense of meaning has shifted, and wonder what their fields ever really meant to them to begin with. Maybe they will come to this blog to hear what others have to say. (I don’t personally plan on coming here much, except to occasionally read a post or two; I’m cutting back on social media).
I think a lot of people (in math, CS, physics, etc.) haven’t really thought this through. They probably tell themselves that it’s about “the quest for truth” or “expanding the frontiers of knowledge” or some other high-minded thing like that. That’s undoubtedly part of the answer. But they probably forget that not all truth is equally valuable. Part of what makes a result “surprising” or “engaging” is mostly a feature of their own cognitive limitations — if they were 100x smarter then they would deem those arresting new discoveries someone had made to be “trivial” and not worth wasting much time on.
Part of it is due to a strange value system absorbed over many years — maybe it began in elementary school, high school, and/or college when they were handed trophies and prizes and told how great they were; then they went to grad school and got *really* pulled in, with each reward or criticism bending their very identity and sense of self-worth towards greater and greater academic achievement; and maybe this continued on to postdoc and faculty positions, with them getting ever more deeply sucked-in, until who they are became identical with what they’d accomplished (what papers they’d written, ideas they’d generated). It’s like how last names used to be assigned, where Mr. Flechter made arrows and Ms. Baker baked bread.
And part of it all is just that people see the enterprise of scientific work as a competition, with the winners triumphing over the losers. The winners are the “good guys” pushing mankind to ever greater heights. And the losers? Those are the people who lack ambition or don’t work very hard or are parasites, or so the thinking probably goes.
When AI starts proving very deep theorems and coming up with highly counterintuitive-but-true conjectures, all these people are going to have to confront these fundamental questions of identity, and will come to blogs like this one for answers.
Comment #40 December 8th, 2023 at 11:14 am
Have you considered work on reforming academia in light of the wave of antisemitism we’ve been seeing? As a famous academic and communicator, you might do some good there. Maybe with University of Austin. Maybe with a new Zack Weinsersmith book or something. But one thing we know about resisting antisemitic genocide is that it can be done successfully since it has been done successfully for thousands of years, although with some close calls.
Comment #41 December 8th, 2023 at 11:26 am
starspawn0 #39
When AI starts proving very deep theorems and coming up with highly counterintuitive-but-true conjectures, all these people are going to have to confront these fundamental questions of identity, and will come to blogs like this one for answers.
I hope I’ll have those answers by the time people come here for them! 😀
Comment #42 December 8th, 2023 at 11:30 am
Scott: On the career choice, where are your heart and soul? Or as a friend put it “What puts fire in your belly?” Your contributions will no doubt be huge in either area.
On another topic, I ended my long-running contributions to Democracy Now. Amy is amazing, but their incessant Israel-bashing with barely a mention of the genocidal terrorists who started this was too much.
Comment #43 December 8th, 2023 at 11:42 am
Scott #29:
> I had thought that the reason why correlated decoding belonged in the “limitations” column was that the computational complexity of doing it might scale exponentially with the number of code blocks — am I wrong about that?
I think it should be fine asymptotically, as long as you do O(1) transversal gate per round of checks. Though AFAIK no one has published a paper confirming this numerically. I guess it’s conceivable that someone performing a pattern of transversal CNOTs akin to an expander graph could complicate the decoding enough to force them to slow down.
One notable gotcha is that having the decoder understand transversal gates does change the nature of the decoding problem. In particular, in the context of surface codes, transversal gates break the ability to use straight matching when considering the system as a whole. Near the transversal gates, some measurement errors in the bulk will produce three detection events (one being in the other logical qubit). But the correctness of matching relies very crucially on bulk detection events always coming in pairs. This is actually another way that single round experiments are easier than multi round experiments: when you’re next to a time boundary it will swallow the third detection event, allowing you to still use matching. (For example, I took advantage of this when benchmarking folded surface code S gates in https://arxiv.org/abs/2302.07395 ). In a multi round experiment with transversal gates, you will need to explicitly deal with this uneven-detection-event-count issue.
I think union find decoding should adapt well to the transversal gate context with odd numbers of detection events in the bulk, so you could probably do that. I also think that color code decoders have to solve an isomorphic three-detection-events-in-the-bulk problem. In fact next week (fingers crossed) I’ll be publishing a paper with some new color code circuits and an open source color code decoder. One of the cases I tested it on was decoding a transversal CNOT in a multi-round surface code circuit, though IIRC it had O(d) rounds of padding. I think it should be possible to make it work with O(1) rounds of padding, but haven’t tested that.
Comment #44 December 8th, 2023 at 11:47 am
In other news “Sam Altman” appeared in last Sunday’s New York Times Crossword Puzzle.
I enjoyed your podcasts referenced in your last post so I hope you just continue what you are doing.
I still do not like Newcomb’s Paradox. The choosing player can resolve through free will to make his decision based on the outcome of some quantum measurement so the predictor then has no deterministic basis to load or not load the box.
If AI safety is targeted toward preventing an AI developing free will and acting in accordance with its own interests to the detriment of humankind then still, at this time, more fiction than science. If it is rather targeted to the immediate case of humans using AI to the detriment of other humans than hopeless, humans being what they are. If you are not really interested in any practical case but just the ideas then still QC seems to me to provide much broader vistas but you know much better than I.
Comment #45 December 8th, 2023 at 12:05 pm
When you say that “AI will transform civilization and daily life”, is that based on what you already knew before you joined OpenAI? Or is there some new evidence that you’ve seen since then?
Comment #46 December 8th, 2023 at 12:58 pm
With respect to the question of “who showed/will-show the first logical>physical advantage”… I’ve surveyed the QEC experiment papers over the past two decades. Something that caught me off guard was how every single one of them, even the old NMR ones, managed to find some way to claim logical > physical. Doing single rounds instead of multiple rounds, doing rep codes instead of quantum codes, using detection instead of correction, postselecting out effects like leakage… there’s lots of ways to scale the difficulty to your current experimental capabilities.
IMO, if you focus on the benchmarks that actually matter, then 5 years ago the field was obviously physical>logical. Currently the field is arguably physical ~= logical. And within 5 years I expect the field to be obviously logical>physical across multiple architectures.
Comment #47 December 8th, 2023 at 2:00 pm
Maybe you can merge AI and QC:
all the potential paths in the latent space will constructively interfere near the “optimal” one (aka The Truth), while the rest (aka The Hallucinations) will destructively interfere… or something like that.
(Just remember to thank me in your Nobel prize speech!)
Comment #48 December 8th, 2023 at 2:41 pm
Timothy Johnson #45:
When you say that “AI will transform civilization and daily life”, is that based on what you already knew before you joined OpenAI? Or is there some new evidence that you’ve seen since then?
No, it’s based on the staggering advances that the entire world has seen over the past couple years, things I would’ve seen with or without joining OpenAI, and on trying to project those advances forward one more decade. There were six months when I could see the AI future a little more clearly than most people, due to having early access to GPT-4, but that ended almost a year ago.
Comment #49 December 8th, 2023 at 2:43 pm
Craig Gidney #46:
IMO, if you focus on the benchmarks that actually matter, then 5 years ago the field was obviously physical>logical. Currently the field is arguably physical ~= logical. And within 5 years I expect the field to be obviously logical>physical across multiple architectures.
I might have to pay you the highest compliment by stealing that line! (If so, though, I’d better do it soon…)
Comment #50 December 8th, 2023 at 2:45 pm
OhMyGoodness #44:
I still do not like Newcomb’s Paradox. The choosing player can resolve through free will to make his decision based on the outcome of some quantum measurement so the predictor then has no deterministic basis to load or not load the box.
In that case, the predictor can just put the $1M into the first box with whatever probability it predicts you’ll take the first box only, and the paradox stands.
Comment #51 December 8th, 2023 at 2:50 pm
Michael Vassar #40:
Have you considered work on reforming academia in light of the wave of antisemitism we’ve been seeing? As a famous academic and communicator, you might do some good there.
I mean, I wrote 4 or 5 blog posts on this subject in the past two months! Given that thousands of others have been penning op-eds on this, and given that I suck at academic politics—I’m as certain of that as of any statement about my strengths and weaknesses—what else would you suggest I do?
Comment #52 December 8th, 2023 at 3:03 pm
I agree with several other commenters that of course you should work on whatever you feel most motivated about. But personally, I read your blog mainly for your fascinating complexity and quantum computing posts, so I know what I would prefer.
Comment #53 December 8th, 2023 at 7:13 pm
RE QC vs AI, obviously you should do what interests you the most personally etc. etc. but since you asked for outside opinions, here’s mine:
There is a LOT of room for advancement in both areas, but it seems like AI is the kind of problem where lots of people banging at it with brute force is going to be what gets us somewhere with it. For QC, this seems to be less the case, and so I think it’s more likely that you will have a more unique impact on it as an individual.
RE quantum computing advancements, It’s really exciting that you think that a demonstration of Shor’s algorithm might be forthcoming. However, as a chemist (who does a lot of work with computational chemistry) What excites me the most is the prospect of using quantum computers to simulate moelcular entities. Do you know what kind of fault tolerance would be required to accurately simulate a small molecule? How close is that looking to you? I know there have been recent advances in this as well, but the noise is still prohibitive.
Comment #54 December 9th, 2023 at 12:27 am
I don’t understand the distinction you are making.
In the case you mention the predictor makes a probabilistic assessment and so it is not infallible or near infallible. The predictor accepts no deterministic assessment is possible and is simply wagering on the outcome of a quantum measurement just as is the normal case. It simulates the quantum measurement and finds say a probability of 50% that both boxes are selected and so is free to choose if the box is loaded or not. There is no basis for deciding otherwise and the box is loaded or not-it can’t be in a state of superposition. The predictor would have a 50% chance of being correct. Since no absolute determination is possible the predictor then, presumably, would never load the box since the problem statement suggests no penalty for the predictor in the case the prediction is wrong and does imply the predictor for some reason wants to limit the gains of the chooser.
I hope you don’t consider this not even wrong. 🙂
Comment #55 December 9th, 2023 at 4:06 am
[…] Scott Aaronson[:] I think it [Google/Sycamore] represented a huge advance in scaling up and benchmarking NISQ devices. I think it showed the major result that the circuit fidelity scaled simply like the gate fidelity to the number of gates, and if that continues to be the case, then contrary to what you say, fault-tolerance will ultimately work. I also think that tensor network and other methods have gotten better at spoofing Sycamore’s Linear XEB score classically, nearly wiping out the quantum advantage as measured by time, though a significant quantum advantage remains as measured by floating-point ops or energy expenditure for the same LXEB score. We knew that quantum supremacy would be a moving target; recent progress underscores the need for better gate fidelities (which, fortunately, seem to be happening anyway) to stay ahead of classical computing on these benchmarks. Further updates (Dec. 2023): In the comment section Greg Kuperberg (March `23) drew my attention to three advances: 1) The Quantinuum ion trap experiment: https://arxiv.org/abs/2107.07505 https://arxiv.org/abs/2208.01863; 2) The Yale experiment: https://arxiv.org/abs/2211.09116 3) The Google experiment: https://arxiv.org/abs/2207.06431 (see also the comment by Craig Gidney). To this we can add a recent paper by Bluvstein et al. https://arxiv.org/abs/2312.03982 (Harvard/MIT/QuEra group) https://arxiv.org/abs/2312.03982 that is also discussed in this SO’s post. […]
Comment #56 December 9th, 2023 at 4:49 am
I think the only task in the AI field that is really worth doing right now is developing an algorithm that will analyze the consistency of politicians speeches and doings. And making this information public.
The world is already very technologically advanced, but all this can be turned to hell if people with bad faith and intentions capture the power around the globe.
Sure, QC also pushes our technologies further. But it also gives us a better understanding of the world we are living in. And, perhaps, could unite us more with it.
Comment #57 December 9th, 2023 at 6:23 am
OhMyGoodness #54: See if my reply in a different thread to Dimitris (who coincidentally had the exact same confusion as you) helps you in getting this.
Comment #58 December 9th, 2023 at 8:35 am
“Do any of you have strong opinions on whether, once my current contract with OpenAI is over, I should focus my research efforts more on quantum computing or on AI safety?”
I think you should spend less time blogging about “hot topics” that lead to large, heated, but ultimately unproductive conversations, use the extra time to think your own thoughts, and not solicit advice from large crowds of relatively informed people (like me, here) about your next move. That’ll increase the chance that you do something really unusual and interesting.
Comment #59 December 9th, 2023 at 8:41 am
Thank you and need to think about it more. I wasn’t considering the case properly as set out in the paradox statement when the prediction is one box and the choice is one box. I simply assumed something other than is in the actual problem statement so that earnings are at most $1,000 when the prediction is correct and $1.1 million when wrong.
Comment #60 December 9th, 2023 at 10:49 am
Physics student #35 and Scott’s reply #37
I think Physics student did not mean to simply count the number of neutral atoms as the number of particles making up the quantum computer. You do need lasers and electronics etc. to control those atoms. It may not be easy to precisely define the number of degrees of freedom N in the control system needed for Nq hi-fidelity qubits, but it seems an interesting conjecture that N >= 2^Nq.
Comment #61 December 9th, 2023 at 11:35 am
Physics student #35 and Scott’s reply #37
I think Physics student did not mean to simply count the number of neutral atoms as the number of particles making up the quantum computer. You do need lasers and electronics etc. to control those atoms. It may not be easy to precisely define the number of relevant degrees of freedom N in the (classical) control system needed for Nq high-fidelity qubits, but it might be an interesting conjecture that N>=2^Nq.
Comment #62 December 9th, 2023 at 1:17 pm
I think the answer to the last question depends on how much you think your unique perspective of TCS can contribute towards AI safety, vs how much you are able to contribute to cutting edge QC research.
I am not at all qualified to evaluate the latter, but as a CS undergrad trying to get into ML research (which is of-course not nearly enough qualification, but it is something), I think the former can actually end up helping the field a lot. TCS looks to me like the only hope for true AI explainability.
ps: I have just recently discovered your blog and other work, and I have to say your TCS writings has really transformed my understanding of the world drastically, thank you for showing me the beauty of this field!
Comment #63 December 9th, 2023 at 6:19 pm
As a qc skeptic, I predict that Shor’s algorithm will work for small integers but for integers with the order of say a hundred bits, I would expect Shor’s algorithm to fail even with error correction.
Comment #64 December 9th, 2023 at 10:12 pm
Some commenters have suggested that the immaturity of the AI safety field is a reason not to get into it, but I’d guess it’s the opposite. Maybe there are results to be had for outsiders who bring in a new perspective.
The “prompt injection” problem could maybe be such a case. It’s practically important yet nobody knows what to do about it, and it’s not very amenable to the brute force engineering approaches that usually push AI forward.
Comment #65 December 10th, 2023 at 6:09 am
Physics or AI? Easy 😉 https://www.smbc-comics.com/comic/agi-3
Comment #66 December 10th, 2023 at 7:06 am
foo #65: LOL
Comment #67 December 10th, 2023 at 7:39 am
Assuming known laws of physics hold, how can qc fail? Nonlocal correlations of errors.
Where would they come from? QFT is famously a divergent power series. Why are higher order effects suppressed so that computationally accessible terms are relevant? Effective field theory, where cutoff energies suppress higher order terms.
Is it possible that effective field theory does not apply as strongly to highly entangled systems? Experiments for qft use unentangled or locally entangled systems.
Is it possible that higher order terms are relevant for large highly entangled systems? If so then qc could fail since higher order effects would be relevant for its state evolution, affecting nonlocal correlations.
A related question. In ep=epr, why is the n qubit cft necessarily k-local where k<<n? Is this just an assumption?
Is it a coincidence that the computationally accessible terms in qft are the relevant ones for accessible experiments?
So the question is, why should we assume that nature is such that k<<n and does k affect the order of terms in qft that are relevant?
Comment #68 December 10th, 2023 at 8:47 am
Johnny D #67: No, there’s nothing in effective field theory that should break down because of “too much entanglement” — only because of the energy exceeding the EFT scale. (In the context of quantum gravity, Harlow and Hayden’s work on the black hole firewall paradox complicates this statement, but not in any way that should be relevant to quantum computation.)
In any case, I’m actually thrilled if, right now, anyone with ideas about how “exotic physics will kill scalable fault-tolerant QC” goes public with specific predictions, since I think it’s very likely that we’ll have the opportunity to test many of these predictions soon! 🙂
Comment #69 December 10th, 2023 at 10:36 am
Johnny D #67:
QFT is not famously a divergent power series. The perturbative treatment of a QFT is. Without looking for sci-fi stuff like EP=EPR, just look at chiral perturbation theory, the EFT of QCD: the only problem for its validity (as Scott correctly points out) is the energy scale (the cut off).
As for QCs: I’d say that the problem is not the amount of entanglement itself, but the control of it. How many (entangled) qbits can be reasonably control with sufficient fidelity? Some commenter above made an argument based on the Avogadro number (which in a QC will comprehend the stuff out of which lasers, traps, silicon around fluxes and currents etc..) are made of. This argument reminds me the one of Dyakonov, just put in another way.
As for QM itself, QCs should work. To me, the problem remains the experimental one: control and isolation (first studies on the effects of cosmic rays and natural radioactivity are appearing).
We will see: for me it is just fascinating to see how things will evolve and personally, the fundamental excitement comes from the more scientific/philosophical question: what are the limits of computation of physical systems in our universe?
Comment #70 December 10th, 2023 at 11:35 am
Scott,
About AI safety, would you say that there exist identified well-posed mathematical questions that a theorist (with a background in TCS, quantum or crypto) could readilly tackle, or is the field still too young for such well-posed problems to already exist?
Comment #71 December 10th, 2023 at 12:06 pm
Shion Arita #53:
A couple of posts ago Scott linked to a survey discussing the prospects of quantum algorithms for various applications:
https://arxiv.org/pdf/2310.03011.pdf
The quantum chemistry section seems far from optimistic to me; I’d be interested to hear your thoughts.
Comment #72 December 10th, 2023 at 5:34 pm
Re: “whether, once my current contract with OpenAI is over, I should focus my research efforts more on quantum computing or on AI safety?”
I hope very much that you will focus your research efforts on quantum computing (both new research and expository papers, lecture notes, etc.). Reasons:
1) There are plenty of great AI-safety researchers and communicators.
2) You probably have the richest TCS-oriented understanding of QC of anyone alive. That is extremely special, and valuable to humanity. You can draw on that to make deep, beautifully communicated contributions to the field (of the kind that younger researchers cannot make no matter how smart they are), to contextualize and assess new results more quickly and clearly than anyone else, to write surveys, maintain lists of open problems, etc.
3) You have honed to perfection your ability to communicate about QC at every level of formality. Your expository papers, book, blog posts, lecture notes, interviews on TCS/QC topics are some of the best works of math exposition ever produced.
4) I would guess thinking/communicating about quantum computing will make you happier in the long run (and for the above reasons, also be the way you can use your distinctive skills to help humanity the most).
Thanks for all your work, and especially for devoting so much time to exposition!
Comment #73 December 11th, 2023 at 3:22 am
If working on AI safety or on QC are both equally appealing to you from all other perspectives, I think it’s a no-brainer – of course you should work on AI safety.
The chance that you alone can make a difference that will save humanity is tiny, but it’s much bigger working in AI safety than QC. More realistically, you’re much more likely to help in more “mundane” ways – maybe not solving alignment, but even doing some other things to help with AI safety is incredibly important, anything from helping the “ethical” use of AI, to even just improving the existing AI so people can use it more effectively. I don’t think QC has anywhere near that impact.
I personally ask myself all the time if I should be switching focus to help with AI safety, and I don’t have the benefit of being a top CS researcher, I’m just a software developer.
Of course all of that is assuming the two paths are equal in other ways – if one pays more, is a better fit for you personally, even just you enjoy one over the other – that is a legit reason to work on that one instead.
Comment #74 December 11th, 2023 at 5:04 am
John Baez #58 wrote: “large crowds of relatively informed people (like me, here)…”
Sorry, I meant to type “relatively uninformed people”.
Comment #75 December 11th, 2023 at 6:17 am
The thing with a machine that could predict someone’s action and write it on a card inside an envelope, etc. And then the claim that “it would all break down if the envelope was open earlier because the person could then change their own action ahead of time as a result of reading the prediction” is misguided because it’s got nothing to do with the machine’s prediction being wrong per se, it’s just a general observation about feedback loops, with questions like asking a machine to predict its own output and the machine and its own output now become part of the thing that needs to be predicted, and it’s an impossibility because it would require infinite regress and resources, etc.
On the other hand, even when the person opens the envelope ahead of time, the machine could trivially maintain a second “hidden” envelope, the real one, that would correctly predict the person’s action as a result of opening the first envelope.
That’s like asking a kid to pick between black and white, and then write the prediction “you’ll choose white” on a card, show the card, the kid says “black!”, and you show the second card that says “I really knew you were gonna say black”.
Comment #76 December 11th, 2023 at 6:48 am
Btw, when it comes to “computational irreducibility”, Wolfram does say that it’s not something new, that many people had an implicitly understanding of it, citing Newton as an example, that he knew that his laws of gravity wasn’t enough to do predictions, and that no matter how much you reduce a system, that smallest efficient model still needs to be run, step by step.
Comment #77 December 11th, 2023 at 7:13 am
When it comes to Many-World vs Copenhagen, with Copenhagen claiming that the wave function is just a mathematical model to come up with “real” probabilities, it’s a bit as if, in order to model gravity and predict the motions of planets, you’d come up with a complex model that requires doing math in a space that has 2^N dimensions (N being the number of planets), and then in the end reduces to a result in 3 dimensions. In some ways the model seems more complex that the thing is simulates.
On the other hand, Many World would claim that the real system with N planets actually works in 2^N dimensions, it’s just our perception of it, as observers, that’s more limited to only 3 dimensions.
Comment #78 December 11th, 2023 at 9:01 am
Please keep working in AI safety! It seems critical. It is good for the world. Assuming you enjoy it, of course. I just read your comment on Scott Alexander’s blog and decided to comment here ! AI safety needs good people who care about the world.
Comment #79 December 11th, 2023 at 10:24 am
play to your strengths, which I take to be quantum complexity and not LLM-wrangling..
Comment #80 December 11th, 2023 at 10:39 am
Explaining consciousness with IIT, or any critique of IIT that itself assumes that consciousness is the result of a “computation” or “information processing”… the problem is that any computation can be reduced to a look up table (e.g. LLMs are just about multiplying two matrices of floats).
So you have to either accept that look up tables are conscious or that consciousness is the result of some implementation specific physical process (e.g. micro tubules and whatnot).
There isn’t room for anything else, really.
Comment #81 December 11th, 2023 at 10:55 am
About choice of field, my advice, based on a similar choice that I made, is:
If you love one field more than the other, give yourself to the field that you love. It is possible that your love for that field includes, in an unconscious but real way, the expected utility of that decision.
If you’re not sure which field you love most, then please pick AI safety, as to me it seems more urgent at this time.
Comment #82 December 11th, 2023 at 3:45 pm
Regarding focusing on quantum computing vs AI safety: you worry that you may have less of a comparative advantage in AI safety work. One possible path to safe systems that some advocate for (eg Max Tegmark IIRC) is provably safe AI. This seems like a potentially promising direction, but I think it will involve proofs whose connections to physical reality are are very difficult to think clearly about, and where many people may get confused by proofs that are superficially convincing but fail in subtle ways to connect to reality. Since proofs in quantum mechanics and quantum computing seem to me to have that same property, this strikes me as an area of safety where your particular skills and aptitude could bring quite a lot to the table.
Comment #83 December 11th, 2023 at 5:07 pm
OhMyGoodness #44:
I still like Scott’s intuitive solution of Newcomb’s Paradox. I knew Newcomb’s Paradox before, but I no longer remember whether I ever worried about it. My position was that you should not take both envelopes, but my reasoning was based on the actual payouts (like your reaction in OhMyGoodness #59), instead of on a coherent argument like Scott’s.
A paradox that did confuse me was Sleeping Beauty. Encouraged by Scott’s convincing argument, I now googled whether there is a similarly convincing argument for Sleeping Beauty. And indeed, B. Groisman in 2008 described a similarly compelling picture for the position that the problem, as stated, is ambiguous. I like it.
Comment #84 December 11th, 2023 at 5:43 pm
fred #75, #76, #77, #80: I know that only reacting when somebody is writing something incomprehensible or unwise is a bad incentive, but I can’t resist. Your rapid succession of strangely unconvincing arguments feels strange to me, especially because normally your comments make perfect sense.
#75: But this last word property is not misguided, but the crucial point. There can be only one last word. So if two actors both “believes” to have the last word, one of them must be wrong (at least if their last words contradice each other).
#76: I don’t think that citing Newton as an example can be interpreted as a proper appreciation of all the existing understanding and work on computability and computational complexity. Rather the opposite.
#77: I am not sure why you bring-up Many-Worlds vs. Copenhagen. Your image is more or less OK for me. However, you wrote “In some ways the model seems more complex that the thing is simulates.” as if the proponents of Copenhagen didn’t knew that. Feynman fought with this question in his 1982 keynote speech, explaining how a similar phenomenon also seems to occur with classical probabilities, but can be overcome in that case.
#80: This “look up tables” argument doesn’t convince me. It also reminds me of Searle’s Chinese room.
Comment #85 December 12th, 2023 at 4:40 pm
Regarding your “It should now be possible, among other milestones, to perform the first demonstrations of Shor’s factoring algorithm with logically encoded qubits”:
Do you think that the challenge posed in https://doi.org/10.3390/math11194222 might be within reach in the near future?
Comment #86 December 12th, 2023 at 6:45 pm
dennis #85: That looks like a 40-bit number, meaning with the most space-efficient known version of Shor’s algorithm, you’d want 160 logical qubits. So then, maybe ~10,000 physical qubits if you wanted a net gain compared to not using error-correction?
This is conceivable in the medium-term future, but I’d definitely start by factoring a smaller number. 🙂 Note that even doing 15=3×5 using logical qubits (rather than bare physical qubits) would already be a major milestone.
Comment #87 December 12th, 2023 at 11:26 pm
Happy Hanukkah Scott and thanks for your interesting, instructive, and prolific blog.
Based on your own remarks, I would recommend you focus your research efforts on quantum computing. That’s where you feel confident you can make the most unique and valuable contribution. You can always spend time on AI safety when you think and/or feel it warranted, even if some self-doubt creeps in.
Comment #88 December 13th, 2023 at 1:04 am
I would suggest AI safety at an Israeli university or startup
Comment #89 December 13th, 2023 at 7:45 am
(I wonder if Scott reads comments posted a week later. If he responds then I will know that he does. If not then I won’t know anything since it could be this was not worth responding do.)
The `Should Scott do AI (Potential to really help humanity, but there are others already doing that who know more) or Quantum (less likely to help humanity, but he is really making a contribution)’ is a great question which generalizes to other people in other fields.
Here are the key followup questions:
1) Is QC reaching the point where people work harder and harder to get less interesting results?
2) Does QC still fascinate you? (I would guess YES)
3) Does AI fascinate you? (I would guess YES)
4) Which do you find more interesting to work on?
5) You say that there are lots of people in AI who know more than you do. Is the field’s learning curve easy enough so that you could (and perhaps already have) caught up?
6) Does your TCS/QC prospective give you something to contribute to AI?
7) Does your AI prospective give you something to contribute to TCS/QC?
8) (This is probably not important) Does your school care what you work on? Grants? Teaching? The whole point of being a Full Prof is that you don’t have to care about this issue,
but I ask anyway.
9) Is UT Austin a good place to do QC? AI? (And does this matter anymore in the electronic zoom age)
10) Do you need to decide? That is, could you work on both, deciding on a day to day or week to week basis `I feel like working on X’
Comment #90 December 13th, 2023 at 7:48 am
Scott #86: Thanks for your reply. Only to be clear, where do the 4n qubits for your “most space-efficient known version of Shor’s algorithm” come from? Is it Beauregard’s 2n+3 qubits plus 2n qubits because you do the QFT quantumly and not semi-classically=iteratively (i.e. you do not require mid-circuit measurement)?
Because if you do the QFT iteratively (as we do in our paper and as Gidney requires in his estimates), I think the total number of logical qubits for the most space-efficient known version is 2n + const.
Comment #91 December 13th, 2023 at 9:46 am
dennis #90: Ah, I stand corrected then, by a factor of 2. I had remembered ~4n, but you’re right that that’s out of date.
Comment #92 December 14th, 2023 at 4:30 pm
[…] The wider quantum community met the results with cautious excitement: “Assuming the result stands, I think it’s plausibly the top experimental quantum computing advance of 2023,” Scott Aaronson, a computer scientist and director of the University of Texas at Austin’s Quantum Information Center, wrote on his blog. […]
Comment #93 December 15th, 2023 at 12:16 am
I say stay with QC. You’re relatively better at it, and both are very important.
Comment #94 December 15th, 2023 at 8:00 pm
I’m pretty sure the lowest known (and little known) space cost for factoring an n bit number is 1.5n + O(log n) qubits, assuming noiseless qubits. Zalka explained how to do this in https://arxiv.org/abs/quant-ph/0601097 , amongst several other good ideas.
The basic idea is what I’ll call “pseudo factoring”, where given an n-bit modulus N and an integer k you can find an n/2-bit integer x and an n/2-bit integer y such that x = k*y (mod N). You find x and y by stopping the extended GCD algorithm halfway through running it. The point is now you can multiply by k (mod N) by multiplying by x and inverse-multiplying by y. And since x and y have at most n/2 bits, whereas k had at most n bits, this lets you use half as much extra workspace. Here’s example code with the pseudo-factoring and the reversible modular multiplications: https://gist.github.com/Strilanc/d08dc245a9661fb9f61359b5f756d9e0#file-zalka_half_workspace_mod_mult-py-L230
Comment #95 December 22nd, 2023 at 7:29 pm
gentzen #84
“#75: But this last word property is not misguided, but the crucial point. There can be only one last word. So if two actors both “believes” to have the last word, one of them must be wrong (at least if their last words contradict each other).”
yea, but that’s my point too, letting the human peak at the prediction so he/she can change his/her mind is just the same idea, you can keep doing that forever. Once the reaction of the prediction is part of the prediction, things can’t stabilize, just like with the sentence “this sentence is lie” flipping forever between true and false. My point was also that once the prediction influences the choice, the idea of “free choice” vanishes. It all becomes a psychological manipulation.
#76: I don’t think that citing Newton as an example can be interpreted as a proper appreciation of all the existing understanding and work on computability and computational complexity. Rather the opposite.
I think the idea was to show that already, as far back as Newton, there was a sense that just coming up with a law wasn’t enough if there was no analytical solution, you’d have to turn to some numerical resolution which shows that you have to just “run/simulate” things step by step (e.g. in the three body problem).
Comment #96 December 23rd, 2023 at 8:02 am
fred #95: The tricky part is to accept that there is a last word, and only one last word. This is the tricky relation between halting Turing machines and natural numbers: To accept that the machine does halt, that there is a last step. This the deep meaning of “finite”, that there is an end.
I have not seen the exact context where Wolfram mentioned Newton, but it would take quite some argumentation for Wolfram’s side to convince me that he is relevant in the context of computational irreducibility. I find Wolfram’s dive into the history of combinatory logic more relevant as an attempt to understand where those thoughs first arose.
Comment #97 January 2nd, 2024 at 8:45 am
[…] The wider quantum community met the results with cautious excitement: “Assuming the result stands, I think it’s plausibly the top experimental quantum computing advance of 2023,” Scott Aaronson, a computer scientist and director of the University of Texas at Austin’s Quantum Information Center, wrote on his blog. […]
Comment #98 January 13th, 2024 at 8:39 pm
[…] In an interview with The Quantum Insider, Dolev Bluvstein, graduate student at Harvard who spearheaded the investigation, and Harry Zhou, research scientist at Harvard and QuEra Computing and key contributor to the work, offered a deep dive into the method from their recent Nature study that garnered headlines around the world and even earned the praise from Scott Aaronson, the Schlumberger Centennial Chair of Computer Science at The University of Texas at Austin, and director of its Quantum Information Center, who called it “plausibly the top experimental quantum computing advance of 2023.” […]
Comment #99 April 3rd, 2024 at 12:29 pm
[…] yet quantum computing continues to progress. In December we saw QuEra announce a small net gain from error-detection in neutral atoms, and accuracy that increased with the use of […]
Comment #100 April 3rd, 2024 at 1:52 pm
[…] but quantum computing continues to progress. In December we saw QuEra announce a small web acquire from error-detection in impartial atoms, and accuracy that elevated with using […]
Comment #101 April 3rd, 2024 at 6:14 pm
[…] but quantum computing continues to progress. In December we noticed QuEra announce a small internet achieve from error-detection in impartial atoms, and accuracy that elevated with […]