WO2024154265A1 - Quantum circuit design assistance program, quantum circuit design assistance method, and quantum circuit design assistance device - Google Patents

Abstract

The present invention makes it possible to ascertain whether quantum bits will take a prescribed value in a quantum computing process.　This quantum circuit design assistance device (10) sequentially assesses quantum gates in order of gate operation in a quantum circuit (1a), beginning with the earliest gate operation. The quantum circuit design assistance device (10) next assesses, on the basis of initial value information (1b) that indicates whether each of a plurality of quantum bits operated by the quantum circuit (1a) is a prescribed value in the initial state, whether the quantum bit being operated by the quantum gate being assessed will become a prescribed value after gate operation. The quantum circuit design assistance device (10) then identifies, for each quantum gate being assessed, a quantum bit that has become a prescribed value after gate operation by the quantum gate being assessed.

Description

Quantum circuit design support program, quantum circuit design support method, and quantum circuit design support device

The present invention relates to a quantum circuit design support program, a quantum circuit design support method, and a quantum circuit design support device.

The quantum computations to be executed by a quantum computer or quantum computer simulator (hereafter referred to as quantum simulator) are represented by quantum circuits. A quantum circuit is a quantum computation model that combines various types of quantum gates. A quantum gate represents an operation that rewrites the state of a quantum bit. There are basic quantum gates and other types of quantum gates used in quantum circuits. Basic quantum gates are quantum gates that can be executed by a quantum computer.

When creating a quantum circuit, a quantum circuit is first generated using a quantum circuit description language, which shows the gate operation procedures required to solve the target problem. Quantum circuits generated using the quantum circuit description language also use quantum gates that perform complex operations other than basic quantum gates. A classical computer then converts the quantum gates included in the quantum circuit, other than the basic quantum gates, into an equivalent quantum circuit (equivalent circuit) that combines basic quantum gates. This generates a quantum circuit described only with basic quantum gates.

In addition, when quantum gates other than basic quantum gates are converted into an equivalent circuit that combines basic quantum gates, the number of quantum gates increases. As the number of quantum gates in a quantum circuit increases, the efficiency of quantum computation by a quantum computer or quantum simulator decreases. Also, in a quantum computer, there is a limit to the time that a quantum bit can maintain a quantum state. Therefore, the probability of successful quantum computation increases when the number of basic quantum gates in a quantum circuit is reduced. For these reasons, when converting quantum gates other than basic quantum gates into an equivalent circuit, it is desirable to convert them into an equivalent circuit that uses fewer basic quantum gates.

Technologies related to quantum circuits have been proposed, for example, for optimizing quantum circuits to program quantum computers in a way that efficiently and cost-effectively exploits their inherent advantages in solving specific problems. Methods have also been proposed for handling continuous gate parameters in automated techniques for optimizing quantum circuits of the size and type expected for quantum computing. Training methods have also been proposed for training quantum neural networks such that, after training, they are capable of bidirectional quantum teleportation. Methods have also been proposed for optimizing quantum circuits for an ordered series of quantum gates that are applied to an initial layout of qubit values.

Special Publication No. 2022-521143 US Patent Application Publication No. 2021/0192113 JP 2022-071108 A US Patent Application Publication No. 2020/0242295

One technique for converting quantum gates other than basic quantum gates into equivalent circuits is the use of auxiliary quantum bits (auxiliary bits). There are two types of auxiliary bits: quantum bits whose state is known to be a specified value (for example, |0>) (clean auxiliary bits), and quantum bits whose state is unknown (dirty auxiliary bits). If there are a large number of clean auxiliary bits available, quantum gates other than basic quantum gates can be converted into quantum circuits with fewer quantum gates.

However, until now, there has been no technology to determine whether each quantum bit will be clean or dirty after a gate operation in a quantum computation process corresponding to a quantum circuit composed of multiple quantum gates. This makes it difficult to reduce the number of gates in a quantum circuit generated by converting quantum gates other than basic quantum gates into an equivalent circuit.

In one aspect, the present invention aims to make it possible to determine whether a quantum bit becomes a predetermined value during a quantum computing process.

In one proposal, a quantum circuit design support program is provided that causes a computer to execute the following processes.
The computer determines whether the quantum bit to be operated by the quantum gate to be determined will have a predetermined value after the gate operation based on initial value information indicating whether each of the multiple quantum bits operated by the quantum circuit has a predetermined value in the initial state.The computer then identifies, for each quantum gate to be determined, the quantum bit that has become the predetermined value after the gate operation by the quantum gate to be determined.

According to one aspect, it is possible to know whether or not a quantum bit becomes a predetermined value during a quantum computation process.
The above and other objects, features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings illustrating preferred embodiments of the present invention.

FIG. 1 is a diagram illustrating an example of a quantum circuit design support method according to a first embodiment. FIG. 1 illustrates an example of a system configuration according to a second embodiment; FIG. 1 is a diagram illustrating an example of a hardware configuration of a classical computer. FIG. 13 is a diagram showing an example of conversion to an equivalent circuit of a C ³ -NOT gate. FIG. 13 is a diagram showing an example of conversion to an equivalent circuit of a C ⁴ -NOT gate. FIG. 1 is a diagram showing an example of a quantum circuit using a plurality of C ^k -NOT gates. FIG. 13 shows an example of adding a clean quantum bit for the transformation of a C ^k -NOT gate. FIG. 2 is a diagram illustrating an example of a state transition of a quantum bit. FIG. 2 is a block diagram showing an example of functions of each device. 1 is a flowchart showing an example of a procedure for executing quantum computation involving optimization of a quantum circuit. 13 is a flowchart illustrating an example of a procedure for a clean bit update process. FIG. 13 is a diagram illustrating an example of initial information setting by a clean bit update process. FIG. 13 is a diagram illustrating an example of a state transition of tmpCleanBitList. FIG. 13 is a diagram illustrating an example of a correspondence relationship between the number of available auxiliary bits and an applicable conversion method. FIG. 13 is a diagram showing an example of an equivalent circuit of a C ⁷ -NOT gate according to the first conversion method. FIG. 13 is a diagram showing an example of an equivalent circuit of a C ⁷ -NOT gate according to the second conversion method. FIG. 13 is a diagram showing an example of an equivalent circuit of a C ⁷ -NOT gate according to the third conversion method. FIG. 13 is a diagram showing an example of an equivalent circuit of a C ⁷ -NOT gate according to the basic approach of the fourth conversion method. FIG. 13 is a diagram showing a first example of an equivalent circuit of a C ⁷ -NOT gate according to the fourth transformation scheme when there are less than k−2 clean bits. FIG. 13 is a diagram showing a second example of an equivalent circuit of a C ⁷ -NOT gate according to the fourth transformation scheme when there are less than k−2 clean bits. FIG. 13 is a diagram showing an example of division according to the fourth transformation method when c=2. FIG. 13 is a diagram showing an example of division according to the fourth transformation method when c=3. FIG. 13 is a diagram illustrating an example of functions of a quantum gate conversion unit. 13 is a flowchart illustrating an example of a procedure for a quantum gate conversion process. 13 is a flowchart illustrating an example of a procedure for a division method determination process. 13 is a flowchart illustrating an example of a procedure for an equivalent circuit generation process in a fourth conversion method. 13 is a flowchart (1/2) showing an example of a procedure for C ^k_i -NOT gate conversion processing. 13 is a flowchart (2/2) showing an example of a procedure for C ^k_i -NOT gate conversion processing. FIG. 13 is a diagram showing an example of transformation of a C ^k -NOT gate.

Hereinafter, the present embodiment will be described with reference to the drawings. Note that each embodiment can be implemented in combination with a plurality of other embodiments as long as no contradiction occurs.
First Embodiment
The first embodiment is a quantum circuit design support method that supports the design of a quantum circuit by determining whether or not a quantum bit becomes a predetermined value during a quantum computation process.

FIG. 1 is a diagram showing an example of a quantum circuit design support method according to a first embodiment. FIG. 1 shows a quantum circuit design support device 10 that realizes the quantum circuit design support method. The quantum circuit design support device 10 can implement the quantum circuit design support method, for example, by executing a quantum circuit design support program.

The quantum circuit design support device 10 has a memory unit 11 and a processing unit 12. The memory unit 11 is, for example, a memory or storage device that the quantum circuit design support device 10 has. The processing unit 12 is, for example, a processor or arithmetic circuit that the quantum circuit design support device 10 has.

The storage unit 11 stores quantum circuit 1a to be executed by a quantum computer or quantum simulator, and initial value information 1b indicating whether each of the multiple quantum bits operated by quantum circuit 1a has a predetermined value in the initial state. Quantum circuit 1a includes multiple quantum gates 2 to 6. In the example of Figure 1, the number of quantum bits operated by quantum circuit 1a is seven.

In the quantum circuit 1a, it is shown that a gate operation according to quantum gates 2 to 4 is performed as the X-1th gate operation (X is a natural number). Each of the quantum gates 2 to 4 is a Hadamard gate that operates on the fifth to seventh quantum bits. In addition, in the quantum circuit 1a, it is shown that a gate operation according to quantum gate 5 is performed as the Xth gate operation. The quantum gate 5 is a Hadamard gate for the fifth quantum bit. In addition, in the quantum circuit 1a, it is shown that a gate operation according to quantum gate 6 is performed as the X+1th gate operation. The quantum gate 6 is a C ³ -NOT gate that uses the first to third quantum bits as control bits and the fourth quantum bit as a target bit.

The C ³ -NOT gate is a quantum gate that inverts a control bit when all three control bits are |1>. The superscript of C indicates the number of control bits. This type of quantum gate is called MPMCT (Mixed-Polarity Multiple-Control Toffoli).

The processing unit 12 determines, based on the quantum circuit 1a and the initial state of each of the multiple quantum bits operated by the quantum circuit 1a, whether the quantum bit to be operated will have a predetermined value after a gate operation on the quantum bit to be operated by the first quantum gate included in the quantum circuit 1a. The initial state of each of the multiple quantum bits is, for example, a state in which the values of all quantum bits are |0>. Furthermore, the predetermined value for the quantum bit to be operated is, for example, |0>.

The processing unit 12, for example, judges the quantum gates in the quantum circuit 1a in order of the gate operation, and judges whether the quantum bit to be operated becomes a predetermined value after the gate operation on the quantum bit to be operated based on the initial value information 1b.

Furthermore, for each quantum gate to be judged, the processing unit 12 identifies a quantum bit that has become a predetermined value after the gate operation by the quantum gate to be judged. For example, the processing unit 12 generates a list of the identified quantum bits. Specifically, the processing unit 12 generates the list based on whether the quantum bit to be operated by the quantum gate to be judged becomes a predetermined value after the gate operation, and whether the quantum bits other than the quantum bit to be operated are a predetermined value before the gate operation. That is, the processing unit 12 includes the identification numbers of the quantum bits that have been at a predetermined value before the gate operation by the quantum gate to be judged and are not the object of operation by the quantum gate to be judged in the list corresponding to the quantum gate to be judged. The processing unit 12 also includes the identification numbers of the quantum bits that become a predetermined value by the gate operation according to the quantum gate to be judged in the list corresponding to the quantum gate to be judged. Furthermore, the processing unit 12 excludes the identification numbers of the quantum bits for which it is unclear whether they become a predetermined value after the gate operation according to the quantum gate to be judged from the list corresponding to the quantum gate to be judged.

In this way, for each quantum gate, a list of quantum bits that will become a predetermined value after gate operation by that quantum gate can be generated. For example, by generating a list of quantum bits whose value is |0>, the processing unit 12 can effectively use the quantum bits whose value is |0> as auxiliary bits to convert the next quantum gate to be executed into an equivalent circuit with a smaller number of gates. In other words, when converting the quantum circuit 1a into a quantum circuit that can be executed by a quantum computer or quantum simulator, the processing unit 12 can reduce the number of quantum gates in the quantum circuit after conversion. As a result, the quantum computer or quantum simulator can perform efficient quantum calculations.

For example, if the gate operation by the quantum gate to be judged is a gate operation that changes the state of the quantum bit to be manipulated to a predetermined value, the processing unit 12 judges that the quantum bit to be manipulated will have a predetermined value after the gate operation. Furthermore, if the gate operation by the quantum gate to be judged is an operation other than an operation that changes the state of the quantum bit to be manipulated to a predetermined value, the processing unit 12 judges that it is unclear whether the predetermined value will be obtained after the gate operation. For example, the user specifies in advance to the processing unit 12 a quantum gate that indicates a gate operation that changes the state of the quantum bit to be manipulated to a predetermined value. The processing unit 12 determines that the gate operation of the specified quantum gate is a gate operation that changes the state of the quantum bit to be manipulated to a predetermined value.

Furthermore, for example, when the quantum gate to be judged is a SWAP gate, the processing unit 12 judges that the states of the two quantum bits to be operated by the SWAP gate will be swapped. That is, the processing unit 12 judges that when the first quantum bit to be operated by the SWAP gate is a predetermined value before the gate operation by the quantum gate to be judged, the second quantum bit to be operated will be a predetermined value after the gate operation. In this case, the processing unit 12 includes the second quantum bit in the list.

Furthermore, when it is unclear whether the first quantum bit to be operated by the SWAP gate has a predetermined value before the gate operation by the quantum gate to be determined, the processing unit 12 determines that it is unclear whether the second quantum bit to be operated will have a predetermined value after the gate operation. In this case, the processing unit 12 excludes the second quantum bit from the list.

In this way, even if the quantum circuit 1a includes a SWAP gate, the processing unit 12 can appropriately generate a list of quantum bits that will become a predetermined value after gate operation by the SWAP gate.

The generated list can be used, for example, in a process of converting a complex quantum gate into an equivalent circuit composed of basic quantum gates. For example, the processing unit 12 identifies a third quantum bit that is a predetermined value after the gate operation of the first quantum gate based on the list generated when the first quantum gate is the quantum gate to be judged. The processing unit 12 then converts the second quantum gate to be executed after the first quantum gate into a quantum circuit equivalent to the second quantum gate, using the third quantum bit. This allows the quantum gate of the predetermined value to be used as an auxiliary bit, and the second quantum gate is converted into an equivalent circuit with a smaller number of quantum gates.

In quantum circuit 1a shown in Figure 1, the quantum bits whose state is the specified value |0> after the X-2th gate operation are the fourth to seventh quantum bits. In this case, it is unclear whether the first to third quantum bits are |0> after the X-2th gate operation.

The list of |0> quantum bits after the X-2th gate operation is {4, 5, 6, 7}. In quantum circuit 1a, gate operations are performed by quantum gates 2 to 4 (Hadamard gates) as the X-1th gate operation. For the fifth to seventh quantum bits, which are operated by quantum gates 2 to 4, it is unclear whether their values are |0> after the gate operation. Therefore, {5, 6, 7} is excluded from the list {4, 5, 6, 7} after the X-2th gate operation. As a result, the list of |0> quantum bits after the X-1th gate operation is {4}.

In quantum circuit 1a, a gate operation by quantum gate 5 (Hadamard gate) is performed as the Xth gate operation. In this case, the fifth quantum bit has had two gate operations by the Hadamard gate performed from |0>. As a result, the fifth quantum bit returns to |0> by the gate operation of quantum gate 5. Therefore, {5} is added to the list {4} after the Xth gate operation. As a result, the list of quantum bits of |0> after the Xth gate operation becomes {4, 5}.

In the X+1th gate operation, a quantum gate (C ³ -NOT gate) is operated. In many cases, the C ³ -NOT gate is not a basic quantum gate. Therefore, the C ³ -NOT gate is converted into an equivalent circuit that combines C ² -NOT gates. In the conversion to an equivalent circuit of the C ³ -NOT gate, if a quantum bit of |0> can be used as an auxiliary bit, it is possible to convert it into an equivalent circuit with fewer quantum gates than when a quantum bit with an unknown value is used as an auxiliary bit. Since the processing unit 12 has generated a list of quantum bits of |0> {4, 5} after the Xth gate operation, it is possible to recognize that the fifth quantum bit is |0> and use that quantum bit as an auxiliary bit. As a result, the processing unit 12 can convert the quantum gate 6 into an equivalent circuit with the minimum number of quantum gates.

In addition, in the X+1th gate operation, it is unclear whether the value of the fourth quantum bit, which is the target bit, is |0> after the X+1th gate operation. Therefore, {4} is deleted from the list {4, 5} after the Xth gate operation. As a result, the list of quantum bits with |0> after the X+1th gate operation becomes {5}.

Second Embodiment
The second embodiment is a computer system that converts a quantum gate that performs complex gate operations in a quantum circuit into a basic quantum gate and causes a quantum computer to execute quantum calculations according to a quantum circuit composed only of basic quantum gates. Hereinafter, a quantum bit whose value is known to be |0> is called a clean quantum bit or clean bit. Also, a quantum bit whose value is unknown whether it is |0> or not is called a dirty quantum bit or dirty bit.

FIG. 2 is a diagram showing an example of a system configuration of the second embodiment. The system includes a classical computer 100 and a quantum computer 200. Terminals 31, 32, ... are connected to the classical computer 100 via a network 20. The terminals 31, 32, ... are computers used by users who request quantum computing by the quantum computer 200. The classical computer 100 accepts quantum circuits from the terminals 31, 32, .... A quantum circuit indicates the order of operations on quantum bits by the arrangement of elements such as gates. A quantum bit is a bit that can express a superposition state of the |0> state and the |1> state.

The classical computer 100 converts the quantum circuits received from the terminals 31, 32, ... into quantum circuits that can be executed by the quantum computer 200. A quantum circuit that can be executed by the quantum computer 200 is, for example, a quantum circuit described using only basic quantum gates. The classical computer 100 instructs the quantum computer 200 to execute the converted quantum circuit. In addition, the classical computer 100 obtains the measurement results of each quantum bit from the quantum computer 200.

Quantum computer 200 has multiple quantum bits and a device for manipulating each of the multiple quantum bits. The multiple quantum bits of quantum computer 200 may be, for example, of a superconducting type or an ion trap type. The multiple quantum bits may also be of a diamond spin type. If the quantum bits are of a superconducting type, quantum computer 200 may have a refrigerator for cooling the quantum bits.

The quantum computer 200 irradiates the quantum bits with microwaves, for example, in response to instructions from the classical computer 100. In addition, a device for manipulating each of the multiple quantum bits measures the state of each of the multiple quantum bits and transmits the state to the classical computer 100.

Figure 3 is a diagram showing an example of the hardware configuration of a classical computer. In the classical computer 100, the entire device is controlled by a CPU (Central Processing Unit) 101. The CPU 101 is a processor that executes program instructions. The CPU 101 may include multiple processor cores. The CPU 101 may also be multiple processors, such as an MPU (Micro Processing Unit) or a DSP (Digital Signal Processor). At least a part of the functions realized by the CPU 101 executing a program may be realized by electronic circuits such as an ASIC (Application Specific Integrated Circuit) or a PLD (Programmable Logic Device). A RAM (Random Access Memory) 102 and multiple peripheral devices are connected to the CPU 101 via a bus 100a.

RAM 102 is the main storage device of classical computer 100. RAM 102 temporarily stores at least a portion of the OS (Operating System) program and application programs to be executed by CPU 101. RAM 102 also stores various data used for processing by CPU 101. Note that classical computer 100 may be equipped with a type of memory other than RAM, or may be equipped with multiple memories.

The peripheral devices connected to bus 100a include a HDD (Hard Disk Drive) 103, a GPU (Graphics Processing Unit) 104, an input interface 105, an optical drive device 106, device connection interfaces 107 and 108, and a network interface 109.

The HDD 103 is an auxiliary storage device for the classical computer 100. The HDD 103 magnetically writes and reads data to the built-in magnetic disk. The HDD 103 stores the OS program, application programs, and various data. Note that the classical computer 100 may be equipped with other types of auxiliary storage devices, such as flash memory or an SSD (Solid State Drive), or may be equipped with multiple auxiliary storage devices.

The monitor 21 is connected to the GPU 104. The GPU 104 displays images on the screen of the monitor 21 in accordance with commands from the CPU 101. The monitor 21 may be a display device using an organic EL (Electro Luminescence) display device or a liquid crystal display device.

The input interface 105 is connected to the keyboard 22 and mouse 23. The input interface 105 transmits signals sent from the keyboard 22 and mouse 23 to the CPU 101. Note that the mouse 23 is an example of a pointing device, and other pointing devices can also be used. Other pointing devices include a touch panel, a tablet, a touch pad, a trackball, etc.

The optical drive device 106 uses laser light or the like to read data recorded on the optical disc 24. The optical disc 24 is a portable recording medium on which data is recorded so that it can be read by the reflection of light. Optical discs 24 include DVDs (Digital Versatile Discs), DVD-RAMs, CD-ROMs (Compact Disc Read Only Memory), and CD-Rs (Recordable)/RWs (ReWritable), etc.

The device connection interface 107 is a communication interface for connecting peripheral devices to the classical computer 100. For example, a memory device 25 or a memory reader/writer 26 can be connected to the device connection interface 107. The memory device 25 is a recording medium equipped with a communication function with the device connection interface 107. The memory reader/writer 26 is a device that writes data to the memory card 27 or reads data from the memory card 27. The memory card 27 is a card-type recording medium.

The device connection interface 108 is a communication interface for connecting the quantum computer 200 to the classical computer 100. The classical computer 100 transmits instructions for controlling quantum bits to the quantum computer 200 via the device connection interface 108.

The network interface 109 is connected to the network 20. The network interface 109 transmits and receives data to and from other computers or communication devices via the network 20.

The classical computer 100 can realize the processing functions of the second embodiment with the hardware configuration described above. The quantum circuit design support device 10 shown in the first embodiment can also be realized with hardware similar to that of the classical computer 100 shown in FIG. 3. The CPU 101 is an example of the processing unit 12 shown in the first embodiment.

The classical computer 100 realizes the processing functions of the second embodiment by executing a program recorded on, for example, a computer-readable recording medium. The program describing the processing to be executed by the classical computer 100 can be recorded on various recording media. For example, the program to be executed by the classical computer 100 can be stored on the HDD 103. The CPU 101 loads at least a part of the program in the HDD 103 into the RAM 102 and executes the program. The program to be executed by the classical computer 100 can also be recorded on a portable recording medium such as the optical disk 24, memory device 25, or memory card 27. The program stored on the portable recording medium becomes executable after being installed on the HDD 103 under the control of, for example, the CPU 101. The CPU 101 can also read and execute the program directly from the portable recording medium.

In the above system, the classical computer 100 acquires from the terminals 31, 32, ... a quantum circuit that describes the procedure for gate operations of quantum bits for quantum computation. The quantum circuits acquired from the terminals 31, 32, ... include quantum gates that perform complex operations other than basic quantum gates. On the other hand, gate operations in the quantum computer 200 are limited to gate operations of basic quantum gates. Therefore, the classical computer 100 converts the quantum gates other than the basic quantum gates included in the quantum circuits acquired from the terminals 31, 32, ... into equivalent circuits that use basic quantum gates that can be executed by the quantum computer 200. The classical computer 100 then instructs the quantum computer 200 to perform quantum computation using the converted quantum circuits.

What kind of quantum gate is the basic quantum gate varies depending on the system. In the system according to the second embodiment, among the one-qubit gates, the basic quantum gates include the Hadamard gate, the NOT gate, and the rotation gate. Among the two-qubit gates, the basic quantum gates include the C-NOT gate and the controlled rotation gate. Furthermore, among the three-qubit gates, the basic quantum gate includes the C ² -NOT gate.

Among quantum gates that perform complex gate operations other than basic quantum gates, a frequently used quantum gate is the C ^k -NOT gate (k is an integer equal to or greater than 3). The C ^k -NOT gate is a quantum gate that inverts the "0/1" of a target bit when all k control bits are |1>.

The gate operation of the C ^k -NOT gate can be replaced with an equivalent quantum circuit composed of a minimum number of C ² -NOT gates depending on the number of clean auxiliary bits and dirty auxiliary bits.

FIG. 4 is a diagram showing an example of conversion of a C ³ -NOT gate into an equivalent circuit. The C ³ -NOT gate 41 has three quantum bits, "c ₁ " to "c ₃ ", as control bits and a quantum bit, "x", as a target quantum bit. The C ³ -NOT gate 41 can be converted into an equivalent circuit 42 if clean auxiliary bits can be used. The equivalent circuit 42 is made up of three C ² -NOT gates 42a to 42c. The C ³ -NOT gate 41 can be converted into an equivalent circuit 43 if clean auxiliary bits cannot be used but dirty auxiliary bits can be used. The equivalent circuit 43 is made up of four C ² -NOT gates 43a to 43d.

In this way, if clean auxiliary bits can be used, the C ³ -NOT gate 41 can be converted into three C ² -NOT gates 42a to 42c. In contrast, if only dirty auxiliary bits can be used, the C ³ -NOT gate 41 will be converted into four C ² -NOT gates 43a to 43d. In other words, if clean auxiliary bits can be used, the number of quantum gates in the quantum circuit after conversion can be reduced.

FIG. 5 is a diagram showing an example of conversion of a C ⁴ -NOT gate into an equivalent circuit. The C ⁴ -NOT gate 44 has four quantum bits, "c ₁ " to "c ₄ ", as control bits and a quantum bit, "x", as a target quantum bit. The C ⁴ -NOT gate 44 can be converted into an equivalent circuit 45 if two clean auxiliary bits can be used. The equivalent circuit 45 is composed of five C ² -NOT gates 45a to 45e. The C ⁴ -NOT gate 44 can be converted into an equivalent circuit 46 if one clean auxiliary bit and one dirty auxiliary bit can be used. The equivalent circuit 46 is composed of six C ² -NOT gates 46a to 46f. The C ⁴ -NOT gate 44 can be converted into an equivalent circuit 47 if no clean auxiliary bit can be used and two dirty auxiliary bits can be used. The equivalent circuit 47 is made up of eight C ² -NOT gates 47a to 47h.

In this way, if two clean auxiliary bits can be used, the C ⁴ -NOT gate 44 can be converted into five C ² -NOT gates 45a to 45e. If only one clean auxiliary bit can be used, the C ⁴ -NOT gate 44 will be converted into six C ² -NOT gates 46a to 46f. Furthermore, if only dirty auxiliary bits can be used, the C ⁴ -NOT gate 44 will be converted into eight C ² -NOT gates 47a to 47h. In other words, the more clean auxiliary bits that can be used, the more the number of quantum gates in the quantum circuit after conversion can be reduced.

As shown in Figures 4 and 5, if a clean quantum bit is known, it is possible to convert a C ^k -NOT gate into an equivalent circuit with a smaller number of gates by using that quantum bit as an auxiliary bit. To do this, it is important to manage which quantum bits are in a clean state.

When a quantum circuit includes multiple quantum gates, if it is not possible to manage which quantum bits are clean, the states of all quantum bits can only be treated as dirty. As a result, a C ³ -NOT gate is converted to an equivalent circuit 43 (see FIG. 4), and a C ⁴ -NOT gate is converted to an equivalent circuit 47 (see FIG. 5).

If the number of quantum gates other than basic quantum gates contained in a quantum circuit were small, this would not be a big problem, but quantum circuits generated using circuit description languages often contain a large number of quantum gates other than basic quantum gates.

FIG. 6 is a diagram showing an example of a quantum circuit using multiple C ^k -NOT gates. The quantum circuit 48 shows a quantum calculation in which, for the quantum bit of "x ₁ " and the quantum bit of "x ₂ ", when "x ₁ =x ₂ =1", "211" is added to a numerical value (binary notation) represented by the quantum bit string "q=q ₈ , ..., q ₀ ". The quantum circuit 48 uses a large number of C ^k -NOT gates. In this case, if it is not known which quantum bit is clean, all the C ^k -NOT gates are converted into equivalent circuits with a large number of gates. As a result, the number of quantum gates in the entire quantum circuit after conversion increases significantly.

Specifically, quantum circuit 48 includes 11 C ² -NOT gates, 16 C ³ -NOT gates, and 13 C ⁴ -NOT gates. Of these, the 16 C ³ -NOT gates are converted into 64 C ² -NOT gates by equivalent circuit 43. Furthermore, the 13 C ⁴ -NOT gates are converted into 104 C ² -NOT gates by equivalent circuit 47. As a result, a quantum circuit is generated that shows gate operations by 179 C ² -NOT gates for 18 quantum bits.

If there is a shortage of clean auxiliary bits, C ^k -NOT can be converted into an equivalent circuit 45 composed of a minimum number of C ² -NOT gates if the required number of clean quantum bits can be added.

FIG. 7 is a diagram showing an example of adding clean quantum bits to convert a C ^k -NOT gate. In the quantum circuit 49, two clean quantum bits are added. If the added quantum bits are used as auxiliary bits, each C ^k -NOT can be converted into an equivalent circuit composed of a minimum number of C ² -NOT gates. In this case, the number of quantum bits used to execute the quantum circuit increases because clean quantum bits are added. There is a limit to the number of quantum bits that can be used in a quantum computer. Therefore, if the number of quantum bits used increases, there is a possibility that the quantum computer cannot execute the quantum circuit after conversion.

Specifically, the 16 C ³ -NOT gates included in the quantum circuit 49 are converted into 48 C ² -NOT gates by the equivalent circuit 42. The 13 C ⁴ -NOT gates are converted into 65 C ² -NOT gates by the equivalent circuit 45. As a result, a quantum circuit is generated that shows gate operations by 124 C ² -NOT gates for 20 quantum bits. In this way, if clean quantum bits are added as auxiliary bits, the number of quantum gates after conversion can be reduced, but the number of quantum bits increases. As a result, there is a risk that the quantum circuit cannot be executed due to a shortage of available quantum bits.

Therefore, a clean bit management function is introduced to the classical computer 100, and the classical computer 100 manages whether the state after each gate operation for each quantum bit used in the quantum circuit is clean or dirty.

Generally, the initial state of each quantum bit is clean. Even if a quantum bit becomes dirty due to a subsequent gate operation, if a gate operation is performed that changes the state to |0>, the quantum bit will become clean.

FIG. 8 is a diagram showing an example of the state transition of a quantum bit. If the initial state of a quantum bit is |0>, then when the quantum circuit is input to quantum computer 200 (before gate operation), all quantum bits are clean. When the operation of a quantum gate in the quantum circuit input to quantum computer 200 is executed, the quantum bit that is the target bit of that quantum gate may be changed from clean to dirty. Even if the quantum bit has become dirty, when the state of that quantum bit is returned to |0> by a certain quantum gate, that quantum bit becomes clean.

For example, a quantum circuit 51 is arranged with a C ⁷ -NOT gate 51a and six Hadamard gates 51b to 51g. The C ⁷ -NOT gate 51a has seven quantum bits, "c ₁ " to "c ₇ ", as control bits and a quantum bit, "x", as a target quantum bit. If the states of all the control bits are |1>, the C ⁷ -NOT gate 51a inverts the state of the target bit (converts |0> to |1>, or |1> to |0>).

Hadamard gates 51b to 51f are arranged for the five quantum bits "a ₁ " to "a ₅ ", respectively. Furthermore, a Hadamard gate 51g is arranged for the quantum bit "a ₁ ".

In the quantum circuit 51, before the gate operation is applied, the states of all quantum bits are clean. After the gate operations of the Hadamard gates 51b to 51f are performed on the five quantum bits "a ₁ " to "a ₅ ", the states of these five quantum bits "a ₁ " to "a ₅ " change from clean to dirty quantum bits. When the second gate operation of the Hadamard gate 51g is performed on the quantum bit "a ₁ ", the state of the quantum bit "a ₁ " changes from dirty to clean.

In the example of quantum circuit 51, when the last C ⁷ -NOT gate 51a is converted into an equivalent circuit, the quantum bit “a ₁ ” can be used as a clean auxiliary bit, and the quantum bits “a ₂ ” to “a ₅ ” can be used as dirty auxiliary bits.

In this way, each quantum bit is initially clean, but becomes dirty when any gate operation is performed. Even if the quantum bit becomes dirty, if the same gate operation as before is performed again, the quantum bit will become clean.

In addition, when a SWAP gate is operated, the state of a dirty quantum bit may also change to clean. A SWAP gate is a quantum gate that performs an operation to exchange the states of two quantum bits. For example, one quantum bit operated by a SWAP gate may be in a clean state, while the other quantum bit may be in a dirty state. In this case, application of the SWAP gate changes the state of the clean quantum bit to dirty, and the state of the dirty quantum bit to clean.

The classical computer 100 uses its clean bit management function to change a clean quantum bit to dirty when a quantum gate operation is performed in which a clean quantum bit is the target bit. Also, when a SWAP gate operation is performed, the classical computer 100 swaps the states of both quantum bits that are the target of the operation. Furthermore, when a process is performed to set a dirty quantum bit to |0>, the classical computer 100 changes the quantum bit to clean.

Note that there are other gate operations besides the Hadamard gate that can return a quantum bit to a clean bit by performing two gate operations of a specific quantum gate on the clean bit. For example, if a NOT gate operation is performed twice on a clean bit, the quantum bit becomes a dirty bit after the first NOT gate operation, but returns to a clean bit after the second NOT gate operation.

With such a clean bit management function, the classical computer 100 can convert all C ^k -NOT gates appearing in the quantum circuit into optimal equivalent circuits according to the number of clean auxiliary bits and the number of dirty auxiliary bits without increasing the number of quantum bits. As a result, the calculation time in the quantum computer 200 can be reduced. This also applies when a quantum circuit simulator is used instead of the quantum computer 200.

FIG. 9 is a block diagram showing an example of the functions of each device. The terminal 31 has a quantum circuit generation unit 31a. The quantum circuit generation unit 31a generates a quantum circuit described in a circuit description language according to input from a user. The quantum circuit generated by the quantum circuit generation unit 31a also uses quantum gates other than basic quantum gates. The quantum circuit generation unit 31a transmits the generated quantum circuit to the classical computer 100.

The classical computer 100 has a quantum computation manager 110, a clean bit manager 120, and a quantum gate converter 130.
The quantum computing management unit 110 manages the execution of quantum computation according to the quantum circuit sent from the terminal 31. For example, when the quantum circuit sent from the terminal 31 contains a quantum gate other than a basic quantum gate, the quantum computing management unit 110 instructs the quantum gate conversion unit 130 to convert the quantum gate into an equivalent circuit. The quantum computing management unit 110 also instructs the management of the state (clean/dirty) of each quantum bit after operation by each quantum gate in the quantum circuit. When a quantum circuit described only by basic quantum gates is generated, the quantum computing management unit 110 instructs the quantum computer 200 to perform quantum computation based on the quantum circuit. Then, the quantum computing management unit 110 obtains the computation result from the quantum computer 200 and outputs the computation result to the terminal 31.

The clean bit manager 120 manages the state of the quantum bit that is being operated on in the quantum circuit. For example, the clean bit manager 120 interprets the operations performed by the quantum gates of the quantum circuit from the beginning, and determines whether the state of the operated quantum bit will be clean or dirty after the gate operation.

The quantum gate conversion unit 130 converts quantum gates other than the basic quantum gates contained in the quantum circuit into an equivalent circuit using only the basic quantum gates. In doing so, the quantum gate conversion unit 130 obtains the state of each quantum bit immediately before executing the quantum gate to be converted from the clean bit management unit 120. The quantum gate conversion unit 130 then identifies clean quantum bits and dirty quantum bits that can be used as auxiliary bits, and converts the quantum gate to be converted into the smallest equivalent circuit that effectively uses these quantum bits.

The functions of each element shown in FIG. 9 can be realized, for example, by causing a computer to execute a program module corresponding to that element.
Next, a procedure for performing quantum computation involving optimization of a quantum circuit will be described in detail.

10 is a flowchart showing an example of a procedure for performing quantum computation involving optimization of a quantum circuit. The process shown in FIG. 10 will be described below in order of step numbers.
[Step S101] The quantum computing manager 110 acquires a quantum circuit to be computed from one of the terminals 31, 32, .... Based on the acquired quantum circuit, the quantum computing manager 110 instructs the clean bit manager 120 to set information for clean bit management. The clean bit manager 120 then analyzes the specified quantum circuit and sets circuit information to be used for managing the clean bits. The circuit information to be set is, for example, the number of quantum bits n, the quantum circuit "QC", the initial state I, and cleaning information CI.

The number of quantum bits n is the number of quantum bits that appear in the quantum circuit. The number of quantum bits n is the minimum number of quantum bits required to execute the input quantum circuit.
A quantum circuit "QC" is information that lists {gate number, quantum gate configuration} in order. The quantum gate configuration is the type of quantum gate, the number of the quantum bit to be operated on, etc. For example, "QC" is information such as [{1, Hadamard gate for the first quantum bit}, {2, C ¹⁰ -NOT gate with 1st to 10th bits as control bits and 11th bit as the target bit}, ...].

The initial state I is a set of clean quantum bit numbers. For example, if the 1st, 2nd, and 10th quantum bits are clean, the initial state I is {1, 2, 10}.
The cleaning information CI is a set of identification numbers of quantum gates that make the state of the target bit clean when executed. For example, for the fifth quantum gate and the ninth quantum gate, if the state of the target bit after execution becomes clean, the cleaning information CI is {5, 9}. In the example of the quantum circuit 51 shown in FIG. 8, the identification number of the Hadamard gate 51g is set in the cleaning information CI.

[Step S102] The quantum computing manager 110 and the clean bit manager 120 generate the initial state of the information used to optimize the quantum circuit. For example, the clean bit manager 120 generates the initial state of the information used to manage the state changes of the quantum bits each time a gate operation is performed. The information used to manage the state changes of the quantum bits includes a list of clean quantum bits "cleanBitList", a list of dirty quantum bits "dirtyBitList", and the number of quantum gates "N" included in "QC".

The initial value of "cleanBitList" is the initial state I (cleanBitList = I). The initial value of "dirtyBitList" is the list of all quantum bits excluding the quantum bits included in the initial state I (dirtyBitList = {1, ..., n} - I). "N" is set to the maximum value of the quantum gate identification number shown in "QC".

In addition, the quantum computing manager 110 sets an initial value to a variable "i" that indicates the number of the quantum gate to be processed. For example, the initial value of "i" is "1" (i=1).
[Step S103] The quantum computing management unit 110 determines whether the conversion process to the equivalent circuit of quantum gates other than the basic quantum gates is completed based on whether the value of "i" is "N+1". For example, if "i==N+1", the quantum computing management unit 110 advances the process to step S110. If "i==N+1" is not true, the quantum computing management unit 110 advances the process to step S104.

[Step S104] The quantum gate conversion unit 130 determines whether the i-th quantum gate "QC[i]" of "QC" is to be converted into an equivalent circuit. Quantum gates to be converted into equivalent circuits are quantum gates other than basic quantum gates. If the quantum gate is to be converted into an equivalent circuit, the quantum gate conversion unit 130 proceeds to step S105. If the quantum gate is not to be converted into an equivalent circuit, the quantum gate conversion unit 130 proceeds to step S108.

[Step S105] The quantum gate conversion unit 130 creates a temporary list of clean quantum bits, "tmpCleanBitList", and a temporary list of dirty quantum bits, "tmpDirtyBitList". For example, the quantum gate conversion unit 130 deletes the identification numbers of the control bit and target bit of QC[i] from "cleanBitList" to create "tmpCleanBitList". The quantum gate conversion unit 130 also deletes the identification numbers of the control bit and target bit of QC[i] from "dirtyBitList" to create "tmpDirtyBitList".

[Step S106] The quantum gate conversion unit 130 performs a conversion process (quantum gate conversion) of QC[i] into an equivalent circuit of a quantum gate based on QC[i], "tmpCleanBitList", and "tmpDirtyBitList". The equivalent circuit obtained as a result of the quantum gate conversion is called "qc". Details of the quantum gate conversion process will be described later (see FIG. 24).

[Step S107] The quantum gate conversion unit 130 replaces QC[i] with the equivalent circuit “qc” generated by the quantum gate conversion process (QC[i]=qc).
[Step S108] The clean bit manager 120 performs a clean bit update process in response to the gate operation of QC[i]. The details of the clean bit update process will be described later (see FIG. 11).

[Step S109] The quantum computing manager 110 adds 1 to the variable “i” (i←i+1) and proceeds to step S103.
[Step S110] The quantum computation manager 110 instructs the quantum computer 200 to execute quantum computation based on the quantum circuit.

[Step S<b>111 ] The quantum computation manager 110 acquires a computation result from the quantum computer 200 .
[Step S112] The quantum computation manager 110 outputs the result of the quantum computation based on the quantum circuit.

In this way, a decision is made for each quantum gate as to whether or not to convert to an equivalent circuit, and if so, the circuit is converted to an equivalent circuit. Furthermore, each time processing is completed for one quantum gate, the state of each quantum bit after the gate operation by that quantum gate is updated. As a result, when converting to an equivalent circuit, the quantum gate conversion unit 130 can correctly determine which quantum bits are clean when performing the gate operation of the quantum gate to be converted, and can convert to an equivalent circuit with a smaller number of quantum gates depending on the number of clean quantum bits.

Next, the procedure for the clean bit update process will be described in detail.
Fig. 11 is a flow chart showing an example of the procedure of the clean bit update process. The process shown in Fig. 11 will be explained below in order of step numbers. Note that in the process of Fig. 11, the quantum gate of QC[i] indicates the i-th quantum gate before conversion, even if QC[i] has been converted to the equivalent circuit "qc".

[Step S201] The clean bit manager 120 determines whether the quantum gate to be processed, QC[i], has been converted to the equivalent circuit "qc". If it has been converted, the clean bit manager 120 proceeds to step S204. If it has not been converted, the clean bit manager 120 proceeds to step S202.

[Step S202] The clean bit management unit 120 determines whether the quantum gate of QC[i] is a SWAP gate. If it is a SWAP gate, the clean bit management unit 120 proceeds to step S203. If it is not a SWAP gate, the clean bit management unit 120 proceeds to step S204.

[Step S203] The clean bit manager 120 swaps the state of the quantum bit being operated on by the quantum gate being processed (SWAP gate). For example, if one of the identification numbers "j, k" of the quantum bit being operated on is included in "cleanBitList" and the other is included in "dirtyBitList", the clean bit manager 120 swaps the lists to which they belong.

Specifically, the clean bit manager 120 deletes the identification number ("j" or "k") of the quantum bit to be operated on that is included in the "cleanBitList" from the "cleanBitList" and adds it to the "dirtyBitList". The clean bit manager 120 also deletes the identification number ("j" or "k") of the quantum bit to be operated on that is included in the "dirtyBitList" from the "dirtyBitList" and adds it to the "cleanBitList".

When the state switching is completed, the clean bit manager 120 ends the clean bit update process.
[Step S204] The clean bit manager 120 determines whether or not the condition that the identification number [j] of the target bit in the quantum gate of QC[i] is included in "cleanBitList" and is not included in the cleaning information CI is satisfied. If the condition is satisfied, the clean bit manager 120 proceeds to step S205. If the condition is not satisfied, the clean bit manager 120 proceeds to step S206.

[Step S205] The clean bit manager 120 deletes the identification number [j] of the target bit in the quantum gate of QC[i] from the "cleanBitList" and adds it to the "dirtyBitList". After that, the clean bit manager 120 ends the clean bit update process.

[Step S206] The clean bit manager 120 determines whether the condition that the identification number [j] of the target bit in the quantum gate of QC[i] is included in "dirtyBitList" and also in the cleaning information CI is satisfied. If the condition is satisfied, the clean bit manager 120 proceeds to step S207. If the condition is not satisfied, the clean bit manager 120 ends the clean bit update process.

[Step S207] The clean bit manager 120 deletes the identification number [j] of the target bit in the quantum gate of QC[i] from the "dirtyBitList" and adds it to the "cleanBitList". After that, the clean bit manager 120 ends the clean bit update process.

In this way, the state of the quantum bit (clean or dirty) after each quantum gate operation is performed is appropriately managed.
Fig. 12 is a diagram showing an example of initial information setting by clean bit update processing. In the example of Fig. 12, it is assumed that quantum gates other than the basic quantum gates of the quantum circuit 48 shown in Fig. 6 are converted into equivalent circuits.

The quantum circuit 48 is a circuit that adds "211" to the quantum bit string " _q8 , ..., _q0 " (binary notation) when both quantum bits " _x1 " and " _x2 " are |1>. In the quantum circuit 48, seven clean quantum bits " _c1 , ..., _c7 " can be used as auxiliary bits.

The number of quantum bits used in quantum circuit 48 is 18, and n is set to 18. Among these quantum bits, the identification numbers of clean quantum bits "c ₁ , ..., c ₇ " are "4, 6, 8, 10, 12, 14, 16", respectively. Therefore, the initial state I is set to "I={4, 6, 8, 10, 12, 14, 16}".

Among the quantum gates included in quantum circuit 48, the seven quantum gates that perform the gate operation to change the state of the target bit to |0> are the ones in the order "20, 23, 27, 30, 32, 36, 39". Therefore, the cleaning information CI is set to "CI = {20, 23, 27, 30, 32, 36, 39}".

Before optimizing the quantum circuit, "cleanBitList = {4, 6, 8, 10, 12, 14, 16}" is generated, which has the same contents as the initial state I. Also, "dirtyBitList = {1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 18}" is generated, which indicates dirty quantum bits.

Since the quantum circuit 48 includes 40 quantum gates, the number of gates is set to "N=40".
The "cleanBitList" and "dirtyBitList" are updated each time a quantum gate is converted into an equivalent circuit and converted into an equivalent circuit. When a quantum gate is converted into an equivalent circuit, a "tmpCleanBitList" is generated based on the "cleanBitList" at that time. The "tmpCleanBitList" indicates quantum bits that can be used as clean auxiliary bits in the equivalent circuit of the corresponding quantum gate. The "tmpDirtyBitList" is generated based on the "dirtyBitList". The "tmpDirtyBitList" indicates quantum bits that can be used as dirty auxiliary bits in the equivalent circuit of the corresponding quantum gate.

FIG. 13 shows an example of the state transition of tmpCleanBitList. The labels of each column in state transition table 52 for tmpCleanBitList indicate the quantum gate number. The labels of each row in state transition table 52 for "tmpCleanBitList" indicate quantum bits.

In state transition table 52, the column corresponding to a quantum gate shows the state (clean or dirty) of the quantum bit before the operation by that quantum gate. A quantum bit set as "control" is the control bit of the corresponding quantum gate. A quantum bit set as "t" is the target bit of the corresponding quantum gate. A quantum bit set as "c" is a clean quantum bit, and the identification number of that quantum bit is included in "tmpCleanBitList". A quantum bit with a blank setting is a dirty quantum bit, and the identification number of that quantum bit is included in "tmpDirtyBitList".

12 and 13, there are a sufficient number of dirty bits that can be used as auxiliary bits. Therefore, the type of equivalent circuit to which the C ^k -NOT gate is converted is determined according to the number of clean bits that can be used.

Of the quantum gates in the quantum circuit 48, the C ² -NOT gate does not require conversion. The quantum gates that do not require conversion are 11 in total: 3, 8, 12, 15, 19, 21, 26, 28, 35, 37, and 40.

Among the C ³ -NOT gates, those that can use at least one clean bit as an auxiliary bit can be converted into an equivalent circuit 42 (see FIG. 4). There are a total of 12 C ³ -NOT gates that can use at least one clean bit: "1, 2, 7, 22, 24, 27, 29, 31, 33, 36, 38, 39." As the equivalent circuit 42 includes three quantum gates, the total number of quantum gates after conversion is 36 (12 x 3).

Among the C ³ -NOT gates, those which cannot use any clean bits are converted to an equivalent circuit 43 (see FIG. 4). There are a total of four C ³ -NOT gates which cannot use any clean bits: "11, 14, 17, 20". As the equivalent circuit 43 includes four quantum gates, the total number of quantum gates after conversion is 16 (4×4).

Among the C ⁴ -NOT gates, those that can use at least two clean bits as auxiliary bits can be converted into an equivalent circuit 45 (see FIG. 5). There are a total of eight C ⁴ -NOT gates that can use at least two clean bits: "4, 5, 6, 9, 25, 30, 32, 34." As the equivalent circuit 45 includes five quantum gates, the total number of quantum gates after conversion is 40 (5 x 8).

Among the C ⁴ -NOT gates, those that can use only one clean bit can be converted to an equivalent circuit 46 (see FIG. 5). There are two C ⁴ -NOT gates that can use only one clean bit, "10, 23". As the equivalent circuit 46 includes six quantum gates, the total number of quantum gates after conversion is 12 (6×2).

Among the C ⁴ -NOT gates, those which cannot use any clean bits are converted to an equivalent circuit 47 (see FIG. 5). There are three C ⁴ -NOT gates which cannot use any clean bits: "13, 16, 18". As the equivalent circuit 47 includes eight quantum gates, the total number of quantum gates after conversion is 24 (8×3).

As a result, when the quantum circuit 48 is converted into a quantum gate consisting of only basic quantum gates, the total number of basic quantum gates becomes "11+36+16+40+12+24=139".
As described above, when the clean bits are not managed, all the C ³ -NOT gates are converted to the equivalent circuit 43, and all the C ⁴ -NOT gates are converted to the equivalent circuit 47. In this case, the total number of basic quantum gates in the quantum circuit after the conversion is 179. That is, by managing the clean bits, the number of quantum gates in the quantum circuit is reduced from 179 to 139.

Next, the conversion process to an equivalent circuit of a quantum gate other than a basic quantum gate will be described in detail.
First, a method of conversion to an applicable equivalent circuit according to the number of usable clean auxiliary bits and dirty auxiliary bits will be described.

FIG. 14 is a diagram showing an example of the correspondence between the number of available auxiliary bits and applicable conversion methods. Conversion method application table 60 shows applicable conversion methods according to the number of clean bits and the number of dirty bits. The horizontal axis of conversion method application table 60 is the number of available clean bits, and the vertical axis is the number of available dirty bits.

The first conversion method is a conversion method capable of converting into an equivalent circuit with the smallest number of quantum gates. The first conversion method is a conversion method capable of converting a C ^k -NOT gate into 2k-3 C ² -NOT gates using k-2 clean auxiliary bits. The first conversion method results in a smaller number of quantum gates after conversion than the other conversion methods described below. On the other hand, the first conversion method can only be applied when k-2 or more clean bits are available. Therefore, the quantum gate conversion unit 130 applies the first conversion method when k-2 clean auxiliary bits are available.

The second conversion method is a conversion method that converts into an equivalent circuit using clean or dirty auxiliary bits. In the second conversion method, a C ^k -NOT gate can be converted into 4k-8 C ² -NOT gates using k-2 auxiliary bits. In the second conversion method, all auxiliary bits can be applied even if they are dirty, and it is highly versatile. On the other hand, when the auxiliary bits are insufficient, it is required to add quantum bits to be used as auxiliary bits until the auxiliary bits (the sum of clean bits and dirty bits) become k-2. In addition, the second conversion method increases the number of gates by 2k-5 compared to the first conversion method.

The third conversion method is a conversion method that converts to an equivalent circuit using one auxiliary bit (clean bit or dirty bit). The third conversion method allows conversion with a small number of auxiliary bits. On the other hand, the number of gates increases by 4k to 6k compared to the first or second conversion method.

The fourth conversion method is a conversion method that can compensate for the shortcomings of the first, second, and third conversion methods. The fourth conversion method is a conversion method that can convert into an equivalent circuit with a smaller number of quantum gates by effectively using available auxiliary bits when at least one clean bit is available. The fourth conversion method can be applied without adding auxiliary bits even when there are fewer than k-2 clean bits, and can compensate for the shortcomings of the first conversion method that uses k-2 or more clean bits. The fourth conversion method can also convert into an equivalent circuit with a smaller number of quantum gates than the second and third conversion methods, and can compensate for the shortcoming of the second and third conversion methods that the number of quantum gates is increased.

When k-2 or more clean bits are available, the first conversion method can be used to convert to an equivalent circuit with the minimum number of quantum gates. Therefore, the fourth conversion method is effective when the number of clean bits c is "1≦c≦k-3".

For example, assume that there is one clean bit (c=1) and four dirty bits (d=4) as auxiliary bits that can be used when converting the C ⁷ -NOT gate 61 into an equivalent circuit.

15 is a diagram showing an example of an equivalent circuit of a C ⁷ -NOT gate according to the first conversion method. The C ⁷ -NOT gate 61 has seven control bits. In this case, the number of clean bits used in the first conversion method is five. Therefore, four clean bits are insufficient. In other words, to convert the C ⁷ -NOT gate 61 using the first conversion method, four clean bits are added.

When five clean bits can be used as auxiliary bits, an equivalent circuit 62 can be generated by the first conversion method. Sets of control bits are generated starting from the most significant control bit, and for each set, the result of the C ² -NOT gate is set as the clean bit. The clean bit to which the operation result is set is also used as the control bit, and a similar gate operation is repeated. Then, the sixth C ² -NOT gate performs the same operation as that by the C ⁷ -NOT gate 61 on the target bit.

The latter five C ² -NOT gates are quantum gates that clean the ancillary bits that were previously clean bits. Due to the presence of these C ² -NOT gates, the equivalent circuit 62, including the state of the ancillary bits after the gate operation, becomes equivalent to the C ⁷ -NOT gate 61.

In the equivalent circuit 62, dirty bits are not used. Therefore, the dirty bits are wasted. Also, because clean bits are added, the number of quantum bits used increases. Furthermore, in order to apply the first conversion method, it is necessary that 17 quantum bits are available. If there are not enough extra quantum bits available in the quantum computer 200, the first conversion method cannot be applied.

16 is a diagram showing an example of an equivalent circuit of a C ⁷ -NOT gate by the second conversion method. When the second conversion method is applied to the C ⁷ -NOT gate 61, k-2 (5) auxiliary bits are used. Therefore, by treating the clean bits as equivalent to the dirty bits, the C ⁷ -NOT gate 61 can be converted into an equivalent circuit 63 by the second conversion method.

In the equivalent circuit 63, the first five C ² -NOT gates use a pair of an auxiliary bit (clean bit or dirty bit) and the control bit of the C ⁷ -NOT gate 61 as the control bit of the corresponding C ² -NOT gate. There is no overlap in the control bits of the first five C ² -NOT gates. The target bit of the first C ² -NOT gate is the target bit of the C ⁷ -NOT gate 61. The target bits of the second to fifth C ² -NOT gates are the auxiliary bits used as the control bit in the immediately preceding C ² -NOT gate. The control bit of the sixth C ² -NOT gate is the control bit of the C ⁷ -NOT gate 61 that is not used in the first five C ² -NOT gates. The target of the sixth C ² -NOT gate is the auxiliary bit used as the control bit in the fifth C ² -NOT gate.

The seventh to eleventh C ² -NOT gates are the first to fifth C ² -NOT gates arranged in reverse order. The twelfth to twentieth C ² -NOT gates are the second to tenth C ² -NOT gates arranged in reverse order.

The eleventh C ² -NOT gate in the equivalent circuit 63 performs the same operation on the target bit as the C ⁷ -NOT gate 61. The latter nine C ² -NOT gates are quantum gates that restore the states of the ancillary bits. The presence of these C ² -NOT gates makes the equivalent circuit 63 equivalent to the C ⁷ -NOT gate 61, including the states of the ancillary bits after the gate operation.

In the second conversion method, clean bits are treated as dirty bits, so the clean bits are not used effectively. Therefore, although the number of quantum bits used is limited to 13, the number of quantum gates in the equivalent circuit 63 is large at 20.

17 is a diagram showing an example of an equivalent circuit of a C ⁷ -NOT gate by the third conversion method. When the third conversion method is applied to the C ⁷ -NOT gate 61, one auxiliary bit is used. In the third conversion method, an equivalent circuit 64 is generated in which the C ⁷ -NOT gate 61 is divided into four C ⁴ -NOT gates by using one auxiliary bit (a clean bit in the example of FIG. 17). By converting each of the C ⁴ -NOT gates included in the equivalent circuit 64 into the equivalent circuit 47 (see FIG. 5), an equivalent circuit 65 consisting of only C ² -NOT gates is generated.

In the third conversion method, clean bits are treated as dirty bits, so the clean bits are not used effectively. Also, only one auxiliary bit is used, so many dirty bits are not used effectively. Therefore, although the number of quantum bits used is limited to 13, the number of quantum gates in the equivalent circuit 65 is large at 32.

The quantum gate conversion unit 130 therefore minimizes the number of gates by using as many of the given clean bits and dirty bits as possible. In particular, when the number of clean bits c is "c=1, ..., k-1", the quantum gate conversion unit 130 uses the fourth conversion method to convert to an equivalent circuit with a smaller number of quantum gates.

The quantum gate conversion unit 130 generates a set of two quantum bits from the k control bit group C={c ₁ , . . . , c _k } of C ^k -NOT in the same manner as the first conversion method, the number of clean bits. The quantum gate conversion unit 130 adds a C ² -NOT gate to the equivalent circuit, in which the two generated quantum bits are control bits and the clean bit is a target bit. The clean bit that becomes the target bit in the added C ² -NOT gate is added to the control bit group C. In this case, if there are k-2 or more clean bits, the conversion method is the same as the first conversion method. Such a conversion policy is the basic policy of the fourth conversion method.

Fig. 18 is a diagram showing an example of an equivalent circuit of a C ⁷ -NOT gate according to the basic principle of the fourth conversion method. As shown in Fig. 18, when k=7 and the number of clean bits "c=5", the C ⁷ -NOT gate 61 is converted into an equivalent circuit 71 including eleven C ² -NOT gates, as in the first conversion method (see Fig. 15).

When the number of clean bits is less than k-5, the quantum gate conversion unit 130 gradually reduces the number of control bits of the C ^k -NOT gate 61. In this case, if the control bits are not appropriately grouped, the number of quantum gates in the quantum circuit after conversion cannot be sufficiently reduced.

For example, it is possible to convert to an equivalent circuit that includes a C ² -NOT gate using a set of control bits equal to the number of clean bits, and a C ^k -NOT gate using control bits not used in those C ² -NOT gates.

19 is a diagram showing a first example of an equivalent circuit of a C ⁷ -NOT gate by the fourth conversion method when there are less than k-2 clean bits. In the example of FIG. 19, c=1 for k=7. In this case, the C ⁷ -NOT gate 61 is converted into an equivalent circuit 72 including two C ² -NOT gates and one C ⁶ -NOT gate.

Here, when the central C ⁶ -NOT gate is further converted into an equivalent circuit, there are only two dirty bits (c ₁ and c ₂ ) that can be used as auxiliary bits. Therefore, only the third conversion method can be applied to convert the C ^{6 -NOT gate into an equivalent circuit. When the third conversion method is applied, the C 6 -NOT} gate is converted into 24 C ² -NOT gates. As a result, the C ⁷ -NOT gate 61 is converted into a total of 26 C ² -NOT gates. In this way, the number of gates increases when the third conversion method is applied.

Therefore, the quantum gate conversion unit 130 divides the control bit group of the C ^k -NOT gate to be converted into a plurality of subgroups so that the second conversion method can be applied to the central C ^k -NOT gate after the division, thereby reducing the number of quantum gates in the equivalent circuit that is finally generated.

20 is a diagram showing a second example of an equivalent circuit of a C ⁷ -NOT gate by the fourth conversion method when there are less than k-2 clean bits. In the example of Fig. 20, when c=1 for k=7, the C ⁷ -NOT gate 61 is converted into an equivalent circuit 72 including two C ³ -NOT gates 72a and 72c and one C ⁵ -NOT gate 72b.

In converting the C ³ -NOT gate 72a into an equivalent circuit, the control bits {c ₄ , c ₅ , c ₆ } can be used as dirty auxiliary bits, so the C ³ -NOT gate 72a can be converted into four C ² -NOT gates using the second conversion method.

In converting the C ⁵ -NOT gate 72b into an equivalent circuit, the control bits {c ₁ , c ₂ , c ₃ } can be used as dirty auxiliary bits, so that the C ⁵ -NOT gate 72b can be converted into 12 C ² -NOT gates using the second conversion method.

In converting the C ³ -NOT gate 72c into an equivalent circuit, the control bits {c ₄ , c ₅ , c ₆ } can be used as dirty auxiliary bits, so the C ³ -NOT gate 72c can be converted into four C ² -NOT gates using the second conversion method.

In this way, by first generating a C ³ -NOT gate instead of a C ² -NOT gate, the central C ^k -NOT gate becomes a C ⁵ -NOT gate. This makes it possible to use k-2 or more auxiliary bits when converting each C ^k -NOT gate included in the equivalent circuit 72 into an equivalent circuit. As a result, the second conversion method can convert the C ⁷ -NOT gate into a total of 20 C ² -NOT gates.

When the number of clean bits c is two or more, the quantum gate conversion unit 130 divides the C ^k -NOT gate into 2c+1 quantum gates. At this time, the quantum gate conversion unit 130 determines c+1 integers "k ₁ , ..., k _c+1 ". The quantum gate conversion unit 130 divides it into C ^k_1 -NOT, ..., C ^k_c -NOT, C ^k_c+1 -NOT, C ^k_c -NOT, ..., C ^k_1 -NOT. The characters following the superscript k indicate the subscript of k. For example, the superscripts "k_1, ..., k_c+1" respectively represent the superscript integers "k ₁ , ..., k _c+1 ".

The quantum gate conversion unit 130 determines an integer indicating the number of control bits of the quantum gate after division (number of control bits after division) so as to satisfy the following two conditions among those satisfying k ₁ ≧k ₂ ≧ ... ≧k _c , where k _c+1 satisfies the following formula:

[Condition 1] The second conversion method can be used for the c ^k_c+1 -NOT gate, which means that k _c+1 -2 dirty bits can be secured.
[Condition 2] There exists no such condition that 1≦i<j≦c such that k _i >c−i+2 and k _j <c−j+2.

In this case, the quantum gate conversion unit 130 can use the clean bits from (i+1) to (c) when converting a C ^k_i -NOT gate to a C ² -NOT gate in 1≦i≦c−1. Also, when converting a C ^k_i -NOT gate in 1≦i≦c−1 to a C ² -NOT gate, a sufficient number of dirty bits can be secured. Therefore, the above-mentioned "basic policy + second conversion method" can be applied.

Condition 1 is a condition for ensuring as many clean bits as possible in the C ^k_i -NOT gates having many control bits.
Condition 2 is a condition for using clean bits without excess or deficiency. If there exists 1≦i<j≦c that satisfies k _i >c-i+2 and k _j <c-j+2, it can be confirmed that in the new division with k _i ←k _i -1, k _j ←k _j +1, the clean bits can be utilized more effectively than in the initial division, especially in the conversion of the C ^k_j -NOT gate. In other words, when condition 2 is not satisfied, the quantum gate conversion unit 130 can reduce the number of quantum gates by four from the initial division by changing the number of control bits after division to k _i ←k _i -1, k _j ←k _j +1.

Fig. 21 is a diagram showing an example of division by the fourth transformation method when c=2. In the example of Fig. 21, it is assumed that a C ¹² -NOT gate 73 is converted into an equivalent circuit 74. The number of clean bits c is 2 (k=12, c=2). In this case, the integers indicating the number of control bits after division of the C ^k_i -NOT gate obtained by division by the fourth transformation method are "k ₁ =k ₂ =3, k ₃ =8".

Since "k ₁ = 3", the first quantum gate of the equivalent circuit 74 is a C ³ -NOT gate 74a. Since "k ₂ = 3", the second quantum gate of the equivalent circuit 74 is a C ³ -NOT gate 74b. Since "k ₃ = 8", the third quantum gate (the central quantum gate) of the equivalent circuit 74 is a C ⁸ -NOT gate 74c. Since "k ₂ = 3", the fourth quantum gate of the equivalent circuit 74 is a C ³ -NOT gate 74d. Since "k ₁ = 3", the fifth quantum gate of the equivalent circuit 74 is a C ³ -NOT gate 74e.

In the conversion to the equivalent circuit of the C ³ -NOT gates 74a and 74e, one clean bit can be used as an auxiliary bit. The fourth conversion method can be applied to the C ³ -NOT gates 74a and 74e. Therefore, the C ³ -NOT gates 74a and 74e can be converted to an equivalent circuit 42 (see FIG. 4) including three C ² -NOT gates using a clean bit based on the basic principle of the fourth conversion method. In the conversion to the equivalent circuit of the C ³ -NOT gates 74b and 74d, one dirty bit can be used as an auxiliary bit. Therefore, the C ³ -NOT gates 74b and 74d can be converted to an equivalent circuit 43 (see FIG. 4) including four C ² -NOT gates using a dirty bit. In the conversion to the equivalent circuit of the C ⁸ -NOT gate 74c, six dirty bits can be used as auxiliary bits. Therefore, the C ⁸ -NOT gate 74c can be converted into 24 C ² -NOT gates by the second conversion method.

As described above, the quantum gate conversion unit 130 can convert the C ¹² -NOT gate 73 into an equivalent circuit including a total of 38 C ² -NOT gates by converting each C ^k -NOT gate in the equivalent circuit 74 into an equivalent circuit.

Fig. 22 is a diagram showing an example of division by the fourth transformation method when c=3. In the example of Fig. 22, it is assumed that a C ¹² -NOT gate 73 is converted into an equivalent circuit 75. The number of clean bits c is 3 (k=12, c=3). In this case, the integers indicating the division positions by the fourth transformation method are "k ₁ =3, k ₂ =k ₃ =2, k ₃ =8".

Since "k ₁ =3", the first quantum gate of the equivalent circuit 75 is a C ³ -NOT gate 75a. Since "k ₂ =2", the second quantum gate of the equivalent circuit 75 is a C ² -NOT gate 75b. Since "k ₃ =2", the third quantum gate of the equivalent circuit 75 is a C ² -NOT gate 75c. Since "k ₄ =8", the fourth quantum gate (the central quantum gate) of the equivalent circuit 75 is a C ⁸ -NOT gate 75d. Since "k ₃ =2", the fifth quantum gate of the equivalent circuit 75 is a C ² -NOT gate 75e. Since "k ₂ =2", the sixth quantum gate of the equivalent circuit 75 is a C ² -NOT gate 75f. Since "k ₁ =3", the seventh quantum gate of the equivalent circuit 75 is a C ³ -NOT gate 75g.

In converting the C ³ -NOT gates 75a and 75g into their equivalent circuits, one clean bit can be used as an auxiliary bit. Therefore, each of the C ³ -NOT gates 75a and 75g can be converted into an equivalent circuit 42 (see FIG. 4) including three C ² -NOT gates using the clean bit. In converting the C ⁸ -NOT gate 75d into its equivalent circuit, six dirty bits can be used as auxiliary bits. Therefore, the C ⁸ -NOT gate 75d can be converted into 24 C ² -NOT gates by the second conversion method.

As described above, the quantum gate conversion unit 130 converts each C ^k -NOT gate in the equivalent circuit 75 into an equivalent circuit, thereby making it possible to convert the C ¹² -NOT gate 73 into an equivalent circuit including a total of 34 C ² -NOT gates.

Next, the functions of the quantum gate conversion unit 130 for realizing such conversion processing will be described.
23 is a diagram showing an example of functions of the quantum gate conversion unit 130. The quantum gate conversion unit 130 includes a quantum gate conversion management unit 131, a division method determination unit 132, and a quantum circuit generation unit 133.

The quantum gate conversion management unit 131 cooperates with the division method determination unit 132 and the quantum circuit generation unit 133 to convert the input C ^k -NOT gate into an equivalent circuit "qc". For example, information indicating a C ^k -NOT gate, "tmpCleanBitList" and "tmpDirtyBitList", are input to the quantum gate conversion management unit 131. The information indicating a C ^k -NOT gate includes a list of control bits C={c ₁ , ..., c _k } and an identification number "x" of a target bit. "tmpCleanBitList" is a list of quantum bits that can be used as clean bits, "CA={ca ₁ , ..., ca _c }". c is the number of clean bits (where 1≦c≦k-3). "tmpDirtyBitList" is a list of quantum bits that can be used as dirty bits, "DA={da ₁ , ..., da _d }," where d is the number of dirty bits.

The division method determination unit 132 determines the number of control bits (k _{1 ,} . . . , k c+1 ) of the quantum gates after division of the C ^k -NOT gates, so that the final number of C ² -NOT gates is minimized, depending on the values of k, _{c, and d} .

The quantum circuit generation unit 133 receives the number of control bits (k ₁ , . . . , k _c+1 ) of the quantum gates after division determined by the division method determination unit 132, and outputs an equivalent circuit "qc" of the C ^k -NOT gate (consisting only of a C ² -NOT gate).

Next, the procedure of the quantum gate conversion process performed by the quantum gate conversion unit 130 will be described in detail.
24 is a flowchart showing an example of a procedure for quantum gate conversion processing. The processing shown in FIG. 24 will be described below in order of step numbers.

[Step S301] The quantum gate conversion management unit 131 determines whether the condition that the number of clean bits c is 0 (c=0) and the number of dirty bits d is 1 or more (d≧1) is satisfied. If the condition is satisfied, the quantum gate conversion management unit 131 advances the process to step S302. If the condition is not satisfied, the quantum gate conversion management unit 131 advances the process to step S303.

[Step S302] The quantum gate conversion management unit 131 instructs the quantum circuit generation unit 133 to generate a quantum circuit equivalent to the C ^k -NOT gate to be converted. The quantum circuit generation unit 133 generates an equivalent circuit "qc" of the C ^k -NOT gate to be converted by the third conversion method. When the quantum gate conversion management unit 131 obtains the equivalent circuit "qc" from the quantum circuit generation unit 133, the process proceeds to step S307.

[Step S303] The quantum gate conversion management unit 131 determines whether the condition that the number of clean bits c is equal to or greater than k-2 (c ≥ k-2) is satisfied. If the condition is satisfied, the quantum gate conversion management unit 131 advances the process to step S304. If the condition is not satisfied, the quantum gate conversion management unit 131 advances the process to step S305.

[Step S304] The quantum gate conversion management unit 131 instructs the quantum circuit generation unit 133 to generate a quantum circuit equivalent to the C ^k -NOT gate to be converted. The quantum circuit generation unit 133 generates an equivalent circuit "qc" of the C ^k -NOT gate to be converted by the first conversion method. When the quantum gate conversion management unit 131 obtains the equivalent circuit "qc" from the quantum circuit generation unit 133, the process proceeds to step S307.

[Step S305] The quantum gate conversion management unit 131 instructs the division method determination unit 132 to determine a division method. The division method determination unit 132 determines the number of post-division control bits of the C ^k_i -NOT gate obtained by dividing the C ^k -NOT gate according to the instruction. The quantum gate conversion management unit 131 obtains a set of integers indicating the number of post-division control bits from the division method determination unit 132. Details of the division method determination process will be described later (see FIG. 25).

[Step S306] The quantum gate conversion management unit 131 instructs the quantum circuit generation unit 133 to generate a quantum circuit equivalent to the C ^k -NOT gate in the fourth conversion method. The quantum circuit generation unit 133 generates an equivalent circuit "qc" of the C ^k -NOT gate by the fourth conversion method. The quantum gate conversion management unit 131 obtains the equivalent circuit "qc" from the quantum circuit generation unit 133.

[Step S307] The quantum gate conversion management unit 131 outputs the equivalent circuit "qc" as the equivalent circuit of the C ^k -NOT gate to be converted.
In this way, when the first conversion method is applicable, the C ^k -NOT gate is converted into an equivalent circuit by the first conversion method. When the applicable conversion method is limited to the third conversion method, the C ^k -NOT gate is converted into an equivalent circuit by the third conversion method. In other cases, the C ^k -NOT gate is converted into an equivalent circuit by the fourth conversion method.

Next, the division method determination process will be described in detail.
25 is a flowchart showing an example of a division method determination process. The process shown in FIG. 25 will be described below in order of step number.

[Step S401] The division method determination unit 132 performs initial settings. For example, the division method determination unit 132 sets k ₁ = k ₂ = ... = k _c = 2. The division method determination unit 132 also sets k _c+1 as shown in formula (1). When "k ₁ , ..., k _c " are initialized to "2", "k _i -1" on the right side of formula (1) all become 1, and the right side becomes "k-c". In other words, the initial value of k _c+1 is the value obtained by subtracting the number of clean bits c from the number of control bits k of the C ^k -NOT gate to be converted.

[Step S402] The division method determination unit 132 initializes a variable j to “1” (j=1).
[Step S403] The division method determination unit 132 determines whether to end the process based on whether the following formula (2) is satisfied.

Equation (2) indicates a condition that the number of quantum bits usable as dirty auxiliary bits at the time of execution of the C ^k_c+1 -NOT gate is k _c+1 -2 or more. This condition is an application condition of the second conversion method. The number of quantum bits usable as dirty auxiliary bits at the time of execution of the C ^k_c+1 -NOT gate is the sum of the number of elements included in the DA and the number of quantum bits used as control bits in each quantum gate from the C ^k_1 -NOT gate to the C ^k_c -NOT gate.

If the condition for the termination judgment is satisfied, the division method determination unit 132 advances the process to step S407. If the condition for the termination judgment is not satisfied, the division method determination unit 132 advances the process to step S404.

[Step S404] The division method determination unit 132 adds "1" to _kj ( _kj ← _kj +1). Also, the division method determination unit 132 subtracts "1" from _kc+1 ( _kc+1 ←kc _+1-1 ).

[Step S405] The division method determination unit 132 judges whether k _j is equal to or greater than c-j+2 (k _j ≧c-j+2?). If k _j is equal to or greater than c-j+2, the division method determination unit 132 advances the process to step S406. If k _j is less than c-j+2, the division method determination unit 132 advances the process to step S403.

The process of step S405 satisfies the above-mentioned condition 2 (there is no 1≦i<j≦c such that k _i >c-i+2 and k _j <c-j+2 are satisfied). In other words, if "k _j ≧c-j+2" does not hold after adding "1" to k _j in step S404, "1" is further added to k _j unless the end determination is satisfied. If "k _{j ≧} c-j+2" is satisfied, no further additions are made, so it does not hold true.

Also, the number of clean bits "c-j" available when converting to an equivalent circuit of a C ^k_j -NOT gate may be small. For example, in the case of "c-j=0", when the initial value "k _j =2" for k _j is added for the first time in step S404 to "k _j =3", "k _j >c-j+2" is obtained. On the other hand, the number of clean bits "c-p" available when converting to an equivalent circuit of a C ^k_p -NOT gate (j<p≦c) is smaller than "c-j" (for example, "c-j=-1"). Therefore, even if the initial value "k _p =2" is used, "k _p <c-j+2" is not satisfied, and "k _p <c-j+2" is not satisfied.

From the above, there is no 1≦j<p≦c that satisfies k _j >c-j+2 and k _p <c-p+2. Since the same result is obtained even if j is replaced with i and p is replaced with j, condition 2 is satisfied by the presence of step S405. By satisfying condition 2, clean bits are effectively utilized, and the number of quantum gates after conversion to an equivalent circuit is reduced.

[Step S406] The division method determination unit 132 updates j to the value obtained by adding 1 to the remainder obtained by dividing j by c (j←(j mod c)+1). After that, the division method determination unit 132 proceeds to step S403.

[Step S407] The division method determination unit 132 outputs " _k1 , ..., _kc+1 " and ends the division method determination process. The output " _k1 , ..., _kc+1 " indicates that the number of quantum gates after division is 2c+1, and the number of control bits for each gate is " _k1 , ..., _kc , _kc+1 , _kc , ..., _k1 ".

In this way, the number of control bits is determined for each of the divided C ^k_1 -NOT gates, C ^k_2 -NOT gates, .... By dividing the determined C ^k -NOT gate to be converted into quantum gates of determined sizes, the number of quantum gates in the finally generated equivalent circuit can be reduced.

Next, the procedure of the quantum circuit generation process in the fourth transformation method will be described in detail.
26 is a flow chart showing an example of the procedure of an equivalent circuit generation process in the fourth conversion method. The process shown in FIG. 26 will be described below in order of step numbers.

[Step S501] The quantum circuit generation unit 133 divides the C ^k -NOT gate according to a set of integers "k ₁ , ..., k _c , k _c+1 " indicating the number of control bits after division. Through the division process, a C ^k_1 -NOT gate, ..., C ^k_c -NOT gate, C ^k_c+1 -NOT gate, ..., C ^k_c -NOT gate, ..., C ^k_1 -NOT gate are generated.

[Step S502] The quantum circuit generation unit 133 generates an empty equivalent circuit “qc” (qc=[]).
[Step S503] The quantum circuit generation unit 133 sets the initial value of the variable i to “1”.

[Step S504] The quantum circuit generation unit 133 determines whether the value of the variable i is equal to or less than the number of clean bits c. If the value of the variable i is equal to or less than the number of clean bits c, the quantum circuit generation unit 133 proceeds to step S505. If the value of the variable i exceeds the number of clean bits c, the quantum circuit generation unit 133 proceeds to step S508.

[Step S505] The quantum circuit generation unit 133 performs a process (C ^k_i -NOT gate conversion process) of converting the C ^k_i -NOT gate (the i-th quantum gate after division) into an equivalent circuit using a C ² -NOT gate. The equivalent circuit generated by the conversion process is called "circ". Details of the C ^k_i -NOT gate conversion process will be described later (see Figures 27 and 28). Note that in the process of the C ^k_i -NOT gate conversion process, the quantum bit that has become the control bit in the C ^k_i -NOT gate is deleted from the list C of control bits.

[Step S506] The quantum circuit generation unit 133 adds the equivalent circuit "circ" to the equivalent circuit "qc".
[Step S507] The quantum circuit generation unit 133 adds 1 to the variable i (i←i+1). After that, the quantum circuit generation unit 133 proceeds to step S504.

[Step S508] The quantum circuit generation unit 133 generates a quantum circuit "qc _inv " in which the quantum gates included in the equivalent circuit "qc" are arranged in reverse order.
[Step S509] The quantum circuit generation unit 133 converts the C ^k_(c+1) -NOT gate, which is the central quantum gate after division, into an equivalent circuit using a C ² -NOT gate by the second conversion method. The control bits of the ^{C k_(c+1)} -NOT gate are the quantum bits remaining in the control bit list C. The target bit of the C ^k_(c+1) -NOT gate is the same as the target bit x of the C ^k -NOT gate to be converted.

For example, the quantum circuit generation unit 133 sets the number L of elements included in the control bit list C to "L = _kc+1 ". The quantum circuit generation unit 133 uses the first two of the dirty bits included in DA as auxiliary bits to convert the ^Ck_(c+1) -NOT gate into an equivalent circuit by the second conversion method. The quantum circuit generation unit 133 names the equivalent circuit generated by the conversion "CIRC".

[Step S510] The quantum circuit generation unit 133 adds the equivalent circuit "circ" generated in step S509 to the equivalent circuit "qc".
[Step S511] The quantum circuit generation unit 133 adds the quantum circuit "qc _inv " generated in step S508 to the equivalent circuit "qc".

In this way, each of the divided quantum gates is converted into an equivalent circuit composed only of C ² -NOT gates, resulting in the generation of an equivalent circuit "qc" of the original C ^k -NOT gate to be converted.

27 is a flowchart (1/2) showing an example of the procedure of the C ^k_i -NOT gate conversion process. The process shown in FIG. 27 will be described below in order of step numbers.
[Step S601] The quantum circuit generation unit 133 leaves the equivalent circuit "circ" blank (circ=[]).

[Step S602] The quantum circuit generation unit 133 judges whether or not k _i is "2" (k _i =2?). If k _i is "2", the quantum circuit generation unit 133 proceeds to step S603. If k _i is not "2", the quantum circuit generation unit 133 proceeds to step S607.

[Step S603] The quantum circuit generation unit 133 adds a C 2 -NOT gate to the equivalent circuit "circ", with the first two quantum bits of C (C[0], C[1]) as control bits and the i- ^th quantum bit of CA (CA[i]) as the target bit.

[Step S604] The quantum circuit generation unit 133 deletes the control bits (the first two quantum bits of C) in the C ² -NOT gate added to the equivalent circuit "CIRC" from C. Then, the quantum circuit generation unit 133 adds these quantum bits to DA.

[Step S605] The quantum circuit generation unit 133 adds CA[i], which is the target bit in the C ² -NOT gate added to the equivalent circuit "circ", to DA.
[Step S606] The quantum circuit generation unit 133 adds CA[i], which is the target bit in the C ² -NOT gate added to the equivalent circuit "CIRC", to C. After that, the quantum circuit generation unit 133 proceeds to step S627 (see FIG. 28).

[Step S607] The quantum circuit generation unit 133 creates a list C _tmp of k _i quantum gates from the top of C.
[Step S608] The quantum circuit generation unit 133 creates an empty quantum circuit "qc _tmp1 " (qc _tmp1 = [ ]).

[Step S609] The quantum circuit generation unit 133 sets the list obtained by excluding the elements of C _tmp from C as DA _tmp (DA _tmp ←C\C _tmp ).
[Step S610] The quantum circuit generation unit 133 sets the smaller value of k _i -2 and c - i to p (p = min {k _i -2, c - i}).

[Step S611] The quantum circuit generation unit 133 initializes j and i to “1” (j=i=1).
[Step S612] The quantum circuit generation unit 133 judges whether the value of j is equal to or less than i+p (j≦i+p?). If the value of j is equal to or less than i+p, the quantum circuit generation unit 133 proceeds to step S613. If the value of j exceeds i+p, the quantum circuit generation unit 133 proceeds to step S618.

[Step S613] The quantum circuit generation unit 133 adds a C 2 -NOT gate to the quantum circuit “qc tmp1 ”, which has the first two quantum bits of C _tmp (C _tmp [0], C _tmp [1]) as control bits and the ^jth quantum bit of CA ( _CA [j]) as a target bit.

[Step S614] The quantum circuit generation unit 133 adds the control bits (C _tmp [0], C _tmp [1]) of the C ² -NOT gate added to the quantum circuit “qc _tmp1 ” to DA _tmp .
[Step S615] The quantum circuit generation unit 133 deletes the control bits (C _tmp [0], C _tmp [1]) of the C ² -NOT gate added to the quantum circuit “qc _tmp1 ” from C _tmp .

[Step S616] The quantum circuit generation unit 133 adds the target bit (CA[j]) of the C ² -NOT gate added to the quantum circuit “qc _tmp1 ” to C _tmp .
[Step S617] The quantum circuit generation unit 133 adds 1 to the value of j (j←j+1). After that, the quantum circuit generation unit 133 proceeds to step S612.

[Step S618] The quantum circuit generation unit 133 sets k _i -p to L (L←k _i -p). After that, the quantum circuit generation unit 133 proceeds to step S621 (see FIG. 28).

28 is a flowchart (2/2) showing an example of the procedure of the C ^k_i -NOT gate conversion process. The process shown in FIG. 28 will be described below in order of step numbers.
[Step S621] The quantum circuit generation unit 133 determines whether or not L = 2 (L = 2?). If L = 2, the quantum circuit generation unit 133 proceeds to step S622. If L = 2, the quantum circuit generation unit 133 proceeds to step S623.

[Step S622] The quantum circuit generation unit 133 sets a C 2 -NOT gate in which the first two quantum bits of C _tmp (C _tmp [0], C _tmp [1]) are set as control bits and the i-th quantum bit of ^CA (CA[i]) is set as a target bit, as an equivalent circuit "qc _tmp2 ". After that, the quantum circuit generation unit 133 proceeds to step S624.

[Step S623] The quantum circuit generation unit 133 converts a C ^L -NOT gate, which has the quantum bit of C _tmp as the control bit and the i-th quantum bit of CA as the target bit, into an equivalent circuit by the second conversion method with the first L-2 bits of DA _tmp as dirty bits. The quantum circuit generation unit 133 outputs the equivalent circuit "qc _tmp2 " obtained by the conversion.

[Step S624] The quantum circuit generation unit 133 generates a quantum circuit "qc _{tmp1_inv} " by arranging the C ² -NOT gates in the quantum circuit "qc _tmp1 " in reverse order.
[Step S625] The quantum circuit generation unit 133 adds "qc _tmp1 ", "qc _tmp2 ", and "qc _{tmp1_inv} " to the equivalent circuit "circ".

[Step S626] The quantum circuit generation unit 133 deletes k _i elements from the beginning of C. The quantum circuit generation unit 133 also adds to DA the elements deleted from C. Furthermore, the quantum circuit generation unit 133 adds to C the i-th element of CA (CA[i]).

[Step S627] The quantum circuit generation unit 133 outputs the equivalent circuit “circ”.
By the processing shown in Figures 27 and 28, each of the quantum circuits (C ^k_1 -NOT gate, ..., C ^k_c -NOT gate) for the number of clean bits is converted into an equivalent circuit combining C ² -NOT gates, and the converted equivalent circuit is added to the equivalent circuit "CIRC".

Next, the conversion process of the C ^k -NOT gate will be explained using a concrete example.
29 is a diagram showing an example of conversion of a C ^k -NOT gate. The C ^k -NOT gate 61 to be converted has the number of control bits "7" (k=7). It is also assumed that one clean bit and four dirty bits can be used.

The inputs to the quantum gate conversion unit 130 are a control bit “C={c ₁ , ..., c ₇ }”, a target bit x, a tmpCleanBitList “CA={ca ₁ }”, and a tmpDirtyBitList “DA={da ₁ , ..., da ₄ }”. The quantum gate conversion management unit 131 first inputs “k=7”, “c=1”, and “d=4” to the division method determination unit 132.

When " _k1 = 2" and " _k2 = 6", the division method determination unit 132 determines that the end judgment condition " _k2 - 2 ≦ d + _k1 " is satisfied because the left side of the condition is "4" and the right side is "6". Therefore, the division method determination unit 132 outputs " _k1 = 2" and " _k2 = 6".

The quantum gate conversion management unit 131 inputs “C”, “CA”, “DA”, “k ₁ = 2”, and “k ₂ = 6” to the quantum circuit generation unit 133 based on the output result of the division method determination unit 132. Then, the quantum circuit generation unit 133 first generates an empty equivalent circuit “qc = [ ]”.

Next, the quantum circuit generation unit 133 adds a C ² -NOT gate 76a with "c ₁ , c ₂ " as the control bit and ca ₁ as the target bit to "qc=[]" with "i=1". At this time, the quantum circuit generation unit 133 updates the control bit to "C={c ₃ , ..., c ₇ }" and updates "tmpDirtyBitList" to "DA={da ₁ , ..., da ₄ , c ₁ , c ₂ }". Furthermore, the quantum circuit generation unit 133 generates a quantum circuit "qc _inv " in which the quantum gates included in "qc" are arranged in reverse order. In the example of FIG. 29, only the C ² -NOT gate 76c is included in "qc _inv ".

The quantum circuit generation unit 133 converts the C ⁶ -NOT gate, which has all quantum bits of "C={c ₃ , ..., c ₇ }" as control bits and x as a target bit, into an equivalent circuit 76b consisting of only C ² -NOT gates by the second conversion method. At this time, the quantum circuit generation unit 133 sets "DA={da ₁ , ..., da ₄ , c ₁ , c ₂ }" as a dirty bit. The quantum circuit generation unit 133 adds the generated equivalent circuit 76b to "qc". Furthermore, the quantum circuit generation unit 133 adds the C ² -NOT gate 76c in "qc _inv " to "qc".

As a result, an equivalent circuit 76 of the C ² -NOT gate 61 is output. The number of quantum bits of the output equivalent circuit 76 is "13", and the number of gates is "18". Compared to the first conversion method (number of quantum bits: "17", number of quantum gates: "11") shown in FIG. 15, the fourth conversion method requires a smaller number of quantum bits. Compared to the second conversion method (number of quantum bits: "13", number of quantum gates: "20") shown in FIG. 16, the fourth conversion method requires a smaller number of quantum gates. Compared to the third conversion method (number of quantum bits: "13", number of quantum gates: "32") shown in FIG. 17, the fourth conversion method requires a smaller number of quantum gates.

In this way, by performing the conversion using the fourth conversion method, it is possible to minimize the number of quantum gates in the quantum circuit after conversion under the condition that the number of quantum bits used cannot be increased. By reducing the number of quantum gates, it is possible to shorten the calculation time by the quantum computer 200.

Even if the number of control bits k of the C ^k -NOT gate to be converted is larger, the number of quantum gates for conversion can be reduced without increasing the number of quantum bits used by applying the fourth conversion method in the same manner. For example, assume that the C ¹² -NOT gate 73 shown in FIG. 21 is converted. The number of quantum gates in the equivalent circuit after conversion varies depending on the number of clean bits "c" and the number of dirty bits "d" that can be used.

<When c=0>
If 1≦d≦k-3, the C ¹² -NOT gate 73 can be converted into an equivalent circuit of 72 C ² -NOT gates by the third conversion method, and if d≧k-3, it can be converted into an equivalent circuit of 40 C ² -NOT gates by the second conversion method.

<In the case of c=1>
If d=0, k ₁ =6, k ₂ =7, and the number of C ² -NOT gates in the equivalent circuit is "52". If d=1, k ₁ =5, k ₂ =8, and the number of C ² -NOT gates in the equivalent circuit is "48". If d=2, k ₁ =5, k ₂ =8, and the number of C ² -NOT gates in the equivalent circuit is "48". If d=3, k ₁ =4, k ₂ =9, and the number of C ² -NOT gates in the equivalent circuit is "44". If d=4, k ₁ =4, k ₂ =9, and the number of C ² -NOT gates in the equivalent circuit is "44". If d=5, k ₁ =3, k ₂ =10, and the number of C ² -NOT gates in the equivalent circuit is "40". If d=6, then k ₁ =3, k ₂ =10, and the number of C ² -NOT gates in the equivalent circuit is 40. If d≧7, then k ₁ =2, k ₂ =11, and the number of C ² -NOT gates in the equivalent circuit is 38.

<When c=2>
If d=0,1, then _k1 =3, _k2 =3, _k3 =8, and the number of ^C2 -NOT gates in the equivalent circuit is 38. If d=2,3, then _k1 =3, _k2 =2, _k3 =9, and the number of ^C2 -NOT gates in the equivalent circuit is 36. If d≧4, then _k1 =2, _k2 =2, _k3 =10, and the number of ^C2 -NOT gates in the equivalent circuit is 36.

<When c=3>
If d = 0, then k ₁ = 3, k ₂ = 2, k ₃ = 2, k ₄ = 8, and the number of C ² -NOT gates in the equivalent circuit is 34. If d ≥ 1, then k ₁ = 2, k ₂ = 2, k ₃ = 2, k ₄ = 9, and the number of C ² -NOT gates in the equivalent circuit is 34.

<When c=4 to 9>
Regardless of the value of d, k ₁ = . . . = k _c = 2, k _c+1 = 12 - c, and the number of C ² -NOT gates in the equivalent circuit is "40 - 2c".

<When c=10>
According to the first conversion method, the number of C ² -NOT gates in the equivalent circuit becomes "21".
In this way, the quantum gate conversion unit 130 can convert the C ^k -NOT gate into a combination of the minimum number of C ² -NOT gates possible.

Other embodiments
In the second embodiment, quantum computation based on a quantum circuit is executed by the quantum computer 200, but it is also possible to execute quantum computation by quantum simulation using a classical computer. In that case, a classical computer capable of executing quantum simulation is used instead of the quantum computer 200. Also, the classical computer 100 shown in the second embodiment may execute the quantum simulation.

In the second embodiment, it is assumed that the quantum computer 200 can perform gate operations of the C ² -NOT gate, but there may be cases where the quantum computer 200 cannot perform gate operations of the C ² -NOT gate. In such cases, the classical computer 100 converts the C ² -NOT gate into an equivalent circuit that further combines other basic quantum gates. Even in this case, as shown in the first and second embodiments, the number of gates in the quantum circuit that is finally generated can be reduced by converting the C ^k -NOT gate into a C ² -NOT gate with a smaller number of quantum gates in advance.

In the second embodiment, the equivalent circuit includes a quantum circuit for returning the state of the auxiliary bit (clean bit or dirty bit) to the state before use. If it is known that the auxiliary bit does not need to be restored, it is also possible to exclude the quantum circuit for returning it to the state before use from the equivalent circuit. A case in which the auxiliary bit does not need to be restored is, for example, when the auxiliary bit is not the object of measurement and the subsequent state of the auxiliary bit does not affect the quantum bit that is the object of measurement. By excluding the quantum circuit for returning the auxiliary bit to the state before use from the equivalent circuit, the number of quantum gates can be reduced.

The foregoing merely illustrates the principles of the present invention. Moreover, since numerous modifications and variations are possible to those skilled in the art, the present invention is not limited to the exact construction and application shown and described above, and all corresponding modifications and equivalents are deemed to be within the scope of the present invention as defined by the appended claims and their equivalents.

1a quantum circuit 1b initial value information 2 to 6 quantum gate 10 quantum circuit design support device 11 storage unit 12 processing unit

Claims (8)

a quantum gate having an earlier order of gate operation in the quantum circuit is selected as a judgment target, and based on initial value information indicating whether each of a plurality of quantum bits operated by the quantum circuit has a predetermined value in an initial state, a judgment is made as to whether a quantum bit to be operated by the quantum gate to be judged has the predetermined value after the gate operation;
for each of the quantum gates to be determined, a quantum bit that has become the predetermined value after a gate operation by the quantum gate to be determined is identified;
A quantum circuit design support program that executes processing on a computer. In the process of identifying the quantum bit that has become the predetermined value, the quantum bit that has become the predetermined value after the gate operation by the quantum gate to be determined is identified based on whether the quantum bit to be operated by the quantum gate to be determined becomes the predetermined value after the gate operation, and whether a quantum bit other than the quantum bit to be operated has the predetermined value before the gate operation.
The quantum circuit design support program according to claim 1. In the process of determining whether the predetermined value is reached, if the gate operation by the quantum gate to be determined is an operation to change the state of the quantum bit to be operated to the predetermined value, it is determined that the quantum bit to be operated will become the predetermined value after the gate operation, and if the gate operation by the quantum gate to be determined is an operation other than an operation to change the state of the quantum bit to the predetermined value, it is determined that it is unclear whether the value will become the predetermined value after the gate operation.
The quantum circuit design support program according to claim 1. In the process of determining whether the predetermined value is reached, when the quantum gate to be determined is a swap gate, and a first quantum bit of the two quantum bits to be operated is the predetermined value before the gate operation by the quantum gate to be determined, it is determined that a second quantum bit of the quantum bits to be operated will be the predetermined value after the gate operation.
The quantum circuit design support program according to claim 1. In the process of determining whether the predetermined value is reached, when the quantum gate to be determined is a swap gate, and it is unclear whether the first quantum bit is at the predetermined value before the gate operation by the quantum gate to be determined, it is determined that it is unclear whether the second quantum bit will be at the predetermined value after the gate operation.
The quantum circuit design support program according to claim 4. identifying a third quantum bit that is the predetermined value after a gate operation of the first quantum gate based on the list generated when the first quantum gate is set as the quantum gate to be determined, and converting a second quantum gate to be executed after the first quantum gate into a quantum circuit equivalent to the second quantum gate, using the third quantum bit;
6. A quantum circuit design support program according to claim 1. a quantum gate having an earlier order of gate operation in the quantum circuit is selected as a judgment target, and based on initial value information indicating whether each of a plurality of quantum bits operated by the quantum circuit has a predetermined value in an initial state, a judgment is made as to whether a quantum bit to be operated by the quantum gate to be judged has the predetermined value after the gate operation;
for each of the quantum gates to be determined, a quantum bit that has become the predetermined value after a gate operation by the quantum gate to be determined is identified;
A quantum circuit design support method in which processing is executed by a computer. a processing unit which determines whether a quantum bit to be operated by the quantum gate to be determined will become the predetermined value after gate operation based on initial value information indicating whether each of a plurality of quantum bits operated by the quantum circuit has a predetermined value in an initial state, and identifies, for each quantum gate to be determined, a quantum bit which has become the predetermined value after gate operation by the quantum gate to be determined;
A quantum circuit design support device having the above structure.

Images