Software key in Quantum vs. Classical

Computer scientists have now shown that the right software will allow classical computers to perform at the same pace as their still-mostly-theoretical qubit-laden counterparts.

Computer scientists have now shown that the right software will allow classical computers to perform at the same pace as their still-mostly-theoretical qubit-laden counterparts.

Fortunately for the qubit, the findings published in Communications of the ACM only apply to a very particular set of problems:

The potential strength of quantum computers lies in their ability to compute in parallel, allowing them to tackle problems that would be insurmountable to classical computers that would have to make the same number of computations in sequence, such as a brute-force attack on an encryption algorithm.

However, in work designed to investigate the relative computability of quantum vs. classical interactive proof systems, the researchers developed an algorithm that approached the issue using parallel processes.

The algorithm showed that, for this set of problems, there was little to no advantage in using a quantum computer, or as MIT's Associate Professor Scott Aaronson puts it: "Instead of demonstrating the power of interactive proofs, the authors had to show that quantum interactive proofs were weak enough to be simulated using polynomial memory".

More in his commentary on the research the Communications of the ACM here.