[Summary] The Grover search algorithm, which is one of the famous quantum algorithms, has already been discussed in the articles below, so I will not explain its meaning or solution in detail here.
In this article, we will review flipping the sign of probability amplitude and inversion about the mean value. Also includes execution results on the latest IBM quantum computer (127 qubits). The following discussion is based on knowledge gained from reference [1].
●Grover's algorithm quantum circuit
Here we consider the case of 2 qubits (number of qubits n = 2). In addition, one more qubit is used for control. The quantum circuit is shown in Fig.1. For all qubits, we apply a Hadamard gate to create a uniform superposition state as an initial state. Next, configure Oracle F for the target function f. The bit string xy with f(xy)=1 is what is searched. Now, the target is set to xy=10. The function of this Oracle F is to flip the sign of the probability amplitude of the basis |10> corresponding to this target. The probability amplitude of other basis is not changed.
The next gate A inverts the four basis probability amplitudes of the top 2 qubits system about the mean of their values. As a result, only the probability amplitude whose sign was flipped in the preceding Oracle is amplified, and the others are attenuated. By repeating Gate F and Gate A as a set, a specific basis can be measured with a high probability (approximately close to 1.0). That's what you're looking for. This repetition needs to be performed only once when n=2.
●Amplitude Amplification Matrix
Now, if we multiply matrix A shown in the upper right corner of Fig. 1 (diagonal elements are -1 and other elements are 1) by the ket vector whose elements are probability amplitudes', the probability amplitudes will certainly be amplified. We can understand that. This is detailed in Chapter 9 of Reference [1]. But how did we derive this matrix? This is explained using Fig.2. Although we will deal with the case of n=2 here, it will be easier to understand if we consider the general case of n. In short, it takes advantage of the fact that the result of inverting the value p of an element around the average value m of all elements is 2m-p.
●Execution on the IBM Quantum 127 qubits real machine
After making the above preparations, execute the quantum circuit shown in Fig.3. The Oracle F circuit was configured for f(10)=1. Also, the amplitude amplification section (purple Amp gate) that inverts about the average value can be configured with Hadamard gates, X gates, and controlled X gates, but it is also possible to just give the unitary matrix A shown in Fig.2. The latter seems easier to think about.
The execution results are shown in Fig.4. These are the execution results of (a) ibm_lagos with a 7-qubits Falcon processor, (b) ibm_brisbane with a 127-qubits Eagle processor, and (c) ibmq_qsam simulator. First, by the simulator (c), the basis of the target was measured with a probability of 1.0, as in theory.
On the other hand, the error rate of the machine (a)lagos was relatively high, and the target basis was measured with a probability of 0.75, and other basis were also measured slightly. However, with the latest model (b) brisbane, the target basis probability has improved to 0.87. Enough information was obtained to find the desired solution.
●Impressions
Until last year, IBM provided general users with real machines with 5-qubits and 7-qubits for free, but recently they have also made the latest machine with 127-qubits available for free. In fact, in April 2023, there was news [2] that "The University of Tokyo will be the first university outside of North America to install an IBM Eagle 127 quantum bits computer.'' Only half a year later, anyone could use this (presumably) same quantum computer over the web, as mentioned above. Amazing progress in quantum computers!
In principle, 127 qubits have the potential to simultaneously process a huge number of states: 2 to the 127th power (= 10 to the 38th power). Such a machine can now be used from home via the web, so although there are still many challenges to overcome, the dream is growing.
●Words from Prof. Chris Bernhardt
==============================
Dear Fujio,
Another great post! Your site contains really useful information.
I especially like the fact that you are showing how to do things on the IBM quantum computer.
Chris
==============================
Dear Chris
Thank you very much for reading my blog article.
My introductory quantum computing journey has come to an end.
I was able to achieve this by coming across your wonderful book and fully understanding its contents.
Based on this, I can move on to even higher levels of quantum computing.
Fujio
==============================
References
[1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.
[2] News about the introduction of IBM's 127 qubit computer to the University of Tokyo
