# Algorithms¶

## Complexity classes¶

## Overview¶

*Quantum algorithms: an overview*[94]an extensive list in Quantum Algorithm Zoo [M19]

a review about

*Variational Quantum Algorithms*[R7]Define oracles…

see also about the

*expressiveness*of**parametrized quantum circuit**(PQC)*ansatzes*[M4]Examples described in this section

## Pure Quantum Algorithms¶

“Pure” quantum in contrast to hybrid quantum-classical algorithms, they require **error-correction**.

### Shor¶

The Shor algorithm describes a way to break the RSA public-key cryptosystem in polynomial time. It uses Quantum Fourier transform and Phase estimation, which both are general building blocks for quantum algorithms.

Application: Breaking RSA

### Grover¶

- Grover, the
*quantum search algorithm*, incl.**Amplitude amplification**“Having a phone book (sorted by name), find the name corresponding to a given phone number”.classical: \(O(N)\)quantum: \(O(\sqrt{N})\) - Grover algorithm is optimal [16]:“relative to an oracle chosen uniformly at random, with probability 1, the class NP cannot be solved on a quantum Turing machine in time \(o(2^{n/2})\)”“recent work of Grover shows how to accept the class NP relative to any oracle on a quantum computer in time \(O(2^{n/2})\).”
An approaching to TSP and SAT using Grover’s

*quantum search algorithm*:- How the quantum search algorithm works [M25], about the traveling salesperson problem (TSP):“consider a variation on TSP, namely, searching for a route shorter than some specified threshold distance, \(T\).”
- “While it doesn’t make sense to use Grover’s algorithm on 3-sat problems, the techniques here can be applied to the more general case (k-SAT, discussed in the next section) for which Grover’s algorithm can outperform the best classical algorithm.”

### HHL¶

*Solving Linear Systems of Equations* [54]

“We consider the case where one doesn’t need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x.”

Application: Classical Physics

Qiskit tutorial: Solving Linear Systems of Equations using HHL [M39]

See also

*Hybrid quantum linear equation algorithm*[77]

## Variational Quantum Algorithms¶

Hybrid quantum-classical algorithms, they are designed to work also on **NISQ** hardware
and tolerate some amount of noise. The classical part is an optimization task.

### QAOA¶

Application: Combinatorial Optimization

Qiskit tutorial: Solving combinatorial optimization problems using QAOA [M39]

### VQE¶

Application: Quantum Chemistry.

Qiskit tutorial: Simulating Molecules using VQE [M39]

## Quantum Advantage¶

For **estimations of the required hardware** and
**claims of quantum advantage**,
see Quantum Advantage in the
State of the Art section.