Applications of Quantum Algorithms

This is the fourth post in a series on quantum computing, which began with the following:

In the previous post, we explained the inner workings of a quantum computer and introduced quantum algorithms to take advantage of the properties of quantum mechanics and execute specific computations.

However, we glossed over how these algorithms can provide a quantum speedup. To understand this, we must first understand the type of problems that are well-suited for quantum computers.

Error Bounded Algorithms

As discussed before, Classical Computers store definite states; therefore, the computations result in deterministic outcomes: a problem may be solved by a direct series of steps (an algorithm) that, given a specific input, will produce a specific outcome. However, while Quantum Computers still must follow an algorithm, the results they produce will not be deterministic. The resulting quantum state will be the same for a given input quantum state; however, when the output quantum state is measured, this state collapses into a single definite state. This results in an algorithm that solves a problem with a probabilistic outcome.

Algorithms that correctly compute the answer to a problem in polynomial time up to some known error percentage belong to the Bounded-Error Probabilistic Polynomial Time (BPP) group. The majority of Quantum Algorithms we are interested in are Error Bound Algorithms. The reason is related to their ability to speed up certain tasks.

But why would we be interested in an answer that is not always correct? Well, some problems have a large time complexity such that exact answers are unfeasible to attain. However, if there are fast enough algorithms that may be run multiple times to provide enough confident answers, then it might be a better, or in some cases, the only approach.

General Structure of Quantum Algorithms

The Error Bounded Quantum Algorithms have an advantage over other algorithms in Quantum Computers as they can easily explore the space of all possible solutions easily with Quantum Computers through superposition and reach the correct answer through entanglement. In general, they follow this series of steps:

Encode input in some of the qubits

$|a\rangle \otimes |00\rangle$

Entangle the input data with the output qubits

$|a_{00}\rangle \otimes |00\rangle + |a_{01}\rangle\otimes |01\rangle + |a_{10}\rangle \otimes |10\rangle + |a_{11}\rangle \otimes |11\rangle$

Perform some computations and amplify the result of the computation we care about

$|b_{00}\rangle \otimes |00\rangle + |b_{01}\rangle\otimes |01\rangle + |b_{10}\rangle \otimes |10\rangle + |b_{11}\rangle \otimes |11\rangle$

Measure the qubits

$90\%:b_{00},f(00) \text{ } 5\%: b_{11}, f(01)$

The idea is the following: we first store the input we want to use for the computation. Then, we entangle the input data to the output to connect all the possible answers to specific states. After this, we execute the core of the algorithm to solve the problem; during this part, we can take advantage of the states being superposed to apply operations to multiple states at the same time. By choosing the correct algorithm and implementation, it is possible to obtain polynomial runtime (or even lower), and depending on the problem it might be faster than the classical algorithm. After this, there is the optional step of amplifying the states connected to the answer to increase its probability. Finally, we measure the qubits to obtain a result from the computation. This process is repeated many times in order to sample the distribution of the states which will inform us about the answer to a problem.

Some examples of algorithms that follow this structure are Grover’s search algorithm, Shor’s algorithm, and Variational Quantum Eigensolver.

Grover Search

The Grover Search Algorithm follows this structure the closest. From the previous post, we established that Grover search allows for searching in $O(\sqrt{n})$ time. To achieve this, the core procedure is made up of two main parts: the oracle and amplitude amplification. The oracle is a set of gates that marks the state of the item you are searching for, while the amplitude amplification rotates the state to increase the probability amplitude marked state. Applying these two processes one after the other is called a Grover Iteration. Mathematically, the Grover Iteration behaves like a rotation, so by executing multiple Grover Iterations, the superposition of states is rotated such that the state corresponding to the solution is maximized relative to the others.

Geometric Representation of a single Grover Iteration. $|s\rangle$ moves towards $|\omega\rangle$ by the rotation from Grover – Wikimedia

Geometric Representation of a single Grover Iteration. $|s\rangle$ moves towards $|\omega\rangle$ by the rotation from Grover – Wikimedia

Rising Applications

While the application of quantum computing is still an open research area, there have been current real-world problems that have been found to have solutions computable through Quantum Computing. The following is a list of areas that are utilizing quantum computing:

Molecular Chemistry and Condensed Matter Physics

Molecular chemistry investigates the unique characteristics resulting from a distinct atom composition and structure and its interactions with other compounds. Meanwhile, Condensed Matter Physics deals with matter’s macroscopic and microscopic properties. For some compounds, their behavior can be studied in the lab; however, this is not true for all cases. Given the choice, we would like to have the ability to simulate the behavior of one molecule and obtain its characteristics that may be useful for medicine or material science. However, simulating quantum mechanical interactions is computationally expensive because the computational cost grows exponentially as the complexity of the system increases. The idea of using Quantum Computers in this case stems from the fact that they have the ability to simulate these quantum systems efficiently. Currently, methods for determining the ground state energy and the dipole moment of simple molecules have been tested in real quantum computers with research being made into simulating more complex molecules and obtaining electronic properties.

Representation of a Quantum Simulator – IBM Quantum Research

Finance

In Finance, there are problems that require the tuning of lots of parameters. Some of these problems are portfolio optimization, option pricing, and market simulation. Portfolio optimization consists of selecting the best investment distribution according to certain constraints like risk minimization and expected return. Option pricing refers to the computation of the probability that an asset or action will produce some profit at a given point in time. And market simulation is the process of predicting the behavior of transactions in an economy. All these areas require a lot of insight from economic and social behaviors which become unfeasible to account for at the global level; therefore, some method of computation that can grasp these limits is required to improve the efficiency of these services. One of the ways this can be done is through the Quantum Approximate Optimization Algorithm (QAOA). This algorithm works similarly to the Variational Quantum Eigensolver but instead uses multiple cost matrices that contain the parameters and constraints that want to be optimized. The quantum advantage comes from the fast computation of the cost of the function for the different possible parameters through the power of superposition.

Representation of the QAOA Quantum Circuit where $H_C$ is the cost matrix

Representation of the QAOA Quantum Circuit where $H_C$ is the cost matrix

Artificial Intelligence

Artificial intelligence has increasingly become an area of computer science with high relevance due to its vast possibilities for application. With the success of ChatGPT and Dall-E, this is true now more than ever. This is why improvements in the computations of machine learning models are very desirable. Currently, quantum computing has proved to be useful by providing Neural Networks with a Quantum Node. The idea is to introduce a quantum layer into the neural network to create a quantum-classical neural network. By training the network through gradient descent, the quantum layer uses the same principle as in the Quantum Approximate Optimization Algorithm and optimizes the parameters of the quantum nodes/neurons in the layer. Then, the measurement result from the Quantum Algorithm is what is sent to the next layer. The advantage comes from the ability to add a stochastic layer that is efficiently computable and optimizable through QAOA.

All of these applications are still in development with more being researched and coming on the horizon. To test these growing uses, bigger and better Quantum Computers are needed. However, current Quantum Computers are still limited in their accuracy, each of them has different qubit interconnections, and certainly building and maintaining them is difficult. While cloud services for quantum computing have been growing in the past few years, it is an arduous task to develop these algorithms and use them without some tests that can verify the correctness of the algorithms or their implementation. That is why Quantum Computer Simulators are used to simulate the behavior of Quantum Computers in a Classical Computer and analyze its runtime. The last post of this series will tackle the use of a Quantum Computer Simulator such as the ArrayFire Quantum Simulator (AQS) for studying these algorithms.

References

Nielsen, M., & Chuang, I. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511976667

Intro to Quantum Mechanics and Use of Linear Algebra: A Modern Approach to Quantum Mechanics, John S. Townsend

Grover Search Algorithm: Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. ArXiv. /abs/quant-ph/9605043

How Quantum Computing Could Remake Chemistry? Jeannette M. Garcia. Scientific American. (2021). https://www.scientificamerican.com/article/how-quantum-computing-could-remake-chemistry/

Option Pricing using Quantum Computers. Nikitas Stamatopoulos et al. Quantum 4, 291 (2020). https://doi.org/10.22331/q-2020-07-06-291

Qiskit Textbook. IBM & Jupyter Book Community. Grover’s Algorithm (qiskit.org)

Quantum Simulator Image: Emerging quantum computing algorithms for quantum chemistry. IBM Quantum & IBM Research-Almaden. https://arxiv.org/pdf/2109.02873.pdf

QAOA Image: Zhou, L., Wang, S., Choi, S., Pichler, H., & Lukin, M.D. (2018). Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices. Physical Review X.

ArrayFire Quantum Simulator. https://github.com/arrayfire/afQuantumSim