Quantum-Computing-Inspired Algorithms in Machine Learning

Introduction

Quantum is a Latin word for amount and in modern understanding means the smallest possible discrete unit of any physical property such as energy, matter. The quantum science is often intimidating due to unfamiliarity with the discipline, even though it is the backbone of many of today’s major state-of-the-art technologies ranging from lasers to semiconductors devices. However, quantum computing is quickly gaining popularity and has found many applications in real time scenarios. Even though applying the ideologies of quantum mechanics to computer science may feel like a sophisticated task, the science has already moved past its theoretical stage as confirmed by the latest researches.

The exciting aspect of quantum computational intelligence is that its fundamentals integrate the principles of both computer science and quantum physics. As pointed out by Feynman, in the early eighties, simple simulations of quantum mechanics on a classical computer appear to require a simulation overhead which is exponential with respect to the size of the system and the simulated time.

Presently, computers in theory (Turing machines) as well as in practice (Personal Computers) are based on classical physics i.e. the state of ON or OFF. Nevertheless, as indicated by modern quantum physics, the world behaves quite differently i.e. between the states of ON and OFF.

And as such, quantum systems exhibit a superposition of various states lying in [0, 1], at any point of time, and exhibit the effects of interference during its evolution. Moreover, in quantum systems due to the theory of entanglement, a particle loses its individuality which results in remote effects. The discipline of quantum computation aims to investigate and enhance the computational power and other performance based aspects of computers based on quantum-mechanical principles. The idea is to obtain alternative quantum algorithms that give better computational results as opposed to classical solutions of the problem. Genetic quantum algorithms and their applications in combinatorial optimisation problems is discussed in (Han and Kim, 2000). A study of cognitive radio decision engine based on quantum genetic algorithm is discussed in (Zhao, Zheng and Shang, 2007).

Instead of storing information as 0s or 1s as done in conventional computers, a quantum computer stores the information as qubits which can store the state of 0 or 1 or a superposition of both at the same time. The fast and powerful quantum computation has been realized by various quantum effects such as quantum superposition, entanglement and quantum tunnelling enabling quantum computers to examine and exploit the fusion of qubits concurrently which do not necessarily follow the binary nature of computing.

While conventional computers encode information into bits and can only perform discrete binary calculations, quantum computers use as spin directions of electrons or polarization orientations of a photon to encode information. These quantum-mechanical states might represent a 1 or a 0, or combination of both or a value lying somewhere in between 1 and 0. The edge that a quantum computer has over a classical computer is that it can perform arbitrary reversible computations on a set of numbers simultaneously, which is impossible for a classical computer. It also has the ability to produce interference between various states. This interference property helps a quantum computer to outperform a classical computer of same size. Although a quantum computer uses only a single processing unit, it can perform numerous operations in parallel. The approach adopted by quantum computing is entirely dissimilar to that of classical computing. A map connecting various locations is an appropriate analogy for explaining this dissimilarity. As an example, solving optimization problems can be thought of as trying to find the shortest distance between two locations. Every possible solution is mapped to this distance, and the cost of travelling that path is the cost of the solution for the problem. The aim is to find an optimal solution which gives the least cost of traversing the corresponding path. Classical computers employing classical algorithms can only “walk over this map”. Quantum computers on the other hand can tunnel through the map making it faster to find the shortest path.

The D-Wave processor used by quantum computers helps in finding the cheapest solution among all possible optimal solutions. The computation is much faster than in case of a classical computer and provides a vast number of optimal solutions. This gives the user the optimal solutions along with various alternative solutions.