TECHNICAL NOTE
Why are Quantum Computers so Powerful? - Another reason
In the first half of the explanatory article, "How Can Quantum Computers Have Such Powerful Computational Capabilities?" was explained in terms of exponential memory.
In the second half of this article, I will focus on and explain another factor that makes quantum computers so powerful:
massively parallel algorithms.
I have for a long time said that quantum computer algorithms are a "bringing to the spotlight."
I will explain the heart of this in the following.
REASON
LOGIC
Combinatorial optimization solved on a classical (conventional) computer - Solved in a straightforward manner
Consider solving a combinatorial optimization problem on a classical computer. When one tries to solve the problem in a straightforward manner, one tries to find the true solution by trying all possible solutions one by one and covering all patterns. This is not much of a problem when the total number of patterns is still small. What is troublesome is that the number of patterns increases exponentially in relation to the size of the problem when the size of the system to be handled grows.
A typical example of such a problem is the NP-hard problem, which will be explained in another article. Typical NP-hard problems include the traveling salesman problem, the knapsack problem, and the Maxcut problem.
In the following, we introduce the relatively simple Maxcut problem to give you an idea of what we mean.
Now, what happens if we attack these NP-hard problems exhaustively with all patterns in the correct way of classical computers? Since there are patterns as per exponential function, the computation time will be exponential in relation to the system size.
A very simple but tough problem: Maxcut problem
We now consider a loading scheme in which five kindergartners are placed on two buses (we will call them "bus 0" and "bus 1").
Here, the five kindergartners are in pairs that dislike each other, as shown in the figure.
Now, we want to put these five on two buses, but we want to put them on the buses so that they do not hate each other as much as possible. What is the best way to put them on the bus? This is a very simple question. However, this problem of deciding the best way to put people on the bus is actually known as a very difficult problem to solve.
It is called the "Maxcut problem" because it involves separating people who dislike each other as much as possible.
Now, how many ways are there to put five school children on a bus, completely ignoring their likes and dislikes?
The answer is 2^5=32, which is not a big deal if there are only 32 ways. We can check up all the patterns and find the best way to put them on the bus. However, the problem is that it is impossible to check all the 2^1000 ways when the number of users increases from 5 to 10, 100, or 1,000. This means that the computational cost increases exponentially as the system size increases.
Once again, solving Maxcut problems with a classical computer
The loading of two buses with N kindergartners can actually be represented by an N-bit sequence. If we put Kid A's bus number (0 or 1), Kid B's bus number (0 or 1), and Kid C's bus number (0 or 1) … in a row, we can see that indeed a bit sequence consisting of N number sequences (we will call it 'N-bit sequence') is equivalent to the bus loading of N kindergartners. Now, to solve this kindergartner problem in a straightforward manner on a classical computer, we need to generate N-bit strings of different input states one after another, and then use the computer to calculate the degree to which we succeeded in tearing apart the bad matching pairs for each of the input states.
Then, after performing the calculation on all N-bit string combinations, we check which was the best bus ride that tore apart the most unfriendly pairs. This is the flow of solving the Maxcut problem on a classical computer. And as the system size (number of kindergartners) increases, the computational cost (you can think of it as computation time) increases exponentially
STRUCTURE
Quantum computer algorithms are an "unveiling a right solution"
-massively parallel algorithm
Above, we saw that there are some problems that take exponentially longer to solve with a classical computer. So how does a quantum computer solve such problems? The way a quantum computer solves a problem is completely different from that of a classical computer. I have always said that the way a quantum computer solves a problem is equivalent to a "unveiling a right answer," and I would like to explain how this is so. First of all, the most important thing to understand about the algorithm of a quantum computer is that it can use "quantum superposition states". Let's use the Maxcut problem described above to illustrate this. Different input states of an N-bit sequence are generated one after another as input states, and calculations are performed sequentially on each N-bit sequence with a classical computer. On the other hand, a qubit can create a superposition of input states, so it is possible to create a single state by superposing all of these input states. This is the decisive difference from a classical computer. In a quantum computer, a series of operations (this is called an "algorithm") are performed on this single superposition of all possible alternatives. The algorithm is designed to attenuate the amplitude of the solution states other than the correct answer, leaving only the correct answer among the various possible solutions that have been inputted and superimposed. This is exactly how the correct solution is "unveiling a right answer". In this way, the algorithm of a quantum computer is completely different from that of a classical computer. Therefore, an algorithm that is good on a classical computer is not necessarily a good algorithm on a quantum computer. In the same way, an excellent algorithm for a quantum computer is not necessarily good for a classical computer. I would like you to note this. How to use a quantum computer is an important piece of know-how.
Quantum Computer Algorithms " Unveiling "
Generalize the discussion above. That is, in the N-bit case, we compare classical bits and qubits. When it's N-classic bit, the story is simple. One of 2^N states |0...00>, |0...01>, ..., |1...11> It will be. Qubits, on the other hand, are a very different story. For N qubits, the superposition state of 2^N states |0...00>, |0...01>, ..., |1...11> can take. That is, α_{0...00}|0...00> + α_{0...01}|0...01> + ... + α_{1...11}|1.. .11> where |α_{0...00}|^2 is the probability that |0...00> state is observed, |α_{0...01}|^2 is |0...01> The probability that a state is observed, and so on. With N classical bits, the calculation proceeds in the form of what to do with the number string in the ket symbol. On the other hand, in a quantum computer, you do not manipulate the contents of the ket symbol, but the coefficients in front of it. This is because you can obtain a huge degree of freedom of 2^N . By freely substituting numbers for the coefficients, we can obtain a memory that can input 2^N pieces of information.
