Quantum algorithms plays a critical role in exploiting the full potential of quantum computing systems in AI, machine learning, big data science, and optimisation

Rajesh Uppal January 21, 2023 AI & IT, Quantum Comments Off on Quantum algorithms plays a critical role in exploiting the full potential of quantum computing systems in AI, machine learning, big data science, and optimisation 133 Views

Quantum technology (QT) applies quantum mechanical properties such as quantum entanglement, quantum superposition, and No-cloning theorem to quantum systems such as atoms, ions, electrons, photons, or molecules. Quantum bit is the basic unit of quantum information. Whereas in a classical system, a bit is either in one state or the another. However, quantum qubits can exist in large number of states simultaneously, property called Superposition. Quantum entanglement is a phenomenon where entangled particles can stay connected in the sense that the actions performed on one of the particles affects the other no matter what’s the distance between them. No-cloning theorem tells us that quantum information (qubit) cannot be copied.

Quantum technology has many Quantum applications, one of the major class is Quantum computation and simulation. Quantum computers shall bring the power of massive parallel processing, the equivalent of a supercomputer to a single chip. They can simultaneously consider different possible solutions to a problem and quickly converge on the correct solution without checking each possibility individually. This dramatically speeds up certain calculations, such as number factoring.

The power of quantum computers depends on the number of qubits and their quality measured by coherence, and gate fidelity. Qubit is very fragile, can be disrupted by things like tiny changes in temperature or very slight vibrations. Coherence measures the time during which quantum information is preserved. The gate fidelity uses distance from ideal gate to decide how noisy a quantum gate is.

We are now in era of Noisy intermediate-scale quantum (NISQ) in which quantum computers are composed of hundreds of noisy qubits that are not error-corrected. They Physical qubits are realized using superconducting Josephson junction qubits and the trapped-ion qubits. Other promising Qubits are Semiconductor based qubits; Topological qubits; and Photonic qubits.

Calculations using these noisy qubits can introduce errors and make long computations impossible. However, these computers still can demonstrate the advantages of quantum computing and various algorithms are being developed in disciplines such as machine learning, quantum chemistry and optimization.

For future fault-tolerant quantum computers Researchers have devised error-correction schemes such as surface code, that store data redundantly with information spread over tens of thousands of entangled physical qubits. These combined bits are collectively known as a logical qubit or perfect qubit. Previous research has found that a quantum computer with 300 perfect qubits could perform more calculations in an instant than there are atoms in the universe.

There is another kind of Quantum computer Analogue quantum computer, that performs “quantum annealing”. This computer can find the global minimum of a complicated mathematical expressions exponentially faster than a classical computer hence useful in optimization and sorting problems. Prime example is D-Wave which has a 5000-qubit system and is planning a 7000-qubit system.

Another type of quantum computer is quantum simulator which is a non-programmable quantum circuit and built for single purpose. Quantum simulator is used to reproduce the behavior of other quantum systems that generally are less accessible.

Quantum Algorithms

Since the quantum computers works differently than classical computers therefore, they require different software approach and different quantum algorithms. In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation.

A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each step can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

Quantum algorithms are usually described, in the commonly used circuit model of quantum computation, by a quantum circuit which acts on some input qubits and terminates with a measurement. A quantum circuit consists of simple quantum gates which act on at most a fixed number of qubits. The number of qubits has to be fixed because a changing number of qubits implies non-unitary evolution. Quantum algorithms may also be stated in other models of quantum computation, such as the Hamiltonian oracle model.

The design of quantum algorithms follows completely different principles from those of classical algorithms. To begin with, even classical algorithms have to be cast in a special form—as reversible algorithms—before they can be run on a quantum computer. Algorithms that achieve quantum speedups use certain quantum algorithmic paradigms or building blocks that have no classical counterparts.

In both the classical and quantum settings, we measure runtime by the number of elementary operations used by an algorithm. In the case of quantum computation, this can be measured using the quantum circuit model, where a quantum circuit is a sequence of elementary quantum operations called quantum gates, each applied to a small number of qubits (quantum bits). To compare the performance of algorithms, we use computer science style notation O(f(n)), which should be interpreted as ‘asymptotically upper-bounded by f(n)’.

Quantum algorithms that can be programmed include:

Algebra and number theory algorithms, such as factoring and Gauss sums
Approximations and simulations, such as quantum simulation, zeta functions, and knot invariants
Machine learning algorithms, such as clustering, binary classification, and training neural networks

One of the famous algorithms is Shor’s algorithm that perform integer factorization in polynomial time compared to exponential time taken by best classical algorithm. Another One is the Grover’s algorithm, which offers quadratic speedup in database searching. Quantum software development kits and computational platforms have been developed to help end users develop and test their quantum algorithms.

Classification of Quantum Algorithms

Quantum algorithms can be categorized by the main techniques used by the algorithm. Some commonly used techniques/ideas in quantum algorithms include phase kick-back, phase estimation, the quantum Fourier transform, quantum walks, amplitude amplification and topological quantum field theory.

Quantum algorithms may also be grouped by the type of problem solved. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. They can be used for scheduling, managing resource tasks, process optimization, predictive analytics and improving security planning. Monte Carlo quantum methods can be used for portfolio management and technical analysis in financial firms.

For example, Mklas encryption, Merkle hash, three signatures, Merkle-Hellman knapsack encryption and Bushman Williams classmate encryption are the new quantum cryptographic algorithms.

Algorithms based on the quantum Fourier transform

The quantum Fourier transform is the quantum analogue of the discrete Fourier transform, and is used in several quantum algorithms. The Hadamard transform is also an example of a quantum Fourier transform over an n-dimensional vector space over the field F2. The quantum Fourier transform can be efficiently implemented on a quantum computer using only a polynomial number of quantum gates.

The quantum phase estimation algorithm is used to determine the eigenphase of an eigenvector of a unitary gate given a quantum state proportional to the eigenvector and access to the gate. The algorithm is frequently used as a subroutine in other algorithms.

Quantum Approximate Optimization Algorithm (QAOA), quantum classifiers, quantum-generated adversarial networks, quantum neural networks and quantum simulated annealing are additional popular techniques based on quantum algorithms.

Search and optimization

One of the most basic problems in computer science is unstructured search.

Grover’s algorithm can speed up an unstructured search problem quadratically, but its uses extend beyond that; it can serve as a general trick or subroutine to obtain quadratic run time improvements for a variety of other algorithms. This is called the amplitude amplification trick

An interesting future direction for quantum algorithms is finding accurate approximate solutions to optimisation problems.

Quantum Walks

There are also quantum walks equivalent to the Markov chain and Markov walks. In classical computer science the concept of the random walk or Markov chain is a powerful algorithmic tool, and is often applied to search and sampling problems. Quantum walks provide a similarly powerful and general framework for designing fast quantum algorithms. Just as a random walk algorithm is based on the simulated motion of a particle moving randomly within some underlying graph structure, a quantum walk is based on the simulated coherent quantum evolution of a particle moving on a graph.

Looking ahead to the future, there’s a lot to come. New areas like generative quantum machines and quantum machine learning are evolving. In quantum machine learning, hybrid quantum algorithms based on quantum Boltzmann machine, quantum random access memory and QRAM concepts are being researched. New algorithms can be used for image processing, object tracking and other use cases for optical character recognition (OCR), intelligent character recognition (ICR) and so on. In the quantum world, quantum NLP, quantum computer vision and quantum RAM are evolving.

Quantum AI has algorithms similar to AI and will have a prefix of “quantum” attached to the same name as techniques from AI. For example, while you have support vector machines (SVMs) in AI, quantum AI has quantum SVMs. This is also the case with quantum classification, quantum cryptography, quantum simulated annealing and quantum k-nearest neighbor (KNN).

Quantum perceptron is like a neural network-based perceptron. If you look at a classical perceptron, you can process N dimensions of data. With quantum perceptron, you can process two to four dimensions.