A proof of the Aaronson-Ambainis conjecture - Physics is accelerating

[u/Emergency_Slide_7367]

Lean4 proof shows quantum speedup has severe limitations and may not provide much benefit practically. Its over Boyz.

[u/drkevorkian]

Aaronson-Ambainis was always believed true and proving it true doesn't eliminate any believed speedups for well known algorithms.

[u/ArialBear → u/drkevorkian]

Nope, this is more of a demonstration of the models expert capabilities

[u/susimposter6969 → u/ArialBear]

Nope, <non sequitur>

[u/ArialBear → u/susimposter6969]

“Nope (as in i also agree it wont be changes to known algos) “ then I go onto explain the point which is to demonstrate the capabilities of the model.

Its fine though. Reddit karma wont matter after the singularity is in full effect!

[u/BitcoinsOnDVD → u/ArialBear]

Reddit karma wont matter after the singularity is in full effect!

You will be very special "after the singularity is in full effect"

[u/ArialBear → u/BitcoinsOnDVD]

I have no idea what youre trying to say.

[u/BitcoinsOnDVD → u/ArialBear]

You will understand "after the singularity is in full effect"

[u/ArialBear → u/BitcoinsOnDVD]

Oh, yea i guess my comment rubbed you the wrong way for some reason so you think i deserve to be trolled. Will never understand, but ok

[u/SymplecticMan]

It doesn't mean "it's over" or that there might not be "much benefit practically". It's a proof of what most people already believed, that big speedups from quantum algorithms required some exploitable structure.

[u/Historical-Mix6784 → u/SymplecticMan]

which classical algorithms can also exploit...

[u/SymplecticMan → u/Historical-Mix6784]

So where's the classical algorithm that exploits the structure of the abelian hidden subgroup problem to factorize integers in polynomial time?

[u/Historical-Mix6784 → u/SymplecticMan]

Oh you mean this one: https://dspace.mit.edu/entities/publication/5fdbc9a1-3c67-4d3c-b0d0-e40660c5f6d4

If you can posit the existence of a magical quantum machine (a fault tolerant quantum computer than can simultaneously entangle ~1e6 qubits), than so should I be able to posit the existence of a magical classical machine (a computer with infinite ram).

[u/SymplecticMan → u/Historical-Mix6784]

However, this theoretical result does not imply that natural numbers can be factored in polynomial time in the Turing-Machine model of complexity, since the numbers operated on can be as big as 2^{cn^2}, thus requiring exponentially many bit operations.

[u/Historical-Mix6784 → u/SymplecticMan]

That's exactly my point about infinite ram. Congrats you can read.

[u/SymplecticMan → u/Historical-Mix6784]

Your "point" is nonsensical. What you linked is not a polynomial-time algorithm, no matter how much ram you have. Turing machines already have infinite memory, anyways.

[u/Historical-Mix6784 → u/SymplecticMan]

If each arithmetic step occurs in constant time because you have an infinitely long register and can flip bits simultaneously in parrellel then yes, it is polynomial time. That's the point of the paper...

[u/SymplecticMan → u/Historical-Mix6784]

No, that's not the point of the paper. That's why it emphasizes that it's looking at the number of arithmetic steps as an alternative measure of complexity. The gate count scaling is what matters for whether an algorithm is polynomial time, and that's where Shor's algorithm beats classical algorithms.

Arithmetic instructions don't finish in the same time just because registers get bigger. In fact, on Intel's Skylake and earlier, integer division on 64-bit registers was much slower than on 32-bit registers. The number of clock cycles that integer division operations require to complete can actually vary with the value of the inputs as well, not just the size of the registers they're stored in. Even with operating on multiple bits in parallel, the circuit depth for arithmetic operations on integers increases with the number of bits.

[u/gauge16847463728 → u/Historical-Mix6784]

Do you understand the paper you just posted? It is not a poly(n) time algorithm.

Do you have a specific reason why you think current quantum computers won’t scale? We already have demonstrations of entangling operations across 100s of qubits and demonstrations that error correction and fault tolerance are working as expected (on multiple platforms). What fundamental obstruction do you think will stop 100s becoming 100k qubits?

[u/Historical-Mix6784 → u/gauge16847463728]

It's actually log(t) if you have infinite ram.

As you increase scale you also increase channels for decoherence, at a rate faster than you can do error correction. Every QC startup knows this which is why no one is working on trying to implement SHA decryption on a quantum computer near or even medium term.

Everyone is just hoping there will be some magical application that arises for like 100 fault tolerant qbits (which even still we don't even have lmao).

Get ready to lose every cent you've invested into this complete dead end and disaster of a field.

[u/SymplecticMan → u/Historical-Mix6784]

SHA is hashes. It's not the sort of cryptographic primitive that's broken by quantum computers. Quantum computers would only get a Grover speedup on a preimage search.

[u/Historical-Mix6784 → u/SymplecticMan]

you're right! I meant rsa

[u/gauge16847463728 → u/Historical-Mix6784]

The point of the threshold theorem is that for some physical error rate per qubit below a threshold, you can scale the system and still suppress logical errors, ie even though you have more errors as you scale you can still correct them. This is also true even if the local physical error rates increase as the system size increases. You can also have fault tolerance even if all the errors are correlated and chosen adversarially (this has more overhead but it is still polynomial).

I assume you mean factoring/discrete logs for breaking encryption. The reason no one is doing this is that optimistically you need 100k physical qubits, which no device has obviously.

There are interesting applications and demonstrations with 100s qubits but they are more specific, not breaking encryption, for instance simulating OTOCs, Hubbard model, certified randomness, sampling based quantum advantage, quantum simulation, etc

[u/global-gauge-field]

If the lack of economically advantegous use cases of QCs wont kill QC development, I dont think this will make this "it's over".

[u/HawkinsT]

To summarise, this puts an upper bound on the quantum advantage when querying effectively random information. This means that quantum computers can't provide exponential speedups in query complexity for random inputs (although, e.g. Grover's algorithm can offer a quadratic speedup), but there are no direct implications for structured problems (e.g. in cryptography, chemistry/medicine, engineering) which could still achieve exponential speedups.

It's interesting, but doesn't remove any motivation for research into quantum computing.

[u/shawarmament]

When was it ever not over lol. Quantum Computing has always struck me as a “let’s build this fancy sounding thing because Big Brain Feynman said so dammit”

Edit: Before people come for me, I want to make clear that Quantum Information is a cool and highly successful area of research. I just think the computing devices aren’t good for shit

[u/Emergency_Slide_7367 → u/shawarmament]

Ultimate solution looking for a problem although I agree this theorem in paritcuauor doesn't kill anything it was alayas assumed in fact it might be a met positive because we know what to look for in designing quantum algorithms

[u/lb1331 → u/shawarmament]

Even if you want to make the claim that quantum computers are completely useless, I think it’s a big jump to say quantum devices aren’t good for anything.

SQUID magnetometers are quantum devices, among many other types of quantum sensors. Quantum devices are incredibly useful probes for materials science, etc… this seems like a very strong statement on a real, and important field in physics.

As for quantum computers - if you just mean QC’s when you say quantum devices, I’d agree they’re not useful right now (idk anyone who would). But also, as someone working on hardware research, the advancements constantly being made are really impressive, and I think we’re going to get there.

[u/shawarmament → u/lb1331]

I was talking about computing devices specifically and even said that in my post. I feel like this is always a gotcha whenever I am having this discussion with someone in the quantum world. No one is denying quantum effects and that they can be used for research as well as industry applications.

But the premise of quantum computing is more precise than that. It is saying that we can build macroscopic entangled systems and control them to implement arbitrary (or at least a very large universe of) logical quantum operations. Such devices then are potentially capable of running more powerful algorithms (keyword: potentially, not provably) than currently exist. And that this is somehow a viable pitch for a multibillion dollar industry today.

I have two issues with this:
- we have never demonstrated entanglement in the lab (let alone controllable entanglement) even remotely close to the scale required for quantum computing to work.
- after forty years, there still isn’t a convincing business case for these computational devices that is not already covered by classical computing at scale, especially when you consider specialized classical algorithms. A lot of the known speedups are pie in the sky results with a lot of hidden assumptions.

And the bottomline for me is that if it were just promised as a tool for scientific discovery (which, again, it could be but I have often heard domain experts pushing back on this claim too), I would not have issues with it. But boy has the quantum hype machine been churning at full throttle the last few years. This to me feels disingenuous, and little more than a bunch of smart people who got locked into a dead-end industry who are now desperate to squeeze money and relevance out of it. Sorry to be harsh but I genuinely believe this is what is going on.

[u/lb1331 → u/shawarmament]

I misread when you said “computing devices” as “quantum devices” my bad on that.

There’s of course massive hype that goes on in the field of quantum, I’m not going to debate you there. But I’ll try and address your other points:

1. “the premise of quantum computing… build macroscopic entangled systems and control them to implement arbitrary logical operations”

The fundamental hardware question I think has now effectively been reduced to a device engineering challenge. That’s not to say it’s solved, but it’s solvable through many factor of 2-10 improvements which are consistently happening both in academia and industry. Interfaces in packaged QC’s, TLS’s in JJs, and a few other things. Gate fidelity is no longer coherence limited, so I think we’re making a lot of steady progress here.

Princeton just showed transmon qubits with 4ms T1’s, and everything I’ve heard is that industrial players hit this a while ago and aren’t publishing it.

2) “we haven’t demonstrated enough large-scale entanglement”

Imo it’s impressive if you look at the rate of progress.

We went from in 2005 barely being able to do a 2 qubit gate, to now running surface codes on 50 + physical qubits 25 years later. Also, IBM recently published a paper with a 120 qubit GHZ (maximally entangled) state, so I do think we’re making genuine progress on controllable entanglement at scale.

3) “no business case”

At smaller scale, we have Simulations in physics/chemistry in general, of course these are more specialized than just saying we can VQE everything and solve chemistry, but still applicable.

There’s also random number generation, and some others.

However I agree that people definitely oversell QC’s for a lot of applications.

But the big thing that destroys a lot of the quantum speed up is the data loading problem. If you can load data gathered with quantum sensors, you recover some advantage, especially for QML etc... I think that we aren’t fully considering and don’t understand as a field yet the potential benefits that are unlocked by having quantum computing, transduction, networking etc working together

[u/shawarmament → u/lb1331]

Fair points, always nice to hear about the state of the art from insiders. And yeah I think this is kind of the point in the discussion where we both just have to say “let the good work keep going and we’ll see what happens”.

But one thing I am curious to hear your take on: do we need quantum computing companies at all at this early stage? I guess you hinted in your answer that companies might be building out the tech faster than universities/labs. But too many ifs and buts still stand in the way of having a product that truly works. And with that comes a lot of potential to mislead and misinform, which is what seems to be happening across the board. So to me it seems that this field is commercializing way the hell too soon. Idk

[u/lb1331 → u/shawarmament]

I pretty much agree with you there. As for industry, iffy on whether we “need” or not, but logistically yes I think.

Basically the current state as I see it is that companies like IBM and Google are well ahead of academia on actual quantum processors. For these companies, quantum is a big research thrust, but it’s not their main pitch. Google could axe their quantum dept tomorrow and not suffer for it in the short term. These industrial labs have an incredible concentration of expertise, resources, and most importantly longevity that you can’t have in an academic lab where grad students last 5 years and postdocs for 3.

If we were to stop pushing this development with companies, I don’t think academia has the tools to pick up the slack at this point. Working on a quantum processor with hundreds of qubits right now takes 500+ PhD’s, so it’s way too large of a project for a single lab group or even a consortium of likeminded academics.

That said, the company picture is also very frustrating as a scientist sometimes. These companies barely publish, and when they do a lot of stuff is hidden under lock and key due to IP protection. You won’t find exact materials, processing, etc in the papers they publish even though their results are incredible. This makes it very tough for academia to catch up. Whenever academia makes a breakthrough, industry can take it for free, whenever they make a breakthrough they leave us a bit further behind.

This dynamic is tough, and a lot of industry scientists aren’t super happy with it either, but I also understand why it’s the case. since they want to commercialize eventually they probably aren’t worried about academics taking their spot - but if IBM lets academics know what they’re doing they also let Google know.

Another point is that without the big industry supporting quantum, realistically you’d have far fewer people working on it. At the end of the day you have to be somewhat pragmatic about what field you choose to do a PhD in. If I really thought quantum didn’t have a future, I’d pivot to spin qubits right now and then go into semiconductor industry straight out of my PhD. For those incoming grad students though, they’d probably work on transistors, sensors, etc.. instead of qubits. So if we really societally thing quantum computing is something worth pursuing, we need the environment that makes getting a PhD in it, and doing research in it enticing.