3 ms·
Yes indeed. it's intriguing to consider problems in BQP that may not fall into NP. this opens up a world of possibilities and challenges our current understandi
by canvascritic 3y ago
Yes indeed. it's intriguing to consider problems in BQP that may not fall into NP. this opens up a world of possibilities and challenges our current understanding of computational complexity.
It suggests there are problems solvable by quantum computers that classical ones can't even verify the results of. This could lead to fascinating developments in fields like cryptography, where solutions could be found but not easily checked.
on the other, it raises questions about the practicality of quantum computing. if we can't verify a solution, how do we trust it?
Maybe we need to rethink our definitions of 'solving' and 'verifying'. after all, these concepts were developed with classical computing in mind.
But maybe this this is just a limitation or topological property of our current theoretical framework? Like we're trying to fit quantum computing into a model that just isn't equipped to handle it.
either way, it feels like we are on the cusp of a paradigm shift. Pretty exciting
Anyway interested to hear more thoughts on this
- heavenlyblue 3y agoYou can verify solutions given by quantum computers
- bawolff 3y agoI don't think that is known to be true (in polynomial time) for all problems solvable by a quantum computer (e.g. Fourier Sampling)