# Quantum Algorithms

### What is a Quantum Algorithm?

Quantum computers use quantum algorithms to outperform traditional computers and they can solve some problems significantly faster than classical algorithms.

They're a set of instructions that tell a quantum computer how to manipulate qubits in a specific way to solve a problem faster than any classical computer could.

Cryptography, search and optimization, quantum system modeling, and solving huge systems of linear equations are all areas where quantum methods can be used.

### Grover's Algorithm

Grover's algorithm is a quantum algorithm for searching an unsorted database.

Grover's algorithm can also be used for estimating the mean and median of a set of numbers, and for solving the collision problem. In addition, it can be used to solve NP-complete problems by performing exhaustive searches over the set of possible solutions.

### Shor's Algorithm

Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer.

Shor’s algorithm only gives the right answer 50% of the time. RSA and ECC are vulnerable to attacks by quantum computers.

As RSA relies on the hard problem of factoring numbers.

Multiplying two prime numbers together is easy, but taking a large number and factoring it in to get those two prime numbers is difficult.

Shor’s algorithm can find the prime factors of a number and can ”undo” this factoring problem much more easily than a classical computer.

However, it would take about 10 million physical and 10,000 logical qubit quantum computers would be needed to break an RSA key.

Considering Google's quantum supremacy claim was achieved with only 53 qubits, it's safe to say that we are still pretty far away from that.

Last updated