Assessing the Effectiveness of Non-Turing Computing Paradigms

Abstract

In recent years the technological limits inherently present in the classical Turing paradigm of computation have sparked the development of innovative solutions based on quantum devices or analog-digital mixed approaches often based on the time evolution of differential equations. Such promising machinery require accurate analysis to understand if and how they will be able to perform better than classical approaches in solving hard optimization problems. Here we challenge two machines representative of the quantum annealing and differential equations approaches, namely D-Wave and Memcomputing by devising a benchmark of three well known hard optimization problems from the realms of number theory, optimal transport and optimal scheduling. We introduce the Mean First Solution Time, a novel metric for accurately comparing performances, and take as baseline the classical Gurobi solver. We show that performances of both solvers are heavily dependent on the selected set of internal parameters. Results shed lights on the advantages and current limits of each paradigm and give a perspective on possible future developments.

Keywords

• Factorization problem
• in-memory computation
• non-linear dynamical systems
• non-turing computation
• NP optimization problems
• optimal transport