How can quantum computing help artificial intelligence

Artificial intelligence (AI) is becoming one of the key industry trends after decades of being only a dream for researchers. From conversations with Alexa and Siri to autonomous driving in vehicles from Waymo (Google) and Tesla, OpenAI's GPT-3 writing prose like a human, and DeepMind's (Google) AlphaZero beating human chess masters, it is becoming increasingly clear that AI is now mature enough to solve real-life problems, and often faster and better than humans, faster and better.

Elsewhere in the technology industry, some visionaries are working to develop quantum computers that attempt to harness the properties of quantum physics to perform calculations far faster than today's computers.

So what exactly does quantum computing have to do with artificial intelligence?

01Algorithmic complexity is the hidden enemy

Algorithmic complexity is a somewhat obscure mathematical concept that connects the ongoing work of AI researchers and quantum computing pioneers.

Spanning the fields of mathematics and computer science, computational complexity theory focuses on classifying computational problems based on resource usage, such as space (memory) and time. Essentially, a computational problem is a task that can be solved by a computer mechanically following the mathematical steps defined in an algorithm.

For example, consider sorting the numbers in a list. One possible algorithm, called "selection sorting", consists of repeatedly finding the smallest element (in ascending order) from the unsorted part of the list (initially all of them) and placing it at the beginning. This algorithm effectively maintains two sublists of the original list as it works: the sorted part and the remaining unsorted part. After several such processes, the result is a sorted list from smallest to largest. In terms of time complexity, this can be expressed in terms of the complexity of N2, where N denotes the size or number of elements in the list. Mathematicians have come up with more efficient, albeit more complex, sorting algorithms, such as the sorting algorithms Cube Sort or Tim Sort, both of which have a complexity of N x log(N). Sorting a list of 100 elements is a simple task for today's computers, but sorting a list of 1 billion records may not be so simple. Therefore, the time complexity (or the number of steps in the algorithm with respect to the size of the input problem) is very important.

To solve a problem faster, one can use a faster computer or find a more efficient algorithm that requires fewer operations, which is what is meant by lower time complexity. However, it is clear that in problems of exponential complexity (e.g., N2 or 2N), for such larger problem sizes, it is not practical to simply use a faster computer: this is exactly what happens in the field of artificial intelligence.

02Artificial intelligence needs to solve highly complex problems

First, we will look at the computational complexity of the artificial neural networks used by today's artificial intelligence (AI) systems. These mathematical models are inspired by the biological neural networks that make up the brains of animals. They "learn" to recognize or categorize input data by seeing many examples. They are collections of interconnected nodes or neurons that, in combination with activation functions, determine the output based on the data presented in the "input layer" and the weights of the interconnections.

In order to adjust the weights in the interconnections so that the "output" is useful or correct, the network can be "trained" by exposing it to many data examples and "back-propagating" the output losses.

For a neural network with N inputs and M hidden layers, where the ith hidden layer contains mi hidden neurons and k output neurons, the time complexity of the algorithm for adjusting the weights of all neurons (called the back-propagation algorithm) is.

02Can quantum computing effectively solve these problems?

Quantum computers are machines that use the properties of quantum physics, particularly superposition and entanglement, to store data and perform computations. They are expected to be able to perform billions of operations simultaneously, and thus provide a very substantial speed boost for highly complex problems, including artificial intelligence.

While classical computers transmit information in bits (short for "binary numbers"), quantum computers use quantum bits (short for "quantum bits"). A quantum bit is considered to have a probability distribution, for example, it can be 70% 1 and 30% 0. This is what makes quantum computers so special.

There are two fundamental properties of quantum mechanics that quantum computers exploit: superposition and entanglement.

Quantum computing and classical computing deal with information differently in nature.

When a quantum bit is both 1 and 0, it is said to be in a superposition state. Superposition is a general term for the situation when a system is in multiple states at the same time and presents only one state when it is measured. If we pretend that a coin is a quantum object, then a superposition state can be imposed when the coin is tossed: there is only one probability that the coin will be heads or tails. Once the coin lands, we have made a measurement, and we know whether the coin is heads or tails. Similarly, only when we measure the spin of an electron (similar to a coin falling to the ground) do we know what state the electron is in, whether it is 1 or 0.

Quantum particles in a superposition state are only useful if we have more than one. This brings us to the second fundamental principle of quantum mechanics: entanglement. Two (or more) particles that are entangled together cannot be described individually; their properties depend entirely on each other. So, entangled quantum bits can affect each other; the probability distribution of one quantum bit (whether it is 1 or 0) depends on the probability distribution of all other quantum bits in the system.

Because of this, adding each new quantum bit to a system doubles the number of states that a computer can analyze. This exponential increase in computer power contrasts with classical computing, which only scales linearly with each new bit.

Theoretically, entangled quantum bits could perform billions of operations simultaneously. Clearly, this capability would provide a tremendous speedup for any algorithm with complexity in the N2, 2N or NN range.

03Preparing for quantum-driven artificial intelligence

Due to the impressive potential of quantum computing, while hardware teams continue to work to make these systems a reality (the largest to date is IBM's 127-bit Eagle system), software researchers are already working on new algorithms that can take advantage of this "simultaneous computing" capability in cryptography, chemistry, materials science The new algorithms are used in areas such as cryptography, chemistry, materials science, systems optimization and machine learning/AI. It is believed that shor's factorization quantum algorithm will provide exponential speedups over classical computers, posing a risk to current cryptographic algorithms.

Most interestingly, it is believed that quantum linear algebra will provide a polynomial speedup, which will greatly improve the performance of our artificial neural networks. Google has launched TensorFlow Quantum, a software framework for quantum machine learning that allows rapid prototyping of hybrid quantum-classical ML models. IBM, also a leader in quantum computing, recently announced that it has discovered a "mathematical proof" of the quantum benefits of quantum machine learning ". However, while companies like IBM and Google are vertically integrated (and thus developing both hardware systems and software algorithms), there is also a very interesting group of quantum software startups, including Zapata, Riverlane, 1Qbit, and to some extent Quantinuum (which, since Cambridge Quantum Computing merged with Honeywell and changed its name, is no longer is a pure software company), just to name a few.

As quantum hardware becomes more powerful, and quantum machine learning algorithms are refined, quantum computing is likely to take an increasingly important share of the AI chip market.

Reference link：

https://www.verdict.co.uk/what-has-quantum-computing-got-to-do-with-ai/