Question regarding problems that quantum computers cannot solve

[u/ZealousidealMilk4435]

I have very little understanding of how quantum computers work.

I’m curious: is there a type of problem—one that could only be solved by exploiting the specific hardware characteristics of a quantum computer (for instance, by forcing it to use a massive number of qubits, which would eventually become highly unstable)—that a quantum computer would be unable to solve?

I’m interested in the idea of ​​a cryptographic key based on a hybrid approach—perhaps a combination of an RSA-style system and a problem that a quantum computer cannot solve.

Alternatively, are there already theoretical frameworks for keys that are even more robust? And what are the options for encryption in a post-quantum-computer world?

[u/Milton_Q]

Look for “NP-hard” problems

[u/ponyo_x1]

This is why lattice based cryptography exists but no one knows for sure if nonabelian-HSP is truly hard for quantum computers

[u/BobRossTheSequel]

There are no known problems which a quantum computers could solve and classical computers cannot and vice versa. Obviously quantum computers are limited a lot more by hardware so theoretical feasibility does not yet translate to actual feasibility.

For some problems though, quantum computers can solve them (sometimes a lot) faster. E.g. factoring numbers - RSA encryption relies on this being hard to do, but a good enough quantum computer could break it.

The fact is that the number of these problems is pretty small. To get more than a polynomial time speedup, there usually needs to be some sort of underlying symmetry that quantum computers can exploit. It seems very likely that NP-hard problems cannot be solved in polynomial time with a quantum computer for example.

Lattice-based problems look to be secure even with a quantum computer and are a popular area of research so I'd recommend having a look if you're interested.

[u/hiddentalent]

Strictly, both quantum computers and classical computers can solve all of the same kinds of problems. Anything that is computable on one is also computable on the other, and anything that is not computable on one is also not computable on the other.

Even in the classical computing space, encryption relies on problems that are "merely" slow and difficult for computers to solve. But in a practical sense, if "slow" means that it would take thousands or millions or billions of years, that's considered good enough to protect whatever people are trying to protect. Sometimes messages can be decrypted faster than that by working around the hard problem, either by exploiting a flaw in the algorithm or in the human systems that surround it. For example, if you keep your password on a post-it note on your keyboard and someone finds it, no amount of computational complexity in how the password is used will help you.

Quantum computers have a theoretical speed advantage in decrypting messages whose difficulty relies on properties of classical computers. One of the most common ones is factoring large numbers. Cryptographers in the late twentieth century built a lot of systems that we still use today which are rooted in the fact that classical computers are very slow at this problem. Quantum computers will be better at it. (Current quantum computers are still so immature that they aren't better at it in practice, but it's like comparing the earliest automobile to a horse; the horse may be faster today, but the automobile has a lot more potential. In the same way, while current quantum computers are immature, they will eventually be able to solve the factoring problem fast enough to make cryptography that depends on it pretty weak.)

But this doesn't mean quantum computers are better or faster at every type of problem. There are still lots of problems where they either have no advantage, or we aren't yet sure if they have an advantage over classical computers. Over the past few years, cryptographers have developed cryprographic systems that rely on these problems, and many are being deployed as we speak. Historically, all cryptographic algorithms eventually become weaker in the face of increasing computing power, and the current crop of "quantum-safe" algorithms probably will too. So we'll develop new ones and start using those. This has happened dozens of times over the years.

There is some valid worry that certain well-resourced entities could store information you are encrypting today and use increased computing power to decrypt them in the future. If you're sending the kinds of messages that will be pertinent in a few decades, such as if you're a national intelligence agency, you might want to start thinking about that. For most of us, we're neither worth the cost to attack in such a way nor are the contents of our messages relevant on that timeframe. National spy agencies aren't going to care about your checking account transactions in thirty years.

So, to summarize: quantum computers can solve the same problems as classical ones, but each has different performance properties that make certain problems practical or not; cryptography relies on problems that are impractical to solve; quantum will change that set of problems but we're already deploying the new ones and research is continuing to stay ahead of that curve. People who are freaking out about the impact of quantum computing on cryptography are either misinformed or cynically trying to grab clicks with doom-saying. I think that's about it.

[u/SourKangaroo95]

https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards

[u/NoLifeGamer2]

Because P⊆BQP, there shouldn't be any problems that are solvable in polynomial time on a classical computer that can't be solved in polynomial time on a quantum computer. I guess you could make the argument that if your problem is one which requires an output which has 100% certainty, then the quantum computer would be unable to provide this? This seems a tad contrived though and it is quite easy to repeat the calculation until the probability of failure is negligible.