3 ms·
If we have quantum computers, then isn't P vs. NP the wrong question? With quantum computers, the more relevant problem to study should be BQP versus QMA (the
by greeneggs 12y ago
If we have quantum computers, then isn't P vs. NP the wrong question? With quantum computers, the more relevant problem to study should be BQP versus QMA (the quantum analogs of P and NP/MA, i.e., computable versus verifiable in polynomial time on a quantum computer). Are complexity theorists studying the wrong problem?