2 ms·
Quantum Luddite here. So much of quantum computing is theory, and so much of current crypto is applied. Is it realistic to think the first applied quantum com
by mvkel 3y ago
Quantum Luddite here.
So much of quantum computing is theory, and so much of current crypto is applied.
Is it realistic to think the first applied quantum computers could quickly get us to a P=NP solution, rendering all crypto effectively irrelevant?
- foota 3y agoQuantum computers are only tangentially related to P=NP, in that some problems in NP may have solutions that are polynomial time on quantum computers, but this says nothing about the rest of them. This class of problems is know as BQP. Is is possible, but unknown, that all problems in NP may belong to BQP, which would imply that a sufficiently large quantum computer could solve all problems in NP in polynomial time, but even then it would be possible that P does not equal NP, since P and NP are about classical computers.