Ask HN: What has quantum computing achieved so far?
As a lowly web developer I struggle to understand what concrete progress has been made in quantum computing. I understand there are papers that have shown results that no classical computer could achieve but what has translated into practical applications?
131 comments
[ 3.9 ms ] story [ 183 ms ] threadI’m joking, but they absolutely had a different designer than the colliders
https://spectrum.ieee.org/media-library/less-than-p-greater-...
Larger cases of quantum factorization since then used non-scalable algorithms.
[1] https://arxiv.org/abs/1111.4147
noise is hell in QC, sadly
Guillaume Verdon (aka Beff Jezos on Twitter) is a physicist, quantum computing researcher, and founder of e/acc (effective accelerationism) movement.
https://www.youtube.com/watch?v=8fEEbKJoNbU
I wonder if it is sucking up all the oxygen in the room for “quantum” and “computing” in a sentence together. Classical computing that uses quantum effects seems more useful IMO. Quantum computing algorithms are too hard, let’s do quantum dot cellular automata instead.
https://en.wikipedia.org/wiki/D-Wave_Systems
> In December 2015, Google announced that the D-Wave 2X outperforms both simulated annealing and Quantum Monte Carlo by up to a factor of 100,000,000 on a set of hard optimization problems.[35]
Timeline of quantum computing and communication > 2023: https://en.wikipedia.org/wiki/Timeline_of_quantum_computing_... :
> 14 June [2023] – IBM computer scientists report that a quantum computer produced better results for a physics problem than a conventional supercomputer.[365][366] :
"Evidence for the utility of quantum computing before fault tolerance" (2023) : https://www.nature.com/articles/s41586-023-06096-3 :
> Quantum advantage can be approached in two steps: first, by demonstrating the ability of existing devices to perform accurate computations at a scale that lies beyond brute-force classical simulation, and second by finding problems with associated quantum circuits that derive an advantage from these devices. Here we focus on taking the first step and do not aim to implement quantum circuits for problems with proven speed-ups.
Quantum Algorithm Zoo lists speedups by algorithm; https://quantumalgorithmzoo.org/
https://westurner.github.io/hnlog/#q-tequila ctrl-f "tequila" :
From "Computational Chemistry Using PyTorch" https://news.ycombinator.com/item?id=36825353 :
> Tequila wraps Psi4, Madness, and/or PySCF for Quantum Chemistry with Expectation Values: https://github.com/tequilahub/tequila#quantumchemistry
And from https://github.com/tequilahub/tequila#quantum-backends :
> Quantum Backends currently supported by tequilahub/tequila: Qulacs, Qibo, Qiskit, Cirq (SymPy), PyQuil, QLM / myQLM
tequilahub/tequila-tutorials: https://github.com/tequilahub/tequila-tutorials
- tequila-tutorials/BasicUsage.ipynb: https://github.com/tequilahub/tequila-tutorials/blob/main/Ba...
- tequila-tutorials/Quantum_Calculator.ipynb : https://github.com/tequilahub/tequila-tutorials/blob/main/Qu...
Practical Q12 QIS STEM learning exercise ideas: https://news.ycombinator.com/item?id=38687045#38801630
(IIRC this is still the best; all the hype-y 2^xxx+1 PR ones aren't really using Shor's algorithm and also use some number theoretic short-cuts).
[1]https://research.ibm.com/blog/factor-15-shors-algorithm [2]https://arxiv.org/abs/1301.7007
I also feel it's a way to make the many-worlds interpretation of Quantum Physics more substantial - I mean, when you have a working QC, if the results of the computation isn't arising from interference between the many worlds, where are the calculations being done?
I had a similar feeling until I took a course on 'Theory of Quantum Information'. It cleared up some reservations I had about problems of Quantum Computing, e.g. error correction, and showed, that these are solvable (at least in theory).
But more important, the lectures made it clear for me, that information is a physical quantity not less real than e.g. energy and that treating it as a non-physical "auxiliary" variable is core to many of the perceived paradoxes of QM. Also Quantum Computers try to make Quantum coherence work outside of closed laboratory systems, which not only pushes the boundaries of experimental physics, but also leads to interesting theoretical problems, since open systems don't exhibit a unitary time translation and are therefore not governed by the Schrödinger equation.
These things together helped to spark a new interest in looking at the foundational questions of Quantum mechanics after decades of "Shut up and calculate".
The general consensus is that there will be a fault tolerant quantum computer by 2035-2040. So like silicon, it is going to take us a while to get there, but we are only talking about 11-16 years or so according to the best experts in the field (remember AI has similar longer terms before it rapidly accelerated).
And quantum computers are profoundly powerful — as in civilization changing computer power.
How is the time of this clear path measured? I actually have the exact same question about fusion reactors (such as ITER with results planned decades ahead of time)
What could speed up those decades? Letting more people work on it at the same time? Throwing more money at it? (e.g. for ITER, are we just waiting for them to pour concrete faster?)
Or are these decades of planning also waiting for other technologies to appear in 10, 20, ... years? (Which would be some kind of unclear uncertainty after all)
This has turned out to be a big problem (with some calling it potentially intractable.) But a lot of progress is being made in this area. There’s a good article in the current issue of Technology Review.) This is one area that could lead to outsized advances.
More money and people can usually move but there’s a limit to which just throwing money at a problem can accelerate the outcome in part because of all the complex interconnection, some not even appreciated. Think ML with GPUs.
ITER itself isn't even intended to achieve that. It's a research facility to test and demonstrate large-scale fusion in a tokamak. It's not even designed to generate electricity as output - just heat energy.
If ITER ends up demonstrating that its approach could be further improved in the direction of a commercial design - which is not at all clear (see reference below) - they'll have to start a new project to achieve that. And you can expect that project to take even more money and quite probably a longer time, since there will be a lot of advances that will still need to be made.
You might be interested to read "ITER is a showcase … for the drawbacks of fusion energy": https://thebulletin.org/2018/02/iter-is-a-showcase-for-the-d... . I recommend reading the whole article.
> Letting more people work on it at the same time? Throwing more money at it?
There are 6500 people all told that work on ITER, and its total funding is projected to reach as much as $65 billion. More people and money for ITER is almost certainly not the answer.
But other groups are also working on it, including 30+ fusion startups (see e.g. https://app.dealroom.co/lists/25184). However, ITER's funding is about 10-15 times that of all those startups combined. The problem with the startup approach is they're more likely to be killed if they don't achieve results.
> Or are these decades of planning also waiting for other technologies to appear in 10, 20, ... years?
For fusion, that's certainly the case. Despite the existence of startups, which perhaps reflect the existence of either altruistic and/or gullible VCs, fusion power is still very much a research project. It's not even certain that commercial fusion power will ever be viable - the article I linked helps explain that.
With quantum error correction, we're not talking a $25B facility with many competing hands in the pie. Instead, we're talking about improving the spatial and timing precision of RF, optics, and photonic hardware. Unlike fusion, where basically everything needs to be a custom job, there are established industries around these quantum-adjacent technologies with decades of accumulated know-how and plenty of low-hanging fruit to get most of, if not all of the way there.
https://www.scmp.com/news/china/science/article/3246752/chin...
Read the quotes. Global financial systems are trying to harden themselves with quantum computers in anticipation of forecast technology advancements.
Maybe this piece by 60 minutes is worth watching too to get a better sense:
https://youtu.be/K4ssT6Dzmnw?si=FseoJawRowldaaPH
It directly addresses technology progress and explains the basics.
We see customers getting requirement requests for using PQ safe crypto algorithms to be used in systems that will be used 30+ years. But that too is also just hedging the bets.
Quantum Key Distribution is feasible - esp for systems that don't need to move and where you own the medium. And can spend the 1000+ kUSD these machines costs. For most use cases (for example between a client and a server setting up a secure session over Internet) these machines does not solve anything. But they sure are very cool to own and deploy.
How so?
The main promise/fear I hear about is breaking cryptography, but then it sounds like we can switch to new post-quantum encryption and we’ll be essentially in the same place as before.
Post-quantum methods have other disadvantages, primarily that they haven't been studied as deeply as traditional methods (especially RSA) so they may be vulnerable to classes of attack we haven't thought of yet.
https://en.m.wikipedia.org/wiki/Post-quantum_cryptography
Some organsations MAY someday have Quantum Computers capable of cracking some asymmetric keys (RSA). All of us will have access to cryptographic algorithms (inlcuding open source implementations) that can't be cracked by the Quantum Computers. These algorithms are executed on our normal, classical computers.
We already have a first set of post quantum computer cryptographic algorithms. See the NIST competition for example. Their implementations still looks immature (some have fallen against classical attacks, including side channel issues). But we'll get there. We will also have to (yet again) deal with having algorithm agility, which adds complexity.
Quantum Computers are not magical things. We can (and do) know type of problems, algorithms, operations they should be better than classical computers to solve (called quantum supremacy). Shor's algorithm, which provides exponential speedup of cracking RSA key is an example of such an algorithm.
What we so far don't consider that much is the feasibility to perform these algorithms in reality. That is, we look at the asymptotic speedup, not the practical speedup.
There is a really good paper by people from the MS PQ team that looked at this. Highly recommended:
https://cacm.acm.org/magazines/2023/5/272276-disentangling-h...
My understanding is that any use of post-quantum crypto today is layered on top of existing crypto (so breaking one is insufficient to compromise the channel), in large part due to the relative immaturity of the field that you've mentioned.
The threat model here is not necessarily that we expect anyone to have sufficiently capable quantum computers (and/or algorithmic breakthroughs) in the immediate future, but that a potential adversary might store some encrypted comms that they can later decrypt. Perfect forward secrecy doesn't protect you against an algorithmic break.
https://en.m.wikipedia.org/wiki/Travelling_salesman_problem
Although faster quantum algorithms for the exact solution exist, I see no reason why this would result in "vastly" improved efficiency.
https://www.energy.gov/articles/doe-national-laboratory-make...
You can buy a quantum computer today. They are reality:
https://quantumzeitgeist.com/how-to-buy-a-quantum-computer/
They will likely only get better from here. Too early to take that promise to the bank, but human progress isn’t generally made by pessimists. To what level, we’ll see. They don’t call it the frontiers of innovation because of the security of outcome involved.
Public transportation is a public good and doesn’t need to be profitable. If it needed to be profitable we have a word for that: private transportation. Maglev trains are obscenely expensive to build and may never be profitable.
Brightline is showing that profitable high speed rail may be a commercial reality worth pursuing however. People bag on them, but they have already launched their first line and are working on their second. Tons of people betting against them and my goodness were there so many naysayers from day one, yet they are getting it done.
Also:
AI is a reality. That was science fiction.
Wearable computers are a reality. Dick Tracy stuff. Also science fiction.
Virtual reality is a reality. Also science fiction.
Electric cars were a fantasty that had so many headwinds and scaling problems they were called impractical, but now in just a decade or so they are commonplace.
Fully automated electronic pilots for both fixed wing and helicopters was science fiction just a few decades ago. Not autopilots but pilot replacements. Today: commercial reality.
Just in time factories with robots running the lines were science fiction until just a few decades ago. Now people use old ones for making art and many factories are deeply automated headed towards even greater automation.
Drones were also science fiction (the first cameras were on kites). Now they are so common we have to ban them from places.
Everyone dogs on the progress these days, especially big projects, but we keep making progress in big ways and the negativity is just unjustified. It’s just that the progress is adsorbed into society in such a way that people don’t realize how remarkable their every day things are.
https://en.m.wikipedia.org/wiki/Fusor
We are talking 4,5,6 orders of magnitude for several vital physical properties. Silicon scaling the last 40 years seems to me as being much easier - and that have required enormous amount of R&D including physical theory, and is bumping into physical limits. We have gone from say 500 nm to 5 nm, basically three orders of magnitude.
What makes it so clear that quantum computer technology are even possible to scale?
And yes, Quantum computers may be profoundly powerful someday, for a set of problems. Not in general.
My gut tells me they may never end up being very useful. something about the intrinsic downsides to any analog computer. which if you are not familiar, is that analog computer components must be far more precise than their digital counterparts.
If you really wanted to get pedantic you could call our everyday semiconductor based computers "quantum" as they operate on a distinctly quantum phenomena. However the term appears to be reserved for devices that are able to exploit analog quantum outcomes.
Counterpoint: some of the most interesting classical algorithms, such as transformer-based neural nets, appear to work well with far less precision than expected. For that matter, the first perceptrons were analog... and of course, so is the one that everybody is trying to emulate.
As a measure of signal-to-noise ratio, numerical precision in the classical domain may correspond to other attributes in other domains. It may not be a productive thing to focus on.
I've worked with analog computers, they were used in control systems. I understand that Moon landing used analog computers along digital ones as well.
Basically you can do PID (proportional, integrative, derivative) calculus on them using plain analog electronics. Very specialized and nothing to get overexcited about.
It's like calling these biological machinery "computers": https://en.wikipedia.org/wiki/File:Human_computers_-_Dryden....
Bottom line "quantum computing" has nothing to do with the classic field of digital computers (personal PCs), it's a stupid, deliberate misuse to borrow from the legitimacy and respectability of an established field.
The term should die in a fire. "quantum crap putting" is a lot more appropriate given all the crap they put in the headlines to fool the guillible.
There’s nothing special about Boolean logic as a way to solve problems that require, wait for it, computation of some sort.
(Or WILL BE when we build proper ones...)
David Deutsch formalized universal quantum computers -in analogy to a universal classical computers in the 80s.
The starting point is basically noticing the mismatch between the classical theories of computing and quantum physics.
From the abstract of 'Quantum theory, the Church-Turing principle and the universal quantum computer':
>It is argued that underlying the Church-Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the ‘universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it.
For one I don't think there's understood to be an implicit physical principle in Church-Turing thesis. The core idea of the thesis is that human thought can be modeled by a Turing-complete machine.
It is silly to say that the thesis implies an assertion that the classical(non-quantum) physical system popular at the time, now known to be flawed (and possibly inconsistent), could be simulated by a Turing-complete machine. What I'm trying to say is, if the best known physical system known by science could be wrong or flawed or inconsistent (and it always has been, we haven't cracked all the secrets of the physical universe yet), it seems silly to assert that some computing system could perfectly simulate it.
IMHO those ideas would be relevant only if there is evidence that human thought is capable of performing computation that cannot be simulated by a classical Turing machine because the human mind uses some features of the physical universe that the machine did not use. But on that front, AFAIK, classical computers can simulate quantum computers albeit with an exponential slowdown.
Arguably then the only concrete achievement of quantum computing to date has been improvements to classical algorithms. However, I fully expect that we will eventually have powerful quantum computers.
Practical applications for those are things like modelling chemical reactions or quantum systems, or optimisation.
No discussion on quantum computing would be complete without a link to Scott Aaronson's blog. Worth a read to get a better understanding of the subject.
https://scottaaronson.com/
As far as i can see there is quite a lot of "quantum safe" encryption so what kind of historical data exists lying around with lots of value?
In my opinion if breaking AES is to serve military (and hunt for secrets) then it would be done in secret.
I assume all the big nations spy on each other. Have a very good idea on the broad strokes total number of personnel, planes, ships, bombs, and where they are all located. Potential for novel military insight seems low.
There is probably lots of stupid human gossip to be found: mistresses, politically embarrassing failures, self-dealing schemes, etc. Maybe there are a few tantalizing useful nuggets: attached are the full schematics for the planetary weather control machine, where we buried that crashed ufo, location of the archive holding all the kompromat, etc.
I have no doubt intelligence agencies would decrypt anything and everything, but it seems more like they would just because vs perceived need.
I find this statement funny, not at your expense.
In public discourse, speak about quantum encryption too early – such as within the last five years – and the common opinion on say Stack Overflow/HN/Reddit/among the outer circles of cybersecurity is "don't model a threat before you get there".
Now apparently there is a lot of quantum-safe encryption - not true, NIST barely came to a standard in the last year, which failed quickly, even though there are quantum-resistant strategies which have gained tentative adoption in companies like Signal and MullvadVPN. But interesting that this is a perception someone has now, and suddenly quantum computers are being put under popular scrutiny again, perhaps driven by advancements in inner circles and higher tiers of tech.
It's tiresome to see these discourses out of sync
Symmetric encryption is safer, but you still need to double the key lengths at least.
Think of it as a control plane vs. data plane, where you have the state as a control plane, and if data can escape its purview, or worse the data plane can generate control messages that subvert it - you get existential uncertainty and risk. It will never let itself be reduced to a dumb pipe. Encryption represents a limit on the absolute sovereignty of that control plane, so the resources to contain it are a constant need.
However there are scientific scenarios where superpositions and qubits come into play. They can also decrypt any form cryptology faster than any conventional computer system. The problem is that they are not as energy efficient as a conventional system.
Even if/when these things are working on a useful scale, quantum computing is going to be more comparable to special-purpose accelerators like GPUs, or perhaps akin having a re-programmable physics lab-on-a-chip. It will be advantageous for the subset of problems that can be cast in the form of Schrodinger's equation, of which there are many. For example, you can use the quantum computer to generate high-fidelity solutions of the electronic structure of some classically intractable molecule, and use those solutions as the training set for a classical AI model that then goes and performs the bulk of the computation on whatever it was you were trying to do.
besides that, it's mostly quackery by pretending code to impossible low temperature calibration and sensors don't exist.
Not that there is anything really wrong with RSA...
Put differently, I assumed that factorization of a 3072 bit number has a higher security margin than discrete logarithm on a 256 bit point on a curve. Is that not so?
"Scott’s Supreme Quantum Supremacy FAQ" (2019) https://news.ycombinator.com/item?id=21053405 https://www.scottaaronson.com/blog/?p=4317
/? quantum supremacy 2024: https://www.google.com/search?q=quantum+supremacy+2024
/? practical quantum advantage: https://www.google.com/search?q=quantum+advantage
https://spectrum.ieee.org/quantum-computing-skeptics
Related HN discussion
https://news.ycombinator.com/item?id=38745970
But then again I'd say that it doesn't need to.
From a theoretical perspective QC improves our understanding of the physics of computation by bridging the gap between our classical theories of computation and our quantum theories of physics.
QC gives us access to "quantum observers" to allow us to take our understanding of what Quantum Physics "means" further.
QC lends some support to the many-worlds interpretation of Quantum Physics - Where else is the computation being done if we are retrieving answers from their interferences?
From a physical perspective we are learning a lot tackling the hard challenges of realizing them.
Even if we never build "practical" Quantum Computers, experimentally it would still be worth building them as physics experiments.
And if we can build real practical machines they might have significant advantages in some practical fields like quantum physics simulations.
* Unless somewhere the NSA (or their Chinese equivalent) are breaking cryptography using some moonshot machine.
Direct answer, QC's are shown to exist at some scale in our universe. They may not get larger than 1000 qbits, but they also might.
However so far the most practical thing that QC has done is inspire new classical algorithms for some problems, notably in recommendation.
Even if QC hasn't achieved anything tangible yet, the side effects of it looming are pushing things on.
Then, something I read to the effect that we need to stop thinking of QC as solving classical problems but solving different problems at least reassured me I wasn't too dumb to get it.
It most probably will never replace classical computers.