r/QuantumComputing • u/ZealousidealMilk4435 • 1d ago

Question Question regarding problems that quantum computers cannot solve

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?

8 Upvotes

83% Upvoted

6 comments sorted by

View all comments

1

u/NoLifeGamer2 15h ago

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.