What makes a quantum algorithm actually quantum?

Quantum algorithms are step-by-step coded instructions that leverage quantum properties to handle computations. While it is possible to run classical algorithms on a quantum computer, the term "quantum algorithm" refers to algorithms that use distinctly quantum procedures, such as superposition or entanglement. Quantum algorithms are why quantum computers can significantly outperform classical computers in certain tasks.

Key areas where quantum algorithms are used include cryptography, quantum system modeling, search and optimization, factoring large numbers, and solving complex systems of linear equations. As quantum computing advances, researchers are actively exploring new quantum algorithms and applications across various domains, pushing the boundaries of what is computationally possible.

Key Quantum Algorithms

We will focus our discussion on two key quantum algorithms: Shor's algorithm to break cryptography and Grover's algorithm for search. Together, these two algorithms hint at the immense potential of quantum computing and are a key reason why so much research is being devoted to developing practical, large-scale quantum computers.

As quantum hardware continues to improve, we may see more and more quantum algorithms emerge that can solve previously intractable computational problems.

Shor’s Algorithm

Named after mathematician Peter Shor, this algorithm is, in theory, capable of efficiently solving the underlying mathematical problems associated with our current encryption system. These mathematical problems involve factoring large numbers, which has proven extremely challenging even for supercomputers' most advanced classical algorithms.

When Shor's algorithm is run on a quantum computer with millions of qubits, it can break the encryption systems and cryptography standards (RSA and ECC) upon which the security of our online world is built. A quantum computer running Shor's algorithm would only require about 100 seconds to factor RSA encryption, whereas classical supercomputers would take 1 billion years. These standards form the basis of our digital security infrastructure, protecting everything from personal emails and financial transactions to sensitive government communications. As a result, all the passwords, pins, and keys we use to safeguard our online data will be rendered useless in the face of a sufficiently advanced quantum computer armed with Shor's algorithm. Hackers, cybercriminals, and even hostile nation-states could gain access to sensitive information, leading to massive data breaches, financial losses, and compromised national security.

As quantum computers advance and scale up in terms of qubit count and stability, the threat posed by Shor's algorithm grows. Industry must begin to develop and implement new quantum-resistant encryption methods.

Grover’s Algorithm

This algorithm, named after its creator Lov Grover, is designed for quantum computers to speed up searching through unstructured or unsorted databases. Grover's algorithm provides a quadratic speedup compared to an exponential speedup from Shor's algorithm.

In a classical computing scenario, searching through an unsorted database becomes increasingly time-consuming as the size of the database grows (searching for an item takes, on average, N/2 queries, where N denotes the number of items in the list). This is because the computer must check each item one by one until it finds the desired result. Grover's algorithm can achieve this with roughly √N queries.

To put this into perspective, if you have a database with a million items, a classical computer would need to check, on average, 500,000 items to find the one you're looking for. With Grover's algorithm on a quantum computer, you would only need to check around 1,000 items - a speedup of 500 times!

This speedup could have significant implications for a variety of fields. In data science and machine learning, Grover's algorithm could enable much faster processing of large datasets. This could lead to quicker insights, more efficient algorithms, and the ability to work with even larger datasets than is currently possible.

Other Notable Quantum Algorithms

• Quantum Fourier Transform (QFT)

Discovered by cryptographer and mathematician Don Coppersmith, this algorithm is the fundamental building block for many quantum algorithms, such as Shor’s algorithm. The Quantum Fourier Transform (QFT) linearly transforms a quantum state into another quantum state (think superposition) that encodes the periodic patterns or phases of the original state. QFT is the quantum analog of the Discrete Fourier Transform (DFT), which disintegrates a signal into an aggregation of sinusoidal waves of different frequencies and amplitudes. Additionally, the Quantum Fourier Transform is exponentially faster than the classical Fourier transform. Like the DFT, major application areas of QFT include signal processing and data analysis.

• Quantum Phase Estimation (QPE)

Quantum Phase Estimation estimates the eigenvalues (or phases) of a unitary operator given its eigenstate. Initially introduced in 1995 by Alexei Kitaev, it is one of the most important quantum algorithms and is often used in conjunction with other algorithms like Shor’s algorithm and the Harrow-Hassidim-Lloyd (HHL) algorithm. QPE makes use of two quantum registers. The first register is used as what is called “counting qubits,” while the second register, which we want to estimate the phase (or eigenvalue) of, encodes the quantum state. Quantum Phase Estimation has many powerful applications, which include quantum physics and chemistry simulations, Hamiltonian simulation, entanglement spectroscopy, and entropy estimation.

• Variational Quantum Eigensolver (VQE)

The Variational Quantum Eigensolver is a hybrid quantum-classical algorithm originally proposed in 2014 by Alberto Peruzzo, Alán Aspuru-Guzik, and Jeremy O'Brien. It incorporates quantum computation with classical optimization techniques to find a quantum system's lowest energy state (or minima). Given the Hamiltonian of a system, VQE approximates the ground state of the system with a parameterized quantum circuit, known as “ansatz,” and then employs a classical optimizer to adjust the parameters of the ansatz. This process aims to minimize the expectation value of the Hamiltonian's energy, which is key to reaching the system’s ground state. VQE has applications in quantum chemistry, material science, and complex optimization problems.

• Quantum Approximate Optimization Algorithm (QAOA)

Quantum Approximate Optimization Algorithm is a quantum algorithm designed to find approximate solutions to combinatorial optimization problems on quantum computers. This algorithm was proposed in 2014 by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. To solve combinatorial optimization problems, QAOA finds the optimal or best possible solution iteratively from a finite set of approximate solutions, where evaluating each solution can be computationally intensive. It is similar to VQE, combining classical optimization with quantum circuits to solve these optimization problems. Some of the applications of QAOA are in graph theory and machine learning, and its potential applications include solving protein folding and energy optimization problems.

Quantum Algorithms Impact Across Industries

Quantum algorithms have many potential applications, which include cryptography and cybersecurity, drug discovery and molecular simulation, optimization problems, machine learning and artificial intelligence, and financial modeling and risk assessment.

As quantum hardware advances and becomes more accessible, the development of new quantum algorithms will likely accelerate. Researchers are actively exploring novel quantum algorithms and adapting classical algorithms to run on quantum computers. As more powerful quantum computers become available and quantum algorithms mature, we can expect to see increasingly significant applications and breakthroughs in the coming years.