Quantum algorithm

from Wikipedia, the free encyclopedia

A quantum algorithm is an algorithm that can be executed on quantum computers . Unlike analytical algorithms, quantum algorithms, which are probabilistic algorithms , do not produce unambiguous results, but rather indicate probabilities for certain results. Repeated application of the algorithm can make the error probability as small as desired. If the initial probability of success is high enough, a few repetitions are sufficient.

Entangled states of quanta are used for the calculation , in which different, simultaneously existing quantum mechanical states of the subsystems overlap . The variables of the algorithms are stored in qubits .

Categories

The algorithms found so far for quantum computers can be roughly divided into three categories:

  • Algorithms based on the quantum Fourier transform . This also includes the most famous algorithm for quantum computers, the Shor algorithm for factoring large integers , which plays an important role in prime number decomposition in cryptography . The time required is polynomial in terms of the number of digits. In contrast to this, the best currently known classical algorithm, the number field sieve , superpolynomial (but subexponential) requires a lot of time. The importance of Shors' algorithm is based on the fact that the security of asymmetric encryption methods such as RSA is based on the fact that no sufficiently efficient classical algorithms for factoring large numbers are known.
  • Quantum search algorithms. These include the Grover algorithm and variants thereof. It is used for an efficient search in an unsorted array. In the worst case, a normal computer has to look at all entries (i.e. compare) for entries, so this problem can classically be solved in computing steps. On a quantum computer, the Grover algorithm can do this in just operations. This limit is sharp, that is, no quantum algorithm can solve this problem in ( asymptotically ) fewer operations. It follows from this that, in general, no exponential speed advantage can be expected when using quantum algorithms.
  • Quantum simulation. In order to simulate quantum mechanical systems, it makes sense to use quantum mechanical systems again. Any Hamiltonian can be represented with a suitable set of quantum gates in a quantum circuit . Algorithms of this kind would allow the simulation of molecules in quantum chemistry , for which rough approximations are required with today's means.

Examples

Well-known examples of a quantum algorithm are the Deutsch algorithm or its extension, the Deutsch-Jozsa algorithm , which are not of great practical use, but as the first quantum algorithms worked faster than classical algorithms and thus made the potential of quantum computers clear.

literature

  • Jozef Gruska : Quantum Computing , McGraw-Hill, 1999
  • Matthias Homeister: Understanding Quantum Computing: Basics - Applications - Perspectives , Springer-Verlag, 2015, ISBN 978-3658104559

Web links