Try solving 3-SAT using Qiskit's Quantum Algorithms Module

[Summary] Grover's algorithm circuit and its implementation have already been described in this article. One of the challenges was generating an oracle according to the search target. When the number of qubits was 2 or 3, it was possible to create it through trial and error, but as the number of qubits increases, it becomes difficult. Therefore, Qiskit provides the Quantum Algorithms Module[1]. This includes Grover. It consists of PhaseOracle, which generates oracles for phase inversion, and Amplification, which amplifies the probability amplitude. By using this, it becomes easy to create large-scale Grover circuits. Additionally, since PhaseOracle can generate oracles from logical expressions, it can be easily applied to 3-SAT problems, etc.[2] The implementation status will also be described.

There are various 3-SAT solvers that use classical computers. Although the content of this article cannot reach the performance of those systems, I would like to connect it to thinking about the potential possibilities for extremely large-scale problems. This is true for quantum computing in general.

●Generate oracle from logical formula and amplify probability amplitude

As a simple 2-qubits example, let |10> be the state to be searched. Give a logical expression '(a&~b)' to PhaseOracle to generate an Oracle for it. Next, give the generated Oracle to AmplificationProblem, which has a probability amplitude amplification function. The generated Oracle circuit diagram is shown below. The two filled-in circles and their connections in the circuit diagram are the same as CZ (Controlled Pauli-Z).

Furthermore, draw the entire Grover circuit diagram as shown below. Here, the open circle means that the gate of the target bit is activated when the control bit is |0>.

The results of running this circuit with a simulator (ibmq_qasm) are shown below. As expected, '10' was observed with probability 1.0. In the display below, '01' is measured. This is because the order of the bits in the execution result on the actual machine is the reverse order compared to when they were given as input.

●Solving 3-SAT problems using Grover's algorithm

Next, as an example, solve the 3-SAT shown below. If you give the logical formula of the problem to PhaseOracle as shown below, the corresponding Oracle will be generated. Furthermore, similar to the example above, you can create a circuit of the Grover algorithm that includes this Oracle. Below is the Oracle schematic and the entire algorithm schematic.

Next, as a backend, set up a quantum simulator or a real quantum computer, generate a Grover object, give the above Grover circuit to its method amplify, and run it. The number of repetitions was 1. In other words, iterations=1. The method for calculating the optimal value for Iterations has been clarified, and in this case (3 qubits and 3 solutions), 1 is optimal.

Finally, we show calculation results using a simulator (ibmq_qsam) and an actual quantum computer (brisbane with 127 qubits). Since a certain amount of errors occur on a real machine, the separation of solutions is a little less clear than in the case of a simulator, but it can be said that three correct solutions have been found. (Note) The bit order of the execution result is in the reverse order of the tensor product.

References

[1] James L. Weaver & Frank J. Harkins, “Qiskit Pocket Guide”, O’reilly, 2022.

[2] Grover's algorithm examples, 

https://github.com/Qiskit/qiskit-tutorials/blob/master/tutorials/algorithms/07_grover_examples.ipynb

Oracle and Amplitude Amplifier in Grover's Quantum Algorithm

[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.

https://sparse-dense.blogspot.com/2022/08/grover.html

https://sparse-dense.blogspot.com/2022/12/grover.html

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.

https://www.chrisbernhardt.info/

[2] News about the introduction of IBM's 127 qubit computer to the University of Tokyo

https://jp.newsroom.ibm.com/2023-04-21-The-University-of-Tokyo-and-IBM-agree-to-install-a-quantum-computer-with-127-qubit-processor

Groverの量子アルゴリズムにおけるOracleとAmplitude Amplifier

【要旨】著名な量子アルゴリズムの一つであるGrover search algorithmについては、すでに以下の記事で述べていますので、ここではその意味や解法の詳細説明は略します。

https://sparse-dense.blogspot.com/2022/08/grover.html

https://sparse-dense.blogspot.com/2022/12/grover.html

今回の記事では、確率振幅の反転と、平均値を中心とした折り返しに関して復習します。最新のIBM量子コンピュータ（127量子ビット）による実行結果も含みます。以下の考察は、参考文献[1]から得た知識に基づいています。

●Groverのアルゴリズムの量子回路

　ここでは2qubits（量子ビット数n=2）の場合を考える。そのほかに、制御用の1qubitを使う。その量子回路をFig.1に示した。全てのqubitsについて、初期状態として均等な重ね合わせ状態を作るため、Hadamardゲートを適用する。次に、対象とする関数fに対してOracle Fを構成する。f(xy)=1となるビット列xyが探索するものである。今はそのターゲットを、xy=10と設定した。このOracleFの機能は、このターゲットに対応するbasis |10>の確率振幅の符号を反転させること（flipping the sign）である。それ以外のbasisの確率振幅は変更しない。

　次のゲートAは、上位の２qubitsシステムの４つのbasisの確率振幅を、それらの値の平均値を中心に反転（inversion about the mean）させる。これによって、前段のOracleで符号反転された確率振幅だけが増幅され、他は減衰することになる。ゲートFとゲートAをセットで繰り返すことによって、（ほぼ1.0に近い）高い確率で特定のbasisが測定されるようになる。それが求めるものである。この繰り返しは、n=2の場合は１回で済む。

●Amplitude Amplification Matrix

　さて、Fig.1の右上に示した行列A（対角要素が-1で他の要素は１）を、「確率振幅を要素とするケットベクトル」に掛ければ、確かに上記の通り、確率振幅が増幅されることが分かる。そのことは、参考文献[1]の第9章に詳しく書かれている。だが、どのようにこの行列を導出したのであろうか？それをFig.2で説明する。ここではn=2の場合を扱うのだが、一般のnに対して考察した方が分かり易い。要は、要素の値aを要素全体の平均値mの周りに反転させた結果は、2m-aとなることを利用しているのである。

●Execution on the IBM Quantum 127 qubits real machine

　以上の準備をしてFig.3に示した量子回路を実行する。Oracle Fの回路は、f(10)=1に対して構成した。また、平均値で折り返す振幅増幅部（紫色のAmpというゲート）は、Hadamardゲート、Xゲート、制御付きXゲートで構成することもできるが、Fig.2で示したユニタリ行列Aをそのまま与えることもできる。後者の方が、考え易いように思われる。

　その実行結果をFig.4に示す。(a)7-qubits Falconプロセッサのibm_lagos、(b)127-qubits Eagleプロセッサのibm_brisbane、(c)ibmq_qsam simulatorの実行結果である。まず、(c)のシミュレータでは、ターゲットのbasisが理論通り、確率1.0で測定された。

　一方、実機(a)lagosのエラー発生率は比較的高く、ターゲットのbasisは確率0.75で測定され、他のbasisも若干測定された。だが、最新機(b)brisbaneでは、ターゲットのbasisの確率は0.87まで向上した。目的の解を求めるには十分な情報が得られた。

●感想

　昨年までは、IBMは一般ユーザに5-qubitsおよび7-qubitsのリアルマシンを無償提供していたが、最近、実に127-qubitsという最新マシンも、無料で使えるようにした。実は、2023年４月に、「北米以外で初めて、東大にIBM Eagle 127量子ビットコンピュータを導入」のニュース[2]があった。それから僅か半年で、これと（恐らく）同じ量子コンピュータを、上記の通り、誰でもwebから使えるようになったのである。驚くべき、量子コンピュータの進歩である！

　127量子ビットは、原理的には、2の127乗(=10の38乗)個の状態を同時に処理できる可能性を秘めている。アルゴリズムの発案次第である。そんなマシンを、今や、自宅からweb経由で利用できるのであるから、まだまだ課題は山積ではあるが、夢は膨らむ。

●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.

https://www.chrisbernhardt.info/

[2] 東大にIBMの127量子ビットコンピュータ導入のニュース

https://jp.newsroom.ibm.com/2023-04-21-The-University-of-Tokyo-and-IBM-agree-to-install-a-quantum-computer-with-127-qubit-processor