Blog: Software [using classical computing] Said to Match Quantum Computing Speed

Software Said to Match Quantum Computing Speed
IDG News Service (12/23/10) Joab Jackson

University of Waterloo researchers have shown that for some computing problems, using the right software algorithms could enable classical computing techniques to work just as well as quantum computing. The researchers demonstrated how a seldom-used algorithm could achieve new levels in problem-solving performance when used on contemporary computers and theoretically match quantum computing speeds. "One striking implication of this characterization is that it implies quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems," according to the paper. Massachusetts Institute of Technology professor Scott Aaronson and colleagues recently proved that quantum interactive proof systems are just as difficult to solve as classical interactive proof systems, by using the matrix multiplicative weights update method to devise a new algorithm. The algorithm provides a method for solving problems using parallel processes, matching the efficiency of quantum computing. The researchers illustrated that "for a certain class of semi-definite programs you can get not the exact answer but a very good approximate answer, using a very small amount of memory," Aaronson says.

View Full Article