As a quantum physicist myself, this is a very good question. I remember going to a quantum control conference (a topic very relevant to quantum computing) a few years ago and there were a couple of quantum computing startups. I asked their engineers, what exactly are quantum computers useful for? They had no concrete ideas. I don't think the situation is much better today.
Now, I understand building quantum computers in research settings, even if just for the secondary theoretical and technological outcomes of learning how to build them (similar to how creating gravitational wave detectors led to a greater development of seismometers, quantum noise theory and techologies, control systems, etc.) However, I honestly can't wrap my head around the value proposition for companies to make these things. The only cases I can see is making them in order to sell to research groups who want to use them to implement quantum communication strategies and basic quantum simulations. On second thought, that might be enough, but it is a very small market.
I did not understand what real world computing use would quantum computers have over the current generation of compute in terms of architecture/efficiency or a measurable metric. Thanks for explaining.
The main benefit of quantum computers is that they're (in principle) very precisely controllable quantum systems. In a sense, if you do a "quantum simulation", it's actually physically real since you are actually working with the same quantum states and interactions you would have in the "real thing".
Apart from some strange cases (usually using quantum fourier transform, such as prime number factorisation) they are not good replacements for classical computers at all.
As I understand from Wikipedia there are four fundamental quantum algorithms that perform better in some way than the best-known classical counterparts, and many more algorithms in total. The four fundamental ones are:
* HHL algorithm for solving (sparse & insensitive) systems of linear equations
* Grover's search algorithm for determining black-box inputs
* Shor's algorithm for factoring primes
* Quantum fourier transforms
The above have various potential applications such as:
You should be very skeptical of all those applications except Shor.
HHL: Here's a quote from Ewin Tang [1]: "We know that quantum computers can “efficiently solve” high-dimensional linear algebra problems; however, this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself."
Grover's search: This is a speed-up from 2^n to 2^sqrt(n). Impressive, but there's not a lot of exp-time algorithms that people ever run. They go for heuristics instead.
Quantum fourier transforms: This is a tool, it's cool, but needs an application. I haven't seen a serious proposal for using it somewhere where a classical algorithm wouldn't do better.
> this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself
That's a fair point. I guess I was interpreting OP's question as "what can we do once we have engineered quantum computers", and would categorise this "harder problem" as an engineering problem.
> would categorise this "harder problem" as an engineering problem.
I'm not sure what your relation to the field is, but I have found that a lot of things that look like engineering problems from the outside, end up being theoretical and fundamental problems from within. This is often the case when I discuss quantum noise of gravitational wave detectors. I often see people say things like "I wouldn't want to be the guy who has to make these gravitational wave detectors less noisy", almost implying it's just a case of one guy sitting there turning some knobs, but in reality it's thousands of physicists coming up with entirely new theoretical frameworks, often discovering fundamental issues of quantum measurement and control theory (quantum non demolition measurements, quantum squeezing, back action evasion, etc.), or coming up with the most sensitive seismometers ever, or developing new mirror coatings, etc.
Everyone thought that Apple's cancelled wireless charger was just an engineering problem, but it turned out that it seems to be physically impossible to achieve what they wanted.
That said, perhaps in this case you are right, but it's not often obvious what is simply a matter of time and what requires whole new paradigms.
Again, a totally fair point. I just mean that when you posed the question "what exactly are quantum computers useful for?", I kind of assumed you meant an ideal quantum computer that had this kind of control over its state.
For reference I am out of my depth! My doctorate was in quantum information theory but I've been out of academia for many years now.
Yeah, I did mean that, and I stand by my opinion that even the ideal cases are not particularly compelling. I'm just also pointing out that the ideal case is not actually possible, even theoretically. There will also be decoherence, for example, and even the tomography of the state (i.e. actually measuring the state) is limited by fundamental quantum noise (e.g. ultimately the Heisenberg limit).
I guess it depends on what you find compelling. I'm not interested in finance. A lot of it just seems like moving money around to make wealthy people wealthier. But it does make sense that a lot of heads will perk up if there's a potential for speeding up market simulation models.
Also, just to add, 'quantumalgorithmszoo.org' is quite out of date: For example, they claim a polynomial speed-up for network flow, but that's based on the SOTA in 2007. These days, there's an almost-linear time classical algorithm [A], and no matching quantum algorithm (and also the idea that you would want to use a quantum computer to shave a factor n^(0.0001) is ridiculous). Now, all these statements are only about asymptotics, but don't get me started on practicalities: The idea that in the next 50 years you would use a quantum computer for any problem with only a polynomial speed-up is silly.
The most well known of those is Shor's algorithm and yet it's still extremely difficult to scale. The problem is that quantum computers, like any quantum system, are so difficult to control without introducing massive decoherence (EDIT: mixing with the environment and thus destroying any relevant "quantumness"), that they are almost impossible to scale.
It is indeed interesting that it's even theoretically possible to create quantum algorithms that are better than classical ones, but that doesn't mean it's practically useful. The latter is the relevant metric for bothering with "the assembly line". What you are talking about is still firmly within the realms of academia.
Investors are impatient, and talk of assembly lines and manufacturing signals to them that an actual product is near. I suspect it’s mostly smoke and mirrors to keep the funding flowing for a few more years.
5 years ago I was at MIT’s QC lab and 4 qubits was the max number of entangled qubits their machine could reach, sustainably. All the marketing fluff from IBM and Google about hundreds, or thousands, of entangled qubits is misleading - they don’t maintain those entangled states for long durations. Only when we can get hundreds of qubits to maintain entangled states for sustainable periods of time can we then attempt the theoretical use cases of the technology.
You’re right! The trapped ion approach (IonQ) is the most promising direction toward scalable quantum computing.
Superconducting qubits — such as those used by IBM and Google — require extreme cooling while ions can be trapped at room temperature.
Superconducting qubits are also plagued by substrate imperfections, while trapped ions — being “nature’s qubits” — are absolutely identical in their quantum mechanical properties. This allows trapped ion quantum computers to realize the best demonstrated gate fidelities.
I still need to be convinced that the exponential power of n qubits grows faster than the exponential complexity of aligning, programming and reading n qubits.
The imminent nonsense of fear-mongering and money wasting, mostly. Academic funds spent billions on PQC and academia has been paid to shill nonsense for long enough to convince some of these players to "ah, let's just integrate PQC, whatever". It's nothing more than a waste of money and resources.
Sorry, huh? Who's paying academia to shill? This is conspiracy thinking.
Changing cryptographic algorithms takes a long time - there are a lot of systems with this stuff embedded in them. Taking some modestly low-cost efforts _now_ to be prepared for a potentially "really bad" future event is more like buying insurance than anything else.
Is it a good choice? I dunno; I have no bets on the likelihood of a working crypto-breaking QC emerging in the next 30 years. But it's not really an irrational thing to worry about on a 10-30 year time horizon, and to simultaneously think that some of the computer systems we design and build today will still be running then.
That's a good question. I thought they are only using PQC for key exchange (which is referred to as Level 2) but they are not.
In the article, Apple explains why they choose to use Level 3:
> At Level 2, the application of post-quantum cryptography is limited to the initial key establishment, providing quantum security only if the conversation key material is never compromised. But today’s sophisticated adversaries already have incentives to compromise encryption keys, because doing so gives them the ability to decrypt messages protected by those keys for as long as the keys don’t change. To best protect end-to-end encrypted messaging, the post-quantum keys need to change on an ongoing basis to place an upper bound on how much of a conversation can be exposed by any single, point-in-time key compromise — both now and with future quantum computers. Therefore, we believe messaging protocols should go even further and attain Level 3 security, where post-quantum cryptography is used to secure both the initial key establishment and the ongoing message exchange, with the ability to rapidly and automatically restore the cryptographic security of a conversation even if a given key becomes compromised.
The main thing that changed "recently" is that NIST standardized ML-KEM (aka Kyber) for post-quantum cryptography, which was important for implementors. However, ML-KEM is still quite new, so it is mostly used in hybrid schemes with the "store-now-decrypt-later" threat in mind.
Other than that, I don't think anything fundamentally changed during the last 10-20 years.
I am very tired of this quantum computing nonsense. I have been hearing about it overtaking everything for almost 20 years (when I did my PhD). While the EU and the US has been pumping money into quantum for all these years, they completely missed the AI revolution, and have been chronically underfunding basic research (e.g. what I'm partial to, formal methods). You can still get tons of money from funding agencies by _somehow_ incorporating "quantum" into your funding proposal. It's a joke.
I remember being at the SAT conference 2 years ago (co-located with all other formal methods conferences), and I raised my concern about the BS that was accepted as a research paper again doing some nonsense quantum stuff, and the person from Intel was like, we are almost at 100 qbits, end of the year! Pinky Promise! Of course none of that happened. They promised 1000s of qbits in just a decade 20 years ago.
Best part is that even when they have 10s of thousands of qbits they can't show me a single, actually useful, revolutionary application other than breaking RSA, which is laughable (yada-yada some optimization problems, sorry, but no, the more you dig, the more it's obvious it is nonsense). Billions of EUR into this fever dream and they got completely blind-sided by deep learning (which they _also_ under-funded until industry picked it up and made it work). It's the same idiots who demoted Katalin Kario who recently got the Nobel recently for mRNA vaccines. I sometimes really get tired of Academia.
Quantum is absolutely over-hyped. But so are many "really exciting but far off" projects. And so is AI (he says, having gotten a lot of funding to work in machine learning systems).
But that doesn't mean that it's bad to continue funding research into it at some level, in the same way that we fund fusion research, and all-optical computing, etc. It's just a question about balance. Unlike, say, blockchain, we know there _are_ useful applications for a quantum computer; cryptography, as you noted, but also things like quantum chemistry, and possibly some optimization problems. But they're also quite far off and many require stable qbits way beyond what we can build today.
It's a shame that funding at some levels requires excessive hype. It's as much a condemnation of our science funding system as anything.
I’ve been a huge skeptic of this field for years. If anything, this summary makes me even more skeptical. The new innovations in laser grid isolated qubits sound amazing until you realize that many if not most (or all?) of those qubits aren’t actually functionally addressable in these systems.
Add to that the facts that error correction will clearly require exponentially more qubits than are programmable; power requirements for cooling or lasers are outlandish and unlikely to shrink significantly; and we don’t even have all that many particularly good quantum algorithms.
Worst of all, all the announcements for the past few years have been in the form of press releases talking about “plans” for new developments and “five year horizons”. Every academic article and new university QC lab is co-sponsored by a VC-funded corporation with every incentive to lie and mislead until a good exit point. This is not the behavior of a highly promising field.
I wish there were a big prize for the first quantum computer shown capable of factoring any product of two odd 4-bit primes {3,5,7,11,13} using Shor's algorithm. I do not expect such a prize to be won in the next decade. Or two.
35 comments
[ 2.1 ms ] story [ 75.3 ms ] threadNow, I understand building quantum computers in research settings, even if just for the secondary theoretical and technological outcomes of learning how to build them (similar to how creating gravitational wave detectors led to a greater development of seismometers, quantum noise theory and techologies, control systems, etc.) However, I honestly can't wrap my head around the value proposition for companies to make these things. The only cases I can see is making them in order to sell to research groups who want to use them to implement quantum communication strategies and basic quantum simulations. On second thought, that might be enough, but it is a very small market.
Apart from some strange cases (usually using quantum fourier transform, such as prime number factorisation) they are not good replacements for classical computers at all.
* HHL algorithm for solving (sparse & insensitive) systems of linear equations
* Grover's search algorithm for determining black-box inputs
* Shor's algorithm for factoring primes
* Quantum fourier transforms
The above have various potential applications such as:
* Deep learning [0]
* Finance [1]
* Solving large-dimensional differential equations [2]
* Solving constraint satisfaction problems [3]
I also came across a webpage called Quantum Algorithm Zoo [4] which looks like it answers your question in much more detail.
[0] https://arxiv.org/abs/1806.11463
[1] https://www.google.com/books/edition/Quantum_Machine_Learnin...
[2] https://arxiv.org/abs/1512.05903
[3] https://link.springer.com/article/10.1007/s002000050134
[4] https://quantumalgorithmzoo.org/
HHL: Here's a quote from Ewin Tang [1]: "We know that quantum computers can “efficiently solve” high-dimensional linear algebra problems; however, this assumes that we have some way to evolve a quantum system precisely according to input data, a much harder problem than the linear algebra itself."
[1] https://ewintang.com/blog/2019/01/28/an-overview-of-quantum-...
Grover's search: This is a speed-up from 2^n to 2^sqrt(n). Impressive, but there's not a lot of exp-time algorithms that people ever run. They go for heuristics instead.
Quantum fourier transforms: This is a tool, it's cool, but needs an application. I haven't seen a serious proposal for using it somewhere where a classical algorithm wouldn't do better.
That's a fair point. I guess I was interpreting OP's question as "what can we do once we have engineered quantum computers", and would categorise this "harder problem" as an engineering problem.
I'm not sure what your relation to the field is, but I have found that a lot of things that look like engineering problems from the outside, end up being theoretical and fundamental problems from within. This is often the case when I discuss quantum noise of gravitational wave detectors. I often see people say things like "I wouldn't want to be the guy who has to make these gravitational wave detectors less noisy", almost implying it's just a case of one guy sitting there turning some knobs, but in reality it's thousands of physicists coming up with entirely new theoretical frameworks, often discovering fundamental issues of quantum measurement and control theory (quantum non demolition measurements, quantum squeezing, back action evasion, etc.), or coming up with the most sensitive seismometers ever, or developing new mirror coatings, etc.
Everyone thought that Apple's cancelled wireless charger was just an engineering problem, but it turned out that it seems to be physically impossible to achieve what they wanted.
That said, perhaps in this case you are right, but it's not often obvious what is simply a matter of time and what requires whole new paradigms.
For reference I am out of my depth! My doctorate was in quantum information theory but I've been out of academia for many years now.
[A] https://www.quantamagazine.org/researchers-achieve-absurdly-...
It is indeed interesting that it's even theoretically possible to create quantum algorithms that are better than classical ones, but that doesn't mean it's practically useful. The latter is the relevant metric for bothering with "the assembly line". What you are talking about is still firmly within the realms of academia.
Changing cryptographic algorithms takes a long time - there are a lot of systems with this stuff embedded in them. Taking some modestly low-cost efforts _now_ to be prepared for a potentially "really bad" future event is more like buying insurance than anything else.
Is it a good choice? I dunno; I have no bets on the likelihood of a working crypto-breaking QC emerging in the next 30 years. But it's not really an irrational thing to worry about on a 10-30 year time horizon, and to simultaneously think that some of the computer systems we design and build today will still be running then.
Would it be a good idea for signal to double the key size?
In the article, Apple explains why they choose to use Level 3:
> At Level 2, the application of post-quantum cryptography is limited to the initial key establishment, providing quantum security only if the conversation key material is never compromised. But today’s sophisticated adversaries already have incentives to compromise encryption keys, because doing so gives them the ability to decrypt messages protected by those keys for as long as the keys don’t change. To best protect end-to-end encrypted messaging, the post-quantum keys need to change on an ongoing basis to place an upper bound on how much of a conversation can be exposed by any single, point-in-time key compromise — both now and with future quantum computers. Therefore, we believe messaging protocols should go even further and attain Level 3 security, where post-quantum cryptography is used to secure both the initial key establishment and the ongoing message exchange, with the ability to rapidly and automatically restore the cryptographic security of a conversation even if a given key becomes compromised.
Article link: https://security.apple.com/blog/imessage-pq3/
Other than that, I don't think anything fundamentally changed during the last 10-20 years.
I remember being at the SAT conference 2 years ago (co-located with all other formal methods conferences), and I raised my concern about the BS that was accepted as a research paper again doing some nonsense quantum stuff, and the person from Intel was like, we are almost at 100 qbits, end of the year! Pinky Promise! Of course none of that happened. They promised 1000s of qbits in just a decade 20 years ago.
Best part is that even when they have 10s of thousands of qbits they can't show me a single, actually useful, revolutionary application other than breaking RSA, which is laughable (yada-yada some optimization problems, sorry, but no, the more you dig, the more it's obvious it is nonsense). Billions of EUR into this fever dream and they got completely blind-sided by deep learning (which they _also_ under-funded until industry picked it up and made it work). It's the same idiots who demoted Katalin Kario who recently got the Nobel recently for mRNA vaccines. I sometimes really get tired of Academia.
But that doesn't mean that it's bad to continue funding research into it at some level, in the same way that we fund fusion research, and all-optical computing, etc. It's just a question about balance. Unlike, say, blockchain, we know there _are_ useful applications for a quantum computer; cryptography, as you noted, but also things like quantum chemistry, and possibly some optimization problems. But they're also quite far off and many require stable qbits way beyond what we can build today.
It's a shame that funding at some levels requires excessive hype. It's as much a condemnation of our science funding system as anything.
Add to that the facts that error correction will clearly require exponentially more qubits than are programmable; power requirements for cooling or lasers are outlandish and unlikely to shrink significantly; and we don’t even have all that many particularly good quantum algorithms.
Worst of all, all the announcements for the past few years have been in the form of press releases talking about “plans” for new developments and “five year horizons”. Every academic article and new university QC lab is co-sponsored by a VC-funded corporation with every incentive to lie and mislead until a good exit point. This is not the behavior of a highly promising field.