JP7570639B2 - Information processing device, simulation method and program - Google Patents

Description

The present invention relates to an information processing device, a simulation method, and a program.

Quantum computers are computers that consist of basic elements called qubits. Quantum computers can perform various computational tasks much faster than conventional computers, and therefore have attracted much attention and are being actively developed. Quantum computing tasks are expressed in a form that mimics a logic circuit, called a "quantum circuit" (Non-Patent Document 1). To investigate what computational tasks can be performed quickly with quantum computing, a quantum circuit simulator that mimics the behavior of quantum computing with a normal computer is an important tool. However, the fact that quantum computers are much faster than normal computers in some tasks also means that the task of "simulating a quantum computer" is a very time-consuming task for normal computers, and it is said that it is impossible to simulate a general quantum circuit with more than 100 qubits in a realistic time (Non-Patent Document 2).

The instructions executed by a quantum computer are divided into two types: "operations" and "measurements." Operations are instructions that change the state of quantum bits, while measurements are instructions that measure quantum bits and obtain normal bits as the measurement result. Therefore, the simulator can output a string of normal bits as a result of the simulation, the number of which is equal to the number of "measurement" instructions.

Operations can be associated with elements of a mathematical set called the "unitary group." Measurements can be associated with elements of a set called the "Pauli group." As mentioned above, it is difficult to simulate all of these commands at high speed, but it is known that if the set of operations is limited from the "unitary group" to its subset, the "Clifford group," it is possible to simulate the behavior of a quantum computer at high speed even on a normal computer (Non-Patent Documents 3 and 4). In this way, quantum circuits whose operations are limited to the Clifford group are called "Clifford circuits." Therefore, in cases where the quantum circuit for the computational task to be simulated on a quantum computer is a Clifford circuit, it can be simulated at high speed using the above algorithm. In addition, the method of simulating a Clifford circuit is called a "stabilizer simulator" after the name of the element used in the method.

In modules such as the "calculus of variations," which is currently expected to find applications, and "error-correcting codes," which significantly reduce errors in quantum computing, it is natural to consider situations in which the operations of the "Clifford group" are dominant. Therefore, stabilizer simulators are often used in research into such algorithms and methods.

The mechanism of existing stabilizer simulators is shown below. Consider the case of simulating a task consisting of n "qubits," which are unit elements of quantum computing. During simulation, existing stabilizer simulators hold a table called a "stabilizer table," which is "2n high and n wide" and consists of a total of ²ⁿ² elements. Here, each element is one of the four characters [I, X, Y, Z] and can be expressed with 2 bits. In a typical stabilizer simulator, a specific column of this table is updated in an "operation," and a row is mainly updated in a "measurement," thereby simulating a quantum computing task.

In normal computer memory, data is arranged one-dimensionally, and it is known that continuous reading and writing is much faster than discontinuous reading and writing. Therefore, to perform the above simulation quickly, it is desirable that the values updated by the operation are arranged as continuously as possible in memory. In the stabilizer table, an arrangement in which rows are arranged consecutively is called row-major, and an arrangement in which columns are arranged consecutively is called column-major. With a row-major arrangement, "measurements" can be performed quickly, and with the column-major method, "operations" can be performed quickly. In existing stabilizer simulator libraries, it is natural to perform mathematical descriptions in row-major, so row-major is often implemented (Non-Patent Document 5, Non-Patent Document 6, Non-Patent Document 7, Non-Patent Document 8).

Learn Quantum Computation using Qiskit, [online], Internet <URL: https://qiskit.org/textbook/ch-states/introduction.html> Arute, Frank, et al. "Quantum supremacy using a programmable superconducting processor." Nature 574.7779 (2019): 505-510. Gottesman, Daniel. "The Heisenberg representation of quantum computers." arXiv preprint quant-ph/9807006 (1998). Aaronson, Scott, and Daniel Gottesman. "Improved simulation of stabilizer circuits." Physical Review A 70.5 (2004): 052328. CNOT-Hadamard-Phase, [online], Internet <URL: https://www.scottaaronson.com/chp/> Python CHP Stabilizer Simulator, [online], Internet <URL: https://github.com/Strilanc/python-chp-stabilizer-simulator> chp-sim, [online], Internet <URL: https://github.com/qsharp-community/chp-sim> Qiskit, [online], Internet <URL: https://qiskit.org/>

However, as the development of quantum computers progresses, the scale of the algorithms and modules to be simulated is growing, making it difficult for even stabilizer simulators to simulate at a sufficient speed. For this reason, there is a demand for a method to simulate quantum circuits faster.

The disclosed technology aims to speed up simulation of quantum circuits.

The disclosed technology is an information processing device for simulating a Clifford circuit, and includes a quantum circuit update unit that updates the quantum circuit so as to improve the continuity of "measurement" and "operation" commands among the commands contained in an input quantum circuit, and a simulation unit that simulates while switching the arrangement of each element of a stabilizer table in memory based on the updated quantum circuit.

The disclosed technology can speed up simulation of quantum circuits.

FIG. 2 is a diagram illustrating an example of a functional configuration of an information processing device. FIG. 4 is a diagram illustrating an example of a stabilizer table. FIG. 11 is a diagram showing an example of the flow of an overall process. FIG. 11 is a diagram illustrating an example of the flow of a quantum circuit update process. FIG. 13 is a diagram illustrating an example of the processing flow of a pop_next_operation function. FIG. 11 is a diagram illustrating an example of a flow of a simulation process. FIG. 2 illustrates an example of a hardware configuration of a computer.

The following describes an embodiment of the present invention (the present embodiment) with reference to the drawings. The embodiment described below is merely an example, and the embodiment to which the present invention is applicable is not limited to the following embodiment.

(Overview of information processing device)
The information processing device according to the present embodiment is a device for simulating a Clifford circuit. A Clifford circuit is a quantum circuit in which operations are limited to the Clifford group. A Clifford circuit is expressed as a one-dimensional sequence of operations and measurement commands.

Specifically, the information processing device updates the quantum circuit so that, among the commands contained in the input quantum circuit, the "measurement" and "operation" are arranged as consecutively as possible, i.e., to improve the continuity of the "measurement" and "operation" commands. The information processing device then simulates the updated quantum circuit by switching the arrangement in memory of each element of the stabilizer table so that it becomes row-major for "measurement" and column-major for "operation".

(Example of functional configuration of information processing device)
1 is a diagram illustrating an example of a functional configuration of an information processing device 10. The information processing device 10 includes a quantum circuit update unit 11, a simulator 12, and a stabilizer table storage unit 13.

The quantum circuit update unit 11 updates the quantum circuit O such that, among the instructions [o ₁ , o ₂ , . . . , o _n ] contained in the input quantum circuit O, the “measurements” and the “operations” are arranged as consecutively as possible.

The simulator 12 uses the stabilizer table to simulate the updated quantum circuit T and outputs data indicating the measurement value m. At this time, the simulator 12 performs the simulation while switching the arrangement of each element of the stabilizer table in memory so that it becomes row-major during "measurement" and column-major during "operation".

The stabilizer table storage unit 13 stores the stabilizer table to be used for the simulation.

(Example of a stabilizer table)
2 is a diagram showing an example of a stabilizer table. The stabilizer table is a table consisting of n rows and 2n columns, a total of ²ⁿ² elements, as in the conventional stabilizer simulator. Here, each element is, for example, one of four characters [I, X, Y, Z], and is expressed by 2 bits. Also, as in the conventional stabilizer simulator, the simulator unit 12 simulates a quantum computing task by updating a specific column of the stabilizer table in the "operation" and mainly updating the rows in the "measurement".

In the initial state, the stabilizer table has a Column-major arrangement in memory. Column-major is an arrangement in which elements of a column are consecutive on the memory, and the elements shown in FIG. 2 are consecutive as follows: _d1,1 , _d2,1 , _d3,1 , ..., d2n _{, 1} , _d1,2 , _d2,2 , _d3,2 , ..., d2n,2, _d1,3 , _d2,3 , _d3,3 , ..., _d2n,3 , ..., _d1 ,n, _d2,n , _d3,n , ..., _d2n,n .

When simulating the "measurement" process, the simulator 12 changes the arrangement in memory so that the stabilizer table has a Row-major arrangement. Row-major is an arrangement in which row elements are consecutive on the memory, and the elements shown in FIG. 2 are consecutive as follows: _d1,1 , _d1,2 , _d1,3 , ..., _{d1 ,n} , _d2,1 , _d2,2 , _d2,3 , ..., _d2 ,n, _d3,1 , d3,2, _d3,3 , ..., d3 _,n , ..., d2n, _{1, d2n, 2, d2n,3 ,} ..., _d2n,n .

(Operation of information processing device)
Next, the operation of the information processing device 10 will be described with reference to the drawings.

Figure 3 is a diagram showing an example of the flow of the overall processing. When the information processing device 10 receives input of the quantum circuit O by user operation or the like, it executes the overall processing. When the overall processing starts, the quantum circuit update unit 11 executes the quantum circuit update processing (step S1). Next, the simulation unit 12 executes the simulation processing based on the updated quantum circuit (step S2).

Figure 4 is a diagram showing an example of the flow of the quantum circuit update process. When the quantum circuit update process shown in step S1 of Figure 3 starts, the quantum circuit update unit 11 initializes the variable s to 0, the variable i to 1, and the updated quantum circuit T to [ ] (step S11).

Next, the quantum circuit update unit 11 determines whether i = n (step S12). If the quantum circuit update unit 11 determines that i = n is not true (step S12: NO), it assigns the execution result of pop_next_operation(s, O) to O, o (step S13). The pop_next_operation function is a function that extracts an "operation" command when s is 0, and extracts a "measurement" command when s is 1. Details of the pop_next_operation function will be described later.

Next, the quantum circuit update unit 11 determines whether or not o=None (step S14). If the quantum circuit update unit 11 determines that o=None is not true (step S14: NO), it assigns T+[o] to T (step S15). In this step S15, the instruction o deleted in step S13 is added to the end of the element string, thereby changing the order of the instructions.

Then, the quantum circuit update unit 11 assigns i to i+1 (step S16) and returns to the processing of step S13.

In step S14, if the quantum circuit update unit 11 determines that o=None (step S14: YES), it assigns 1-s to s (step S17) and returns to the processing of step S13. In step S17, the quantum circuit update unit 11 switches between the processing for consolidating "operation" commands and the processing for consolidating "measurement" commands.

In step S12, if the quantum circuit update unit 11 determines that i = n (step S12: YES), it outputs the updated quantum circuit T (step S18).

5 is a diagram showing an example of the process flow of the pop_next_operation function. The input quantum circuit O is set to [o ₁ , o ₂ , ..., o _m ]. Note that, since the quantum circuit O may have instructions extracted by the process described later deleted, m is a number between 1 and n. In addition, when the pop_next_operation function starts, i=1.

The quantum circuit update unit 11 determines whether i=m (step S1301). If the quantum circuit update unit 11 determines that i=m (step S1301: YES), it returns O, None (step S1302) and ends the processing of the pop_next_operation function.

Furthermore, when the quantum circuit updating unit 11 determines that i=m is not true (step S1301: NO), it determines whether or not s=0 is true (step S1303). When the quantum circuit updating unit 11 determines that s=0 is true (step S1303: YES), it determines whether or not the instruction o _i is an operation (step S1304).

If the quantum circuit update unit 11 determines that the instruction o _i is an operation (step S1304: YES), it assigns 1 to the variable j (step S1306) and determines whether the instruction o _i and the instruction o _j are substitutable (step S1307).

When the quantum circuit is a Clifford circuit, it is known that it is easy to determine whether an instruction is replaceable or not, since the types of instructions are limited.

Furthermore, in the process of step S1304, if the quantum circuit update unit 11 determines that the instruction o _i is not an operation (step S1304: NO), it assigns i+1 to i (step S1308) and returns to the process of step S1301.

In addition, in the process of step S1303, if the quantum circuit update unit 11 determines that s is not 0 (step S1303: NO), it determines whether the instruction o _i is a measurement (step S1305). If the quantum circuit update unit 11 determines that the instruction o _i is a measurement (step S1305: YES), it proceeds to the process of step S1306.

If the quantum circuit update unit 11 determines that the instruction o _i is not a measurement (step S1305: NO), the process proceeds to step S1308.

If the quantum circuit update unit 11 determines that the instruction o _i and the instruction o _j are not substitutable (step S1307: NO), the quantum circuit update unit 11 proceeds to the process of step S1308.

When the quantum circuit update unit 11 determines that the instruction o _i and the instruction o _j are interchangeable (step S1307: YES), it determines whether or not j = i (step S1309). When the quantum circuit update unit 11 determines that j = i is not the case (step S1309: NO), it assigns j + 1 to j (step S1310) and returns to the process of step S1307.

When the quantum circuit update unit 11 determines that j=i (step S1309: YES), it deletes the instruction o _i from the quantum circuit O (step S1311). Then, the quantum circuit update unit 11 returns the quantum circuit O and the instruction o _i (step S1312) and ends the processing of the pop_next_operation function.

Figure 6 is a diagram showing an example of the flow of the simulation process. When the simulation process shown in step S2 of Figure 3 is started, the simulator 12 initializes the variable s to 0, the variable i to 1, and the measurement value m to be output to [ ] (step S201).

The simulator 12 judges whether s=0 (step S202). If the simulator 12 judges that s=0 (step S202: YES), the simulator 12 judges whether the command o _i is an operation (step S203). If the simulator 12 judges that the command o _i is an operation (step S203: YES), the simulator 12 simulates the command o _i (step S205). Next, the simulator 12 assigns i+1 to the variable i (step S206) and proceeds to the process of step S212.

In the process of step S203, when the simulator 12 determines that the command o _i is not an operation (step S203: NO), it swaps the columns and rows of the stabilizer table for the arrangement on the memory (step S210). That is, the simulator 12 changes the arrangement on the memory from a Row-major arrangement to a Column-major arrangement, and changes the arrangement on the memory from a Column-major arrangement to a Row-major arrangement.

Then, the simulator 12 assigns 1-s to the variable s (step S211) and returns to the processing of step S202.

Furthermore, when the simulating unit 12 determines that s is not 0 in the process of step S202 (step S202: NO), it determines whether the command o _i is a measurement (step S204). When the simulating unit 12 determines that the command o _i is a measurement (step S204: YES), it measures the command o _i to obtain an individual measurement value v (step S207) and assigns m+[v] to the overall measurement value m (step S208). Next, the simulating unit 12 assigns i+1 to the variable i (step S209) and proceeds to the process of step S212.

When the simulator 12 determines in step S204 that the instruction _oi is not a measurement instruction (step S204: NO), the simulator 12 proceeds to step S210.

In the process of step S212, the simulator 12 determines whether i=n (step S212). If the simulator 12 determines that i=n is not true (step S212: NO), the process returns to step S202.

When the simulator 12 determines that i = n (step S212: YES), it outputs the measurement value m (step S213).

(Hardware Configuration Example According to the Present Embodiment)
The information processing device 10 can be realized, for example, by making a computer execute a program in which the processing contents described in this embodiment are described. Note that this "computer" may be a physical machine or a virtual machine on the cloud. When a virtual machine is used, the "hardware" described here is virtual hardware.

The above program can be recorded on a computer-readable recording medium (such as a portable memory) and can be stored or distributed. The above program can also be provided via a network such as the Internet or e-mail.

Figure 7 is a diagram showing an example of the hardware configuration of the computer. The computer in Figure 7 has a drive device 1000, an auxiliary storage device 1002, a memory device 1003, a CPU 1004, an interface device 1005, a display device 1006, an input device 1007, an output device 1008, etc., all of which are interconnected via a bus B.

The program that realizes the processing on the computer is provided by a recording medium 1001, such as a CD-ROM or a memory card. When the recording medium 1001 storing the program is set in the drive device 1000, the program is installed from the recording medium 1001 via the drive device 1000 into the auxiliary storage device 1002. However, the program does not necessarily have to be installed from the recording medium 1001, but may be downloaded from another computer via a network. The auxiliary storage device 1002 stores the installed program as well as necessary files, data, etc.

When an instruction to start a program is received, the memory device 1003 reads out and stores the program from the auxiliary storage device 1002. The CPU 1004 realizes the functions related to the device according to the program stored in the memory device 1003. The interface device 1005 is used as an interface for connecting to a network. The display device 1006 displays a GUI (Graphical User Interface) or the like according to a program. The input device 1007 is composed of a keyboard, mouse, buttons, a touch panel, or the like, and is used to input various operation instructions. The output device 1008 outputs the calculation results. Note that the above computer may be equipped with a GPU (Graphics Processing Unit) or a TPU (Tensor processing unit) instead of the CPU 1004, or may be equipped with a GPU or TPU in addition to the CPU 1004. In that case, the GPU or TPU may execute processes that require special calculations, and the CPU 1004 may execute other processes, so that the processes may be shared and executed.

In the above-described embodiment, the quantum circuit update method illustrated in FIG. 4 and FIG. 5 is a method that applies an optimization technique known as a greedy method. The quantum circuit update method is not limited to this, and any other method that improves the continuity of the "measurement" and "operation" commands may be used.

In the above-described embodiment, when simulating multiple quantum circuits, if a quantum circuit of the same shape is simulated multiple times, the information processing device 10 may store the quantum circuit T updated by the quantum circuit update unit 11 in the first simulation, and in the second and subsequent simulations, the updated quantum circuit T may be used to perform simulation by the simulator 12. This makes it possible to substantially ignore the cost of the update process by the quantum circuit update unit 11 when simulating the same quantum circuit multiple times.

(Effects of this embodiment)
According to the information processing device 10 of the present embodiment, the quantum circuit is updated so that, among the commands included in the input quantum circuit, "measurement" and "operation" are arranged as consecutively as possible. Then, the information processing device 10 simulates the updated quantum circuit while switching the arrangement of each element of the stabilizer table in memory so that "measurement" is row-major and "operation" is column-major.

If the quantum circuit is not updated and only the memory layout is switched, and "measurements" and "operations" are arranged alternately in quantum circuit O, a process of switching between row-major and column-major will occur for each simulation process, and the time required for simulation may actually increase.

In contrast, according to the information processing device 10 of this embodiment, the continuity of the "measurement" and "operation" commands is improved, so the number of times the process of switching the memory layout can be executed can be minimized. This makes it possible to speed up the simulation of quantum circuits.

Specifically, the quantum circuit update unit 11 uses a greedy optimization method to update the quantum circuit O so that the "measurements" and "operations" are arranged as contiguously as possible. This makes it possible to easily improve the continuity of the "measurements" and "operations" commands.

(Summary of the embodiment)
This specification describes at least the information processing device, simulation method, and program described in the following sections.
(Section 1)
1. An information processing apparatus for simulating a Clifford circuit, comprising:
A quantum circuit update unit that updates the quantum circuit so as to improve the continuity of the "measurement" and "operation" commands among the commands included in the input quantum circuit;
A simulating unit that simulates while switching the arrangement of each element of the stabilizer table on the memory based on the updated quantum circuit.
Information processing device.
(Section 2)
The simulating unit simulates while switching the arrangement of each element of the stabilizer table in memory so that the instruction included in the updated quantum circuit becomes row-major in the case of “measurement” and column-major in the case of “operation”.
2. The information processing device according to claim 1.
(Section 3)
The quantum circuit update unit updates the quantum circuit using a greedy optimization method so that the "measurements" and "operations" are arranged as consecutively as possible.
3. The information processing device according to claim 1 or 2.
(Section 4)
1. A method for simulating a Clifford circuit executed by an information processing device, comprising:
Updating the quantum circuit so as to improve the continuity of "measurement" and "operation" commands among the commands included in the input quantum circuit;
and simulating while switching the arrangement of each element of the stabilizer table in the memory based on the updated quantum circuit.
How to simulate.
(Section 5)
A program for causing a computer to function as each unit in the information processing device according to any one of claims 1 to 3.

Although the present embodiment has been described above, the present invention is not limited to this specific embodiment, and various modifications and variations are possible within the scope of the gist of the present invention described in the claims.

10 Information processing device 11 Quantum circuit update unit 12 Simulator unit 13 Stabilizer table storage unit 1000 Drive device 1001 Recording medium 1002 Auxiliary storage device 1003 Memory device 1004 CPU
1005 Interface device 1006 Display device 1007 Input device 1008 Output device

Claims (5)

1. An information processing apparatus for simulating a Clifford circuit, comprising:
A quantum circuit update unit that updates the quantum circuit so as to improve the continuity of the "measurement" and "operation" commands among the commands included in the input quantum circuit;
A simulating unit that simulates while switching the arrangement of each element of the stabilizer table on the memory based on the updated quantum circuit.
Information processing device. The simulating unit simulates while switching the arrangement of each element of the stabilizer table in memory so that the instruction included in the updated quantum circuit becomes row-major in the case of “measurement” and column-major in the case of “operation”.
The information processing device according to claim 1 . The quantum circuit update unit updates the quantum circuit using a greedy optimization method so that the "measurements" and "operations" are arranged as consecutively as possible.
3. The information processing device according to claim 1 or 2. 1. A method for simulating a Clifford circuit executed by an information processing device, comprising:
Updating the quantum circuit so as to improve the continuity of "measurement" and "operation" commands among the commands included in the input quantum circuit;
and simulating while switching the arrangement of each element of the stabilizer table in the memory based on the updated quantum circuit.
How to simulate. A program for causing a computer to function as each unit of an information processing device according to any one of claims 1 to 3.

Images