AI proved a major quantum complexity conjecture. What does it mean?

If you bring in the additional possibilities associated with a quantum computer, however, you no longer have just classical bits and classical gates, but qubits and fundamentally quantum gates.

Therefore, there are also errors introduced, so that the fidelity of your quantum computer is never perfect.

However, for a wide variety of problems, it’s unclear how much of a speedup a quantum computer can get you versus a classical computer.

We’ve already talked about the P complexity class of problems: problems that can be solved in deterministic polynomial time.

What has been a longstanding conjecture — a conjecture that was widely thought to be true — has now been proven.