How much faster will quantum computers be ? For more energy efficient industry and accelerated AI

Quantum computers offer “only” an n^2/3 black-box speedup over classical computers, rather than a square-root speedup.

A paper (Quantum lower bounds for the collision and the element distinctness problems) proves that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function Omega((n/r)^{1/3}) times, where n is the size of the domain and r|n. This improves the previous best lower bound of Omega((n/r)^{1/5}) evaluations due to Aaronson [quant-ph/0111102], and is tight up to a constant factor. Our result also implies a quantum lower bound of Omega(n^{2/3}) queries to the inputs for the element distinctness problem, which is to determine whether or not the given n real numbers are distinct.

The exponential speed-up of Shor’s quantum algorithm for integer factorization over the best known classical algorithm has inspired scientists of many fields to explore the power of quantum computing. On the other hand, understanding the limitations of quantum computing is also of great importance. Identifying problems that are hard for quantum computers can not only deepen our knowledge on the power of quantum computing, but is also necessary for developing a new cryptography immune to quantum cryptanalysis.

Θ(p^n/r) evaluations are sufficient and necessary for classical algorithms to solve the r-to-one Collision. Quantum computers can do much better: using Grover’s quantum search algorithm in a novel way, the quantum algorithm found by Brassard, Høyer, and Tapp makes only O(n/r)^1/3


evaluations. Despite much research effort, no lower bound better than constant had been found until very recently, when Aaronson proved the ground-breaking
Ω(n/r)^1/5

lower bound. In this paper, we improve the lower bound to the tight bound.

What could be done with faster than classical computers ?

Simulation and optimization

Another particularly difficult class of problems is the simulation and optimization of complex systems (specifically, systems where complexity scales with 2n). This is a very broad class of problems, but can be roughly conceptualized as a system where n-number of multifaceted things all interact with one another, producing many possible outcomes and variants.

Better catalyst design can make more energy efficient industry. In particular fertilizer production

A tangible example of a problem in this category is the simulation of molecular interactions. Modeling how complex compounds interact at a molecular level is notoriously difficult to do on classical computers, but should be achievable with the use of quantum computers. This could herald breakthroughs in materials science, biology, chemistry, medicine and a host of other fields.

Simulating complex molecular interactions will not only enhance our understanding of existing compounds, but will enable us to analyze hypothetical compounds in a safe, simulated environment, unlocking new frontiers by exponentially increasing the scope of what can be modeled and therefore tested and discovered. This type of simulation could be particularly useful for catalyst design. Some of industry’s most important processes rely on catalyst-enhanced reactions. One example is the Haber-Bosch process, which is at the center of virtually all modern fertilizer production. Unfortunately, this chemical reaction process is extremely energy and resource consumptive. If a new, more efficient catalyst could be designed, massive amounts of energy and resources could be conserved, thereby increasing the efficiency and productivity of the global food supply.

Artificial intelligence

Quantum computing could also enable significant breakthroughs in artificial intelligence (AI) and machine learning. By simultaneously processing all combinations of inputs in a massively parallel fashion, and by taking advantage of a property dubbed “quantum tunneling,” quantum computing can tackle extraordinarily complex data challenges (such as discrete optimization of large datasets and complex topologies) that would otherwise be intractable on classical hardware (which, today, forces practitioners to rely on imperfect heuristic techniques).

The potential applications for quantum computers in the field of artificial intelligence are so compelling that NASA has a research team dedicated specifically to quantum AI. The team is aimed at demonstrating that quantum computing and quantum algorithms may someday dramatically improve the ability of computers to solve difficult optimization and machine learning problems.