Algorithm Designed To Show the Benefit of Quantum Computers Finally Tested

 Quantum Computers  

For the first time, A 20-year-old algorithm that demonstrated the benefit of using quantum computers to solve certain problems has finally been run, and the results matched the predictions.

Quantum algorithms are expected to solve problems faster than their classical equivalents, but few have been tested experimentally. Now Mark Tame, from the University of KwaZulu-Natal in South Africa, and his team have used a prototype quantum computer to run the a version of Simon’s algorithm, and achieved the predicted results.

Related articles Andrea Morello Explains Moore's Law and Quantum Computers  Quantum Computer Wins Head-To-Head Test  Lawrence Krauss Explains Quantum Computing

First conceived by computer scientist Daniel Simon in 1994, provides instructions for a computer to determine whether a black box returns a discrete output for every possible input. Simon's was the first example of problem-solving software that quantum computers should be able to execute exponentially faster than conventional computers as the problem gets harder. the first algorithm predicted to run exponentially faster on a quantum computer than a classical one. Although Simon’s algorithm doesn’t have practical applications, it could provide a useful way to test the capabilities of future quantum computers.

"This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model."

Tame and collaborators ran a quantum version of this algorithm on an optical quantum computer, in which entangled photons served as qubits. Their setup, which utilizes a total of six qubits, solved Simon’s problem in three quarters of the steps that it would take a classical computer to solve the equivalent classical black box function. Assuming theoretical predictions about Simon’s algorithm’s performance are correct, this gain in efficiency will increase exponentially on computers with more qubits.

"This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model," claim Tame and his collaborators.

Their work is published in the journal Physical Review Letters.


SOURCE  Physics

By 33rd Square

Embed