Quantum Computing Algorithms for Artificial Intelligence

Key Equations of Quantum Computing

The foundation of quantum computing is the three basic theories of quantum mechanics:  the Non-Relativistic Time-Independent Schrodinger Equation, Relativistic many-fermion systems (the many-body Dirac equation), and Gauge field theories (quantum Yang-Mills theories).

The Schrodinger equation is the basis for non-relativistic wave equation used in one version of quantum computing to describe the behavior of a quantum particle (electron, photon or ion) in a field of force. There is the time dependent equation used for describing progressive waves, applicable to the motion of free particles. And the time independent form of this equation used for describing standing waves.

Components of Quantum Computing

Quantum computing has five key components: control and manipulation of the isolated quantum particles, measurement of the parameters of the quantum particles, error correction, quantum algorithms and scaling up for large scale implementation.

There are three approaches to quantum computing: Quantum Annealing (QA),  Adiabatic quantum computation (AQC) and Gate-based quantum computing (GQC). Here, we will focus mostly on quantum annealing implementation of the algorithms. In the book Quantum Computing algorithms for Artificial Intelligence these approaches are discussed in details.

Quantum Annealing:

Quantum annealing is the set of meta-heuristic algorithms of quantum computing based on the concepts of quantum superposition, entanglement and tunneling. Quantum wave-functions and Quantum coherence are the key elements of quantum annealing.   The idea of Quantum Annealing is an offspring of the traditional thermal simulated annealing process, where the problem of minimizing a certain cost or energy function in a large space of configurations is solved, through a statistical mechanics analogy, by the introduction of an artificial temperature variable which is slowly reduced to zero in the course of a Monte Carlo simulation or Molecular Dynamics simulation. This device allows to explore the configuration space avoiding trapping into local minima, often providing a more effective and less biased search for the minimal “energy” than standard gradient-based minimization methods. 

D-Wave Systems Inc. manufactures quantum annealing processor chips that exploit quantum properties to realize QA computations in hardware. When supercooled to temperatures below 20mK (very near absolute zero), the chips are able to exploit quantum properties to carry out their computations.

Adiabatic Quantum Computation:

Adiabatic quantum computation (AQC) is an alternative to the quantum gate model. It deeply involved with the quantum complexity theory and the Bose- Eisenstein condensed matter of physics. The (AQC) system is slowly evolved from the ground state of a simple initial Hamiltonian to a final Hamiltonian that encodes a computational problem. The Hamiltonian is the sum of the kinetic energies of all the particles, plus the potential energy of the particles associated with the system. A key challenge in adiabatic quantum computing is to construct a device that is capable of encoding Hamiltonians problem that are non-stoquastic.  The entanglement between stationary spin qubits and propagating photon qubits are the main concept of implementing adiabatic quantum computational models.

Quantum Monte Carlo and Quantum Annealing

Quantum Monte Carlo methods have been very prominent in computer simulation of various systems in physics, chemistry, biology, business, philosophy and materials science. In the process of Quantum Monte Carlo (QMC), the annealing take place in the fictitious “time” represented by the number of Monte Carlo steps.  Here the quantum particles like photons, electrons and ions are directly represented as particles, instead of as a fluid. Quantum Monte Carlo can provide properties of exact solutions to Schr€odinger’s equation for Bose ground states.

There are two components in Monte Carlo simulation one is a constant directional movement derived from past data, and another is the random input. It rely on repeated random sampling to obtain numerical results. By generating an arbitrary number of simulations, one can assess the probability that the result will follow a given trajectory. A number of variations of QMC algorithms are available today. Reptation quantum Monte Carlo (RQMC), Self-healing Diffusion Monte Carlo (SHDMC) and  Fermion Monte Carlo (FMC) algorithms are most popular.

Quantum Monte Carlo Tree Search for Artificial Intelligence

The main engine behind the success of modern artificial intelligence (e.g. AlphaGo etc.)  is the algorithms that combines deep machine learning approaches with the technique called Monte Carlo tree search. In Quantum Monte Carlo Tree Search (QMCTS) the algorithm searches for possible solutions and records the results in a search tree. As more searches are performed, the tree grows larger with more accurate predictions.

In QMCTS the policy and the value functions are evaluated through quantum tunneling. In QMCTS, the quantum adaptive multi-stage sampling simulation optimization algorithm are used for estimating value functions through finite-horizon Quantum Markov decision processes (QMDPs). In our models of QMCTS, we first use Quantum Upper Confidence Bounds (QUCBs) for Quantum Monte Carlo simulation-based solution of Quantum Markov decision processes. There are four main stages of our Quantum Monte Carlo Tree Search algorithm are: selection, expansion, simulation and backpropagation. Quantum selection and quantum backpropgation are key algorithms of our QMCTS framework.

Here, the quantum annealing begins with the tree search simultaneously occupying many branches thanks to the quantum phenomenon of superposition. The probability of being at any given branch smoothly evolves as annealing progresses, with the probability increasing around the branches of optimal value functions. Quantum tunneling allows the search to pass through many branches simultaneously—rather than be forced to climb one branch after another —reducing the chance of becoming trapped in branches that are not the global optimum.

Travelling Salesman Problem and Quantum Annealing

Quantum annealing is a set of meta-heuristic algorithms based on quantum computing concepts of quantum superposition, entanglement and tunneling. These are used for finding the global optimal solution of a given value function over a given set of candidate solutions, by a process using quantum fluctuations.

Travelling salesman problem (TSP) consists in finding the shortest route connecting them, visiting each city once and returning to the starting point. The literature on TSP is vast. Here, for the time being, you can think of a real life travelling salesman problem, where one the salesman tries to find out the shortest route when travelling between a number of cities. If we want to compute the best route with simple trial and error techniques on a classical computer it would take longer than the age of the universe by the time you were up to 30 cities, even the best algorithms for exactly solving it must take a super-polynomial amount of time.

However, using quantum annealing you can define the problem as an optimization task. Bounded error in polynomial time is one of the key obstacle of developing effective quantum algorithm for travelling salesman problem.  Here, all points on the landscape of total travel space are examined simultaneously to determine the minimum distance route. Essentially each result is sampled from a Boltzmann distribution space. Given N cities with set inter-city distances d_ij, TSP consists in finding the shortest route connecting them, visiting each city once and returning to the starting point. Quantum tunneling allows the traveler to pass through many cities simultaneously—rather than be forced to move one city after another —reducing the chance of becoming trapped in the routes that are not the global optimum.  The route that minimize the sum of the kinetic energies of all the quantum particles, plus the potential energy of the quantum particles associated with the system.

Quantum Search Algorithms

Algorithms such as Deutsch’s algorithm, Deutsch-Jozsa algorithm, Bernstein-Vazirani algorithm, Simon algorithm, Shor’s algorithm are the first algorithms which made use of quantum superposition to perform a certain task sufficiently faster than classical computer. However, Peter Shor showed that it is possible for a quantum algorithm to compute factorization in polynomial-time. L. K. Grover, on the other hand, showed that it is possible to search for a single target item in an unsorted database.

The Grover search algorithm provides a powerful method for quantum computers to perform searches. It is an optimal search algorithm for a quantum computer. The Grover search algorithm has four stages: initialization, oracle, amplification, and measurement. The initialization stage creates an equal superposition of all states. The oracle stage marks the solution(s) by flipping the sign of that state’s amplitude. The amplification stage performs a reflection about the mean, thus increasing the amplitude of the marked state. Finally, the algorithm output is measured.

Quantum Computing Algorithms for Gradient Descent

Suppose you are at the top of a mountain, and you have to reach a valley or lake which is at the lowest point of the mountain. Gradient Descent is an optimization algorithm used for finding the minimum value of a function. It moves along the function with steps proportional to the negative of the gradient. In artificial intelligence, common algorithms such as regression, support vectors machines, and neural networks rely on optimization. Often in these cases the objective function to minimize is a least-squares loss or error function. In real life situation the objective functions are often non-convex with multiple minimum value.

In classical framework the algorithms seek the lowest valley by placing the traveler at some point in the landscape and allowing the traveler to move based on local variations.  While it is generally most efficient to move downhill and avoid climbing hills that are too high, such classical algorithms are prone to leading the traveler into nearby valleys and thereby settled at local minimum rather than the global minimum. To get the global minimum, numerous trials are typically required, with many travelers beginning their journeys from different points.

However, in quantum computing the quantum algorithms begin with the traveler simultaneously occupying many coordinates by utilizing the properties of superposition. The probability of being at any given coordinate smoothly evolves as annealing progresses, with the probability increasing around the coordinates of deep valleys. Quantum tunneling allows the traveler to pass through hills—rather than be forced to climb them—reducing the chance of becoming trapped in valleys that are not the global minimum. Quantum entanglement further improves the outcome by allowing the traveler to discover correlations between the coordinates that lead to deep valleys.

Our quantum gradient decent algorithms uses vectors as quantum states, which leads to exponential improvements in terms of the dimension. The quantum processing unit considers all the possibilities simultaneously to determine the lowest energy required to form those relationships. The solutions are values that correspond to the optimal configurations of qubits found, or the lowest points in the energy landscape. These values are returned to the user program over the network.

Conclusion:

Here we explained the concepts of quantum annealing, Quantum Monte Carlo Tree Search, quantum algorithms for traveling salesman problem and Quantum algorithms for gradient descent problems. Regardless of the answer, quantum computers are expected to have a significant advantage of finding optimal tours for TSPs quickly.  In our subsequent articles we will explain the concepts of quantum deep learning (QDL) and quantum reinforcement learning (QRL) in depth.

Source Books:

1. Compassionate Super-Intelligence AI 5.0 By Dr. Amit Ray, 2018
2. Quantum Computing Algorithms for Artificial Intelligence By Dr. Amit Ray, 2018

Read More ..

Spin-orbit Coupling Qubits for Quantum Computing and AI

References:

Synopsis: Traveling with a Quantum Salesman, Michael Schirber,  Physical Review A, March 2017.