How quantum algorithms solve problems that classical computers can’t

Subject: Science and Tech

Section: Awareness in IT

Context:

We often hear that quantum computers efficiently solve problems that are very difficult to solve with a classical computer. But even if the hardware is available to build a quantum computer, exploiting its quantum features requires us to write smart algorithms.
An algorithm is a sequence of logically connected mathematical steps that solve a problem.

Quantum v. classical algorithms:

An algorithm is a series of steps to find the solution of the targeted problem.
A quantum algorithm is also a series of steps, but its implementation requires quantum gates.
- Some problems may need fewer steps on the part of a quantum algorithm than the number of steps required by a classical algorithm. That is, the quantum algorithm can speed up the computation.
One factor that controls this speed-up is the possibility of superposition of the states of quantum bits, or qubits, that encode information.
Whereas a classical computer uses semiconductor-based gadgets as bits to encode information, quantum computers use qubits. In both cases, the bit or the qubit can have two distinct states, 0 or 1; but qubits have the additional ability to be partly 0 and partly 1 at the same time.

Shor’s algorithm:

One of the earliest quantum algorithms is the factorisation algorithm developed by Peter Shor. It requires fewer steps to factorise a number than one that operates with classical principles.
The efficiency of an algorithm is related to the number of steps required as the size of the input increases. An algorithm is more efficient if it requires fewer steps (and thus less time). Thus, Shor’s algorithm is far more efficient than any known classical algorithm for factorisation.
Modern cryptography – which is used to secure user accounts on the internet – depends on the fact that there are no efficient classical algorithms that can factorise large integers. This is the source of the claim that the availability of quantum computers will challenge the safety of classical cryptography.

Grover’s and Deutsch-Jozsa algorithms:

Another popular quantum algorithm is the quantum search algorithm developed by Lov Grover.
- For every 100x increase in the list’s size, Grover’s algorithm will need only 10x more steps. This is the kind of speed-up this quantum algorithm achieves.
another quantum algorithm that showcases the exponential speed-up is the Deutsch-Jozsa algorithm.
Scientists already know of more quantum algorithms that can solve problems in optimisation, drug design, and pattern search, among other fields more efficiently.

Term related to quantum computing:

Qbits: A qubit or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device.
Entanglement: It refers to the phenomenon in which two or more quantum particles can become correlated in such a way that their states are intrinsically linked, regardless of the distance between them. This correlation is stronger than any classical correlation and is described by a mathematical concept known as a quantum state.
Superposition: Superposition is the ability of a quantum system to be in multiple states at the same time until it is measured. Because the concept is difficult to understand, this essential principle of quantum mechanics is often illustrated by an experiment carried out in 1801 by the English physicist, Thomas Young.

Source: TH