Try Deutsch's and Grover's algorithms in my quantum circuit simulator

I wrote about the quantum circuit application (simulator) that I created using three mobile phones in previous articles. This time, I confirmed that Deutsch's and Grover's algorithms work correctly with this simulator. Note that in the diagram below, Alice's qubit (q0) and Bob's qubit (q1) are assigned to different mobile phones. The effects of each quantum gate are sent via CloudBD to a mobile phone for control.

●Deutsch's algorithm

Many explanations regarding this have already been published, so I will omit the details. The Deutsch algorithm determines whether a function whose inputs are all 0 or 1 and whose function value also takes 0 or 1 is a constant function or a balanced function. Its feature is that by creating a special mechanism called Oracle, the judgment can be made with only one function evaluation.

Fig.1 and Fig.2 show that the Deutsch algorithm works correctly when the input is one variable using my quantum circuit simulator.

●Grover's algorithm

Grover's algorithm searches for specific data in an unstructured data set. In the first stage of this algorithm, the data to be searched is first marked. In a quantum bit system, this means inverting the phase of the probability amplitude of the corresponding basis vector. This is achieved by creating a circuit called Oracle, just as in the case of Deutsch. Next, in the subsequent stage, a quantum circuit for amplifying the probability amplitude is assembled and executed. As a result, only the probability of the corresponding basis vector becomes 100%, so a search result can be obtained.

Figures 3 to 6 show that, using my quantum circuit simulator, the Grover algorithm works correctly in the case of classical 2-bit information (4 pieces of data) and obtains the desired results.

Superdense coding using my mobile quantum simulator

Japanese abstract
前のポストにおいて、２量子ビットシステムを３台のモバイルフォンで探究するためのアプリ（量子回路シミュレータ）を開発した。今回これを利用して、Superdense codingを実装してみた。Superdense codingは、少ない量子ビットを送ることでたくさんの古典ビット情報を送ることができるアルゴリズムである。このアルゴリズムは、量子重ね合わせと量子もつれを巧みに利用しており、これによって、私の開発したモバイルフォンアプリが正しく動作することを確認できた。

English abstract
In the previous post, I developed an app (quantum circuit simulator) to explore a two-qubit system using three mobile phones. This time I used this to implement Superdense coding. Superdense coding is an algorithm that can send many classical bits of information by sending fewer qubits. This algorithm makes clever use of quantum superposition and entanglement, and I was able to confirm that the mobile phone app I developed worked correctly. 

●Superdense coding that sends classical 2-bit information with 1 qubit
Here, we will deal with Superdense coding, which allows you to send classical 2-bit information (any of 00, 01, 10, 11) by just sending one qubit. The details of the theory are carefully described in reference [1]. I implemented this algorithm with reference to that description. This will be explained specifically using Fig.1 and Fig.2.

Fig.1 shows the preparation phase. In the left column of Fig.1, Alice and Bob each have one qubit. Each is assigned to one mobile phone. The various quantum gates shown in the figure can be applied to freely change the qubit state. Here, (1) Alice applies Hadamard gate H to the initial state |0> to create a superposition state. On the other hand, (2) Bob applied the Pauli X gate to the initial state |1> and changed the state to |0>. These quantum states are transmitted to the control mobile phone on the right side via the real-time database CloudBD. Then, (3) tensor product is calculated to consider these two qubits as one system. Next, (4) Applying the CNOT gate creates a quantum entangled state. In other words, notice that the ”Entangled?” label has changed from false to true.

In Fig.2, (5)Alice applies  Pauli gate Y. As we will see later, applying this Y gate actually means selecting the classical 2-bit information "11". It then sends this qubit to Bob. On the other hand, at this point,  (6) Bob does not take any new action. The control mobile device on the right side of the figure (7)updates the tensor product to reflect Alice's application of the Y gate, but the entangled state is maintained. At this point, Bob will have a total of two qubits: the qubit sent by Alice and the qubit he originally had. Next, Bob has the control mobile device (8)apply the reverse Bell circuit. As a result, the quantum entanglement disappears ("Entangled?" false), and the probability of the basis vector |11> becomes 100%. In other words, if Bob makes a measurement here, he will get the classical bit information "11".

The most important point here is that Bob has no idea what Alice sent him before taking the measurements. Nevertheless, no matter which classical 2-bit information Alice sends, Bob can always simply apply the reverse Bell circuit. That way, Bob can get the information that Alice sent! This is the great thing about Superdense coding.

When sending classical bit information other than "11", it is shown in Fig.3. If Alice would like to send "00", she applies the I gate (no action). If she sends "01" she applies the X gate, and if she sends "10" she applies the Z gate. In any of these cases, as mentioned above, Bob only needs to perform the measurement after applying the reverse Bell circuit.

References
[1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.
https://www.chrisbernhardt.info/

Quantum entanglement experiment using multiple mobile phones

Japanese abstract

今回は、量子コンピューティングで最も神秘的な原理である「量子もつれ」を、自作モバイルアプリで探究する。その特徴は、１量子ビットを１台のモバイルフォンに割り当て、２つの量子間のもつれ関係を、（リアルタイム性を持つ）クラウドデータベースを経由して作り出すことである。遠く離れた２台のモバイルフォン間でこれを実験することにより、遠隔量子間のもつれ現象を模倣し、理解を深めることができる。これこそが、このアプリを開発した理由なのである。このような高度な機能の実現を容易にしてくれるMIT App Inventorに改めて感謝したい！

English abstract

I would like to explore the most mysterious principle in quantum computing, "quantum entanglement", using a mobile app I created. Its major feature is that one qubit (quantum bit) is assigned to one mobile phone, and the entanglement relationship between two qubits is created via a cloud database (with real-time capabilities). By experimenting with this between two mobile phones far apart, it is possible to mimic and better understand the phenomenon of entanglement between remote quanta. That is the reason why I developed this app. Thanks again to MIT App Inventor for making it easy to achieve such advanced functionality!

●Manipulate a single qubit

In a previous post, I described a mobile application for a single qubit. Even when limited to a single qubit, it is possible to create any quantum state using various quantum gates. Using this app, we were able to learn the basics of quantum superposition and measurement. However, to handle the most mysterious and important principle of quantum entanglement, we need at least two qubits. So, what method should we use to handle more than two qubits in mobile apps? This will be explained below.

●Explore quantum entanglement by assigning one qubit to one mobile phone

The new app targets a two-qubit system, with one qubit assigned to one mobile phone. Perhaps this method will reduce the complexity of the app. To mimic quantum entanglement, we need to consider multiple qubits as a system, rather than looking at each one individually. To do this, I decided to use another mobile phone to calculate the tensor product of all qubits. The measurement result of one quantum bit in an entangled state automatically and instantly changes the state of the other quantum bit. The real-time Cloud DB included in MIT App Inventor was useful in achieving this.

●Experimental example of quantum entanglement

(1)IBM Quantum Composer

Let's take the most basic quantum entanglement as an example. Fig.1 shows the case using IBM Quantum Composer. Prepare two qubits q0 and q1. First, apply the Hadamard gate H to q0 to create a superposition state, and leave q1 in its initial state (|0⟩). At this stage, q0 has no relationship with q1.

Next, if we apply a CNOT(0,1) gate to two qubits (control bit is q0, target bit is q1), both become entangled. Then, for example, when q0 is measured, the states of q0 and q1 will be either 00 or 11. In other words, the measurement result of q0 is immediately reflected in q1. This is quantum entanglement.

The mathematical model for this example problem is explained in detail in reference [1].

(2) Mimic quantum entanglement with three mobile phones

What was done with IBM Quantum was achieved with three mobile phones. As shown in Fig. 2(a), quantum bits qubit_0 and qubit_1 are each assigned to one mobile phone, and the third mobile phone performs control. Hadamard Gate H has already been applied to qubit_0. Once the quantum states (probability amplitudes) of qubit_0 and qubit_1 are stored in CloudDB, the third mobile phone calculates the tensor product to treat the two qubits as one system. As a result, four disks (corresponding to the four basis vectors) are displayed, and the probabilities and phases are shown. Fig.2(b) shows the actual screens of the three mobile phones on which this was performed.

The third mobile phone then applies the CNOT(0,1) gate to these two qubits. This creates a quantum entangled state as shown in Fig. 3(a). Fig.3(b) shows the actual screens of the three mobile phones at this time.

Once entangled in this way, the two mobile phones set up their Cloud DBs so that they can sense when the other has taken a measurement. As shown in Fig. 4(a), when it senses the other party's measurement, it immediately changes its own state based on the already stored quantum entanglement information. Fig.4(b) is the actual screen at that time.

(Note) This example is an entanglement in which two qubits are in the Bell state. In entanglement cases other than the Bell state, the measurement result of one does not necessarily definitively determine the other state. It depends on the nature of Entanglement at that time. Quantum entanglement generally refers to a correlation, but its strength varies.

●Summary

By developing an application that mimics quantum entanglement, I have gained a deeper understanding of the meaning of the tensor product of multiple qubits and the phenomenon of quantum entanglement. This time, I used CNOT(0,1), but you can also use CNOT(1,0) with the control bit and target bit reversed. Additionally, other gates can be combined to create quantum entanglement.

References

[1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.

https://www.chrisbernhardt.info/

Final version of my single-qubit apps

I recently completed the final versions of two apps for single-qubit manipulation!

These apps were developed in a short period of time using MIT App Inventor. Although many existing blocks could be used effectively, some ingenuity was required to represent the qubit states on the Bloch sphere. The problem was to project 3D coordinate data (x, y, z) onto a 2-dimensional plane, and I was able to solve this problem by using the isometric projection method.

(1) Displaying the results of successive application of quantum gates

Five types of quantum gates (Z, X, Y, H, T) can be used. The figure below (b) shows the result of successively applying H, T, and H to the quantum bit |0>. The final qubit state is shown as a big red dot on the Bloch sphere on the left. Small disks are also shown to the right. The area of the filled disk indicates the probability of each basis (|0>, |1>). A straight line coming out from the center of the circle indicates the phase. At the bottom of the Bloch sphere, some numerical values indicating quantum states are also shown.

(2) Conversion to make the phase of α 0 in qubit α|0>+β|1>

In order to represent a quantum bit on a Bloch sphere, the phase of α needs to be 0, and the phase of β needs to be the relative phase (φ) to it. The app shown below achieves this functionality. This is also a transformation that makes the imaginary part of the complex number α 0. Figure (b) below confirms that this conversion function is working correctly.

Dynamic representation of qubit for arbitrary θ and Φ

The static Bloch sphere model image is good, but it would be even better if we could dynamically represent the quantum bit state for arbitrary θ and Φ values !

I made this possible with a smartphone app! 

Generally speaking, it is somewhat difficult to create a 3D representation using MIT App Inventor, but it was relatively easy to map points on a Bloch sphere with a radius of 1 onto a 2D plane using Isometric projection.

Also check out the short video in action below.

Developing the most basic app to understand Qubit state (3)

Sometimes we need to go back to basics!

In the third article in this series, I'll compare my app's results with that of IBM Quantum Composer to confirm that it's working correctly. In my app I can use quantum gates Z, X, Y, T, H.  The T is a quantum gate that adds the phase of e^iφ to the qubit |1>. By default, φ=π/4. Also, H is a Hadamard gate. Here, as an example, H, T, and H are successively applied in this order to the quantum bit initial state |0>.

Fig.1 shows (a) the execution results of my app and (b) the execution results of IBM Quantum. In (a), the probability (area of the colored disk) and phase (the angle of the straight line coming out from the center of the circle) are shown for |0> and |1>. On the other hand, in (b), the results are displayed only for |1>. Although the way the disks are displayed is slightly different, it can be seen that the probabilities and phases of both are the same. However, the values of probability amplitude (amplitude in (a) and Output state in (b)) seem to be different. This will be explained in Fig.2.

Fig.2 explains that although the expressions of the probability amplitudes of the two are different, they are the same quantum state. In my app, the phase with respect to |0> is zero, and the phase of |1> is the relative phase to it. This does not seem to be the case with IBM Quantum. In fact, when I input IBM's probability amplitude numbers into my app's function state2relphase, the results I got matched my app's representation of probability amplitudes. This result confirms that my app is working perfectly correctly, at least for this example.

Developing the most basic app to understand Qubit state (2)

 Sometimes we need to go back to basics!

This is a major update to the previous app. The aim was to help students become familiar with the most basic elements of quantum computing using only their smartphones. The example below shows the results of (1) starting from the initial state, (2) applying the Pauli X gate, (3) then applying the Hadamard gate, and (4) applying the Hadamard gate again. 

The probability amplitude, probability, and relative phase of each basis |0>, |1> are shown numerically and on a disk. Additionally, the values of θ and φ can be set using text boxes and sliders, making it easy to understand the position of the quantum bit on the Bloch sphere.

Developing the most basic app to understand Qubit state (1)

Sometimes we need to go back to basics!

As I have already written several times, I was able to almost completely understand the basic concepts and ideas of quantum computing by reading the book [1]. Although this book does not explain the Bloch sphere or phases in detail, I would not have been able to write this article without the knowledge I gained from the book.

I developed an app to understand the state of qubits on the Bloch sphere. As shown in the figure below, set the two angular parameters θ and φ using the sliders for a single qubit on the Bloch sphere. This app uses it to calculate the probability amplitude and probability for each of the two basis (|0> and |1>). Probability and phase are also illustrated in the two disks at the top right. Note that since the global phase can be ignored, the phase of |0> is set to 0, and the phase of |1> is expressed as a relative phase to that.

As you can see, the current app specifies θ and φ manually. In the next version, it will also be possible to apply basic quantum gates (X, Y, Z, H, etc.).

References
[1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.
https://www.chrisbernhardt.info/

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

Simonの量子アルゴリズムとHadamard行列のKronecker積

【要旨】量子コンピューティングでの重要な行列（ゲート機能）の一つに、アダマール行列があります。複数の量子ビットシステム（テンソル積）の各量子ビットにアダマール変換を施すための行列が、Kronecker Products of Hadamard Matrices（アダマール行列のクロネッカー積） です。記念碑的解法として有名なSimonの量子アルゴリズムにも有効に使われています。それは、参考文献[1]で丁寧に説明されているのですが、時間が経つと忘れてしまうので、私自身の理解をメモとして残して置きます。

■Simon's Algorithm
　まず、ここで解くべき問題については既に本ブログ（2022-12-11の記事）に書いたので、以下に極く簡単に記す：

　長さnのbinary string x（0か1から成る文字列）を入力とし、出力も長さnのbinary stringとなる2対1関数fがあるとする。ここで、ある長さnの秘密のbinary string s があり、y=x or y=x⊕s の時に限りf(x)=f(y) である。ただし、sの全ての文字が0であることは無いとする。記号⊕は、bitwise addition of strings modulo 2を意味する。入力xに対する関数値f(x)を問い合わせることはできるが、関数fの定義は与えられていない。解くべきことは、秘密のsを特定することである。

　そのために、関数fを何回評価する必要があるかを問題とする。古典的アルゴリズムでは、最悪の場合、2のn乗のオーダーの関数呼び出し回数となるが、Simonの量子アルゴリズムではnの多項式オーダーとなる。しかし、この言い方はあまり正確ではない。計算量に関する、BQP（Bounded-error Quantum Polynomial-time）などの議論を、Prof. Bernhardtの書籍[1]のChapter 8 （pp.166-170）等でご覧いただく必要がある。

■Simon's Algorithmを実装する量子回路
　Simonの問題は、上記の関数fと秘密のsを知っている人が作成した問題を解く、いわばリバースエンジニアリングである。実用的な問題ではないにも拘らず、これに対するSimonの解法は、量子アルゴリズムの威力を示すものとして広く認められている。そのための量子回路を、n=2とn=3の場合について検討するが、その方法は一般のnについても自然に当てはめることができる。この量子回路の出力であるいくつかのbinary string（長さn）から、秘密のsを特定するための連立一次方程式を作ることができる。なぜかと言うと、出力されたbinary string bと秘密のsとのdot product（後述）が0になるからである。以下に、このようなdot productがなぜ0になるかを中心に、図を使って詳しく述べる。

　Fig.1は、n=2とn=3の場合のSimonのアルゴリズムを実装した量子回路である。上述の通り、関数fに対するOracleが設定されている。すなわち、関数fの定義と秘密のsがこのように決められているのだが、回答する人はそれを知らずにsを特定するのである。

　一般のnに対してのSimonの量子回路は、Fig.2のように描ける。

　さて、Fig.3は、Fig.1でのn=2とn=3の場合の量子回路の実行結果である。２段になっているレジスタの１段目を測定した結果をFig.3に示した。n=2の問題では測定結果としてbinary string 00と10がそれぞれ1/2の確率で得られた。これらのbinary stringと秘密のsとのdot productsは0となる。そうすれば、それらから連立一次方程式を作ってsを特定できのだが、この部分に関しては既に述べたので、ここでは省略する。以降では、なぜ、このdot productsが0になるのかを考察する。

■測定結果のbinary stringと秘密のsとのdot productsがなぜ0になるのか
　この質問の回答を、以下で検討する。Fig.4は、Fig.1 case(a)でのψaのフェーズ（２回目のHadamard変換後で測定を行う直前）の4量子ビットシステムの状態ベクトルである。いくつかの計算を経ているが、ここに示されているのは、４qubitsのうちの上段の2qubitsに着目して式を整理した結果である。

　テンソル積の左側が|10>（測定結果10に対応）である項の関数fの値に注目する。秘密sに関するペアのbit string（00と01、および10と11）に対する関数fの値は同一であるが、それらの符号（プラス、マイナス）も同一である。もう一つの測定結果|00>についても同様である。

　一方、測定結果に現れない|01>と|11>に関しては、これらのペアの間数値の符号が互いに反転している。そのため、最終的な計算結果として、|00>と|10>の確率振幅が増大され、|01>と|11>に関しては減衰（キャンセル）されて０となった。

　このような増幅と減衰が、「測定結果のbit stringと秘密のsとのdot podurct (・)」とどのように関係しているかを、Fig.5で明らかにしている。

　以上で説明を終わるのだが、最後に、Fig.6をご覧いただきたい。ここに、Hadamard行列のKronecker積がある。たとえば、n=2の場合の行列を見ると、その各要素の符号は、Fig.4で示した項の符号と完全に合致している。すなわち、Fig.4でのテンソル積の左側のqubitのペアを行ラベルとし、関数fの引数に与えるqubitの組みを列ラベルと考えれば、Hadamard行列の該当要素の符号が（マイナス１に対してのdot productの冪乗で）直ちに計算できるのである。むしろ、Fig.4でのテンソル積の右側に出現する項の符号は、このHadamard行列から決められるのである。ここに、Kronecker products of Hadamard matricesの重要性がある。

■まとめ
　Prof. Bernhardtは [1]の中で、このSimon's algorithmにダブルスター⭐️⭐️（かなり難しい）を付している。確かにその通りだが、何度か読み返して検討して、上記のように理解できた。確率振幅の増幅と減衰に関しては、Groverのアルゴリズムではその操作を明示的に行なってるが、Simonでは「知らぬ間にそうなっている」感がある。ともかく、以下の文言を言えれば、Simonアルゴリズムは一応理解できたことになるのではないか。Fig.7参照。

「Simonの量子回路での全ての測定結果（行ラベル）について、秘密sでペアとなるbinary string（列ラベル）が示すHadamard行列の要素の符号は互いに一致する」

　Simonのアルゴリズムは、有名なShorの因数分解アルゴリズムに影響を与えたことが[1]に具体的に説明されている。その叙述から、Shor's algorithmの"こころ"をつかむことができると思う。ただし、もちろん、その詳細を知るには、量子フーリエ変換などの進んだ数学が必要になるので、改めてじっくり取り組みたいと思う。

 Reference

 [1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.

https://www.chrisbernhardt.info/

生成AIに関するMIT App Inventor Workshopが神奈川工科大学で開催

　MIT App Inventorでは、いち早くChatBotやImageBotなどの生成AIを組み込んで、生徒、学生、一般人が利用できる環境を提供している。それに関するワークショップが、日本では初めて、神奈川工科大学で5日間（2023/9/6〜12）に渡り開催された。生成AIのうちでも、自然言語からアプリを生成するAptlyは、まだ研究開発中のものであるが、今回（このようなワークショップとしては）初めて、受講生が試用できるよう設定していただいた。

　MIT AppInventorチームのソフトウェア開発者であるDavid Kimさん（in person）とAngie Zhouさん（online）が講師となり、情報、生命、電気、機械など多様な分野の学生が多数、熱心に受講した。最終日には、受講生が各自のアイディアをApp Inventorで実現したプレゼンも行われた。

　最終日の冒頭、MITの著名なComputer Science教授で、App Inventor創始者であるProf. Hal Abelsonから、受講生を激励するメッセージをライブ出演でいただいた。さらに同チームのDr. Evan Patton、Jeff Frilich、Dr. Natalie Laoの3名の専門家からも同様に貴重なメッセージがあった。これは、MIT App Inventorチーム全体として、本Workshopに強い関心を持って対応していただいた証であり、特筆すべきことであった。

　講師のDavidさんのTweetはこちらにあります。また、MIT App Inventor Facebookにも同様の投稿があります。神奈川工科大学の日本語ニュースと英語版ニュースにもこのWorkshopの模様が載っています。

　このワークショップの詳細レポート（８ページ）は、ここには掲載していないが、特にご関心のある方はご連絡いただきたく。

MIT App Inventor Generative AI workshop at 神奈川工科大学