CN109858628B

CN109858628B - Method, apparatus, device and computer readable storage medium for compiling quantum circuit

Info

Publication number: CN109858628B
Application number: CN201910153013.5A
Authority: CN
Inventors: 刘树森; 段润尧
Original assignee: Beijing Baidu Netcom Science and Technology Co Ltd
Current assignee: Beijing Baidu Netcom Science and Technology Co Ltd
Priority date: 2019-02-28
Filing date: 2019-02-28
Publication date: 2021-04-27
Anticipated expiration: 2039-02-28
Also published as: CN109858628A

Abstract

Embodiments of the present disclosure relate to methods, apparatuses, devices and computer program products for compiling quantum circuits. The method comprises the following steps: obtaining a logical instruction to be compiled for a quantum circuit, the quantum circuit including a plurality of qubits, the logical instruction being associated with a first qubit and a second qubit of the plurality of qubits, at least a portion of the plurality of qubits being operable with a dual-bit qubit gate therebetween; determining a path in the quantum circuit between the first qubit and the second qubit; and generating an underlying instruction for the quantum circuit corresponding to the logic instruction by adding a single bit quantum gate based on the path.

Description

Method, apparatus, device and computer readable storage medium for compiling quantum circuit

Technical Field

Embodiments of the present disclosure relate to quantum computing, and more particularly, to methods, apparatuses, and computer-readable storage media for compiling quantum circuits.

Background

At present, the topology of most superconducting quantum computers is a non-strong connection graph structure, so that the use of hardware is limited, and the general quantum computation is difficult or impossible to achieve. General quantum computing requires arbitrary (mutual) connections between any two qubits. In other words, given

(where U denotes the space in which the generic quantum task used for the computation is located, 2ⁿRepresenting the size of the space, n being the number of qubits), can be decomposed into a single bit U²And a sequence of controlled not gates (CNOT). Thus, except that each qubit is required to perform any U²In addition, any two qubits are required to perform the CNOT operation. Therefore, to achieve the purpose of general quantum computation, any two qubits can be connected, i.e., the whole quantum hardware circuit needs to have a strongly connected graph topology. However, the conventional manufacturing process cannot manufacture qualified (high-fidelity) quantum hardware with a strong connection diagram topology, and most of the quantum hardware with the topology being the connection diagram.

Disclosure of Invention

According to an embodiment of the present disclosure, a scheme for compiling quantum circuits is provided.

In a first aspect of the disclosure, a method for compiling a quantum circuit is provided. The method comprises the following steps: obtaining a logical instruction to be compiled for a quantum circuit, the quantum circuit including a plurality of qubits, the logical instruction being associated with a first qubit and a second qubit of the plurality of qubits, at least a portion of the plurality of qubits being operable with a dual-bit qubit gate therebetween; determining a path in the quantum circuit between the first qubit and the second qubit; and generating an underlying instruction for the quantum circuit corresponding to the logic instruction by adding a single bit quantum gate based on the path.

In a second aspect of the present disclosure, there is provided an apparatus for compiling quantum circuits, comprising: a logic instruction obtaining module configured to obtain a logic instruction to be compiled for a quantum circuit, the quantum circuit including a plurality of qubits, the logic instruction being associated with a first qubit and a second qubit of the plurality of qubits, at least a portion of the plurality of qubits being operable with a two-bit qubit gate therebetween; a path determination module configured to determine a path between a first qubit and a second qubit in a quantum circuit; and a bottom layer instruction generation module configured to generate a bottom layer instruction for the quantum circuit corresponding to the logic instruction by adding a single bit quantum gate based on the path.

In a third aspect of the disclosure, an electronic device is provided. The electronic device includes: one or more processors; and memory for storing one or more programs that, when executed by the one or more processors, cause the electronic device to implement the method according to the first aspect of the disclosure.

In a fourth aspect of the present disclosure, a computer readable medium is provided, having stored thereon a computer program, which when executed by a processor, implements a method according to the first aspect of the present disclosure.

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the disclosure, nor is it intended to be used to limit the scope of the disclosure.

Drawings

The above and other objects, features and advantages of the present disclosure will become more apparent by describing in greater detail exemplary embodiments thereof with reference to the attached drawings, in which like reference numerals generally represent like parts throughout.

FIG. 1 illustrates a schematic diagram of an example computing environment in which embodiments of the present disclosure can be implemented;

fig. 2 illustrates a schematic diagram of a topology of a quantum circuit, in accordance with some embodiments of the present disclosure;

fig. 3 illustrates a flow diagram of a method for compiling quantum circuits, in accordance with some embodiments of the present disclosure;

fig. 4 shows a schematic diagram of a topology of a quantum circuit, in accordance with some embodiments of the present disclosure;

FIG. 5 illustrates a schematic diagram of a swap gate, according to some embodiments of the present disclosure;

FIG. 6 illustrates an example implementation of a swap gate according to some embodiments of the present disclosure;

FIG. 7 illustrates an example implementation of a swap gate according to some embodiments of the present disclosure;

fig. 8 illustrates a block diagram of an apparatus for compiling quantum circuits, in accordance with some embodiments of the present disclosure; and

fig. 9 illustrates a block diagram of an electronic device capable of implementing some embodiments of the present disclosure.

Detailed Description

Preferred embodiments of the present disclosure will be described in more detail below with reference to the accompanying drawings. While the preferred embodiments of the present disclosure are shown in the drawings, it should be understood that the present disclosure may be embodied in various forms and should not be limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the disclosure to those skilled in the art.

The term "include" and variations thereof as used herein is meant to be inclusive in an open-ended manner, i.e., "including but not limited to". Unless specifically stated otherwise, the term "or" means "and/or". The term "based on" means "based at least in part on". The terms "one example embodiment" and "one embodiment" mean "at least one example embodiment". The term "another embodiment" means "at least one additional embodiment". The terms "first," "second," and the like may refer to different or the same object. Other explicit and implicit definitions are also possible below.

FIG. 1 illustrates a schematic diagram of an example computing environment 100 in which embodiments of the present disclosure can be implemented. As shown in fig. 1, computing environment 100 includes a classic computer 102, e.g., computing device where classic computer 102 may be implemented by a deterministic turing machine. However, it should be understood that classic computer 102 may also be any other suitable type of computing device.

As shown in fig. 1, computing environment 100 includes quantum circuitry 106, which may also be referred to as a quantum processor or the like. For example, the quantum circuit 106 may be a superconducting quantum circuit, a nuclear magnetic resonance circuit, an ion trap circuit, a silicon-based semiconductor quantum circuit, or a combination of one or more of these. It should be understood that embodiments of the present disclosure may also be applied to any other suitable specific physical implementation of a quantum circuit, whether now existing or later developed, and the disclosure is not limited thereto.

The quantum circuit 106 may have a non-strongly fully connected topology or may have a strongly fully connected topology. Classical computer 102 includes compiler 104 for compiling quantum circuit 106. Compiler 104 may convert the logical instructions into underlying instructions for provision to the quantum processor. The quantum processor may convert the received underlying instructions into physical instructions to manipulate the quantum circuit 106.

The example computing environment 100 is described above in connection with FIG. 1, however, it is to be understood that embodiments of the present disclosure may be implemented in any other suitable computing environment 100. For example, embodiments of the present disclosure may also be implemented in purely quantum circuits.

As described above, it is difficult for current quantum circuits to achieve a strongly connected topology. In quantum circuits, the CNOT may incorporate a hadamard gate (HGate) to flip the local connectivity structure. And selecting two quantum bits which can be communicated, and constructing a local full-communication structure by using the CNOT and the HGate so as to complete the target CNOT. However, this approach all performs the flipping operation by manually selecting the corresponding qubit. In addition, this approach also fails to achieve the lowest cost goal and does not achieve good fidelity. For example, the cost represents the number of gates. Manual selection of qubits ensures that only local availability is available, and global selection is not possible. In slightly larger quantum circuits (more than 3 qubits), it is virtually impossible to perform real-time, global mapping manually.

Fig. 2 illustrates a schematic diagram of a quantum circuit 200, according to some embodiments of the present disclosure. To more clearly illustrate the above problem, a detailed description is given below in conjunction with the quantum circuit 200 of fig. 2. It should be understood that the topology of fig. 2 is provided as an example only, and the principles and concepts of the present disclosure may also be applied to any other suitable quantum circuit or quantum processor, which may have more or fewer qubits, and may have a completely different topology.

The quantum circuit 200 includes five qubits q0-q4 and six bi-bit topologies coupling the five qubits to each other, the bi-bit quantum gate being capable of acting only on qubits having a bi-bit topology. For example, the two-bit quantum gate may be CNOT. For simplicity, the following description is made in conjunction with CNOT. However, it should be understood that the principles and concepts of the present disclosure may also be applied to any suitable dibit quantum gate now known or later developed in the future.

The quantum circuit 200 has a non-strongly connected graph structure in which not any two qubits can be connected. For example, quantum circuit 200 may be a superconducting quantum circuit, a nuclear magnetic resonance circuit, an ion trap circuit, and/or a silicon-based semiconductor quantum circuit, among others.

As shown in fig. 2, the arrows represent directional interactions, where the direction of the arrow represents the control direction, the head of the arrow represents the target qubit, and the tail of the arrow represents the control qubit. For example, q2 may control q1, while q1 may not control q 2. Thus, when implementing CNOT (q1, q2), an ideal circuit can be compiled into a corresponding real circuit, as shown in table 1. The real circuit shown in table 1 can implement CNOT (q1, q2) since the hadamard gate can be used to flip the direction of the CNOT gate. In this way, the CNOT may reverse the local connectivity structure in conjunction with the hadamard gate, thereby constructing a local fully-connected structure.

TABLE 1

However, for slightly more complex quantum topology logic circuits, there is no good way to implement automatic mapping of ideal and real circuits, and the general computation task cannot be completed under the limitation of CNOT and single-bit quantum gate.

For example, in the quantum circuit 200, if it is necessary to implement CNOT (q0, q3), it can be implemented using the manner shown in table 2. As shown in table 2, q3 and q2 are exchanged first, and then the direction between q2 and q0 is reversed, so that q0 controls q 3.

TABLE 2

However, the compiling method shown in table 2 has a high compiling cost, and the corresponding qubits need to be manually selected to perform the flipping operation. Based on this, embodiments of the present disclosure provide a compiling method that enables general-purpose computing that at least partially solves the above technical problems.

Fig. 3 illustrates a flow diagram of a method 300 for compiling quantum circuits, in accordance with some embodiments of the present disclosure. For example, the method 300 may be implemented at the example computing environment 100 shown in FIG. 1, and in particular the compiler 104. However, it should be understood that the method 300 may be implemented in any other suitable computing environment.

At block 302, a logical instruction to be compiled for the

quantum circuit

106 or 200 is obtained. The quantum circuit includes a plurality of qubits. The logic instruction is associated with a first qubit and a second qubit of the plurality of qubits. At least a portion of the plurality of qubits can be operated upon using a two-bit qubit gate. The first qubit may also be referred to as a control bit and the second qubit may also be referred to as a target bit. As described above, the quantum circuit 200 may have a non-strongly connected topology or a strongly connected topology, and may be, for example, a superconducting quantum circuit, a nuclear magnetic resonance circuit, an ion trap circuit, and/or a silicon-based semiconductor quantum circuit, etc.

In some embodiments, the two-bit qubit gate may be a CNOT gate and the logic instruction may include the CNOT gate controlling the second qubit by the first qubit. For example, the logical instruction may be CNOT (q0, q3) where the first qubit is q0 and the second qubit is q 3.

It should be appreciated that although described herein primarily in connection with CNOT gates, the dual bit quantum gates may be any other suitable dual bit quantum gates now known or developed in the future, and may be non-controlled dual bit quantum gates.

At block 304, a path between the first qubit and the second qubit is determined in the

quantum circuit

106 or 200. For example, the path may be the shortest path between two qubits, thereby providing better fidelity. The shortest path may be calculated by any suitable algorithm now known or developed in the future. For example, the shortest path may be calculated by Dijkstra (Dijkstra) algorithm.

In some embodiments, the path between two qubits may be determined by a graph representation of the

quantum circuit

106 or 200. For example, a graph representing the quantum circuit 200 may be acquired. The nodes in the diagram represent qubits in the quantum circuit 200 and the edges in the diagram represent dibit quantum gates. For example, a directed graph as shown in fig. 2 may be used, in which the direction of the edge represents the control direction of the CNOT. Alternatively, an undirected graph may also be used.

For example, in the graph shown in fig. 2, an edge may be determined that connects a first node representing a first qubit (e.g., q0) with a second node representing a second qubit (e.g., q 3). These edges correspond to the path between two qubits. For example, the path may be q0 — > q2 — > q3, q0 — > q2 — > q4 — > q3, and so on.

In some embodiments, the length of the path may be represented by the number of edges, so that the shortest path is the path with the fewest edges. For example, path q0- > q 2- > q3 is shorter than path q0- > q 2- > q 4- > q 3.

In other embodiments, the length of the path also takes into account the direction of the edge. For example, if at least one positive edge is included in a path, the length of the path may be reduced by one. For example, path q0 — > q2 — > q4 — > q3 includes a positive side q2 — > q4, so that its length is 3-1 ═ 2, the same length as path q0 — > q2 — > q 3. Tables 3 and 4 show the compilation results corresponding to these two paths, respectively. It can be seen that both paths have substantially the same cost and are less costly relative to the compilation results shown in table 2. Since the path q0- > q 2- > q3 contains no positive edge, q0 needs to be switched to q 3. Since path q0- > q 2- > q 4- > q3 contains a positive edge, there may be less switching.

TABLE 3

TABLE 4

In some embodiments, the graph may be a weighted graph, where each edge in the weighted graph has a corresponding weight. In this way, the weight of the path may be calculated based on the weights of the respective edges in the path. For example, the weight of the path is calculated by multiplying the number of edges included in the path by the weight of each edge. For example, since one SWAP gate may be implemented by 7 gates, the weight of each edge may be set to 7. The weight of a path may be obtained by subtracting 6 after the weight of each edge. This is because the last qubit does not need to be swapped. The weight of a path may indicate how fidelity the path is. For example, if the weight value of a path is too high, it indicates that the path has too high cost and lower fidelity.

For example, the weighted graph may be constructed in the form of a table. For example, the weight between two qubits that are connected may be set to 7, and the weight between two qubits that are not connected may be set to infinity (inf). A connection table of the quantum circuit 200 shown in fig. 2 is shown in table 5.

TABLE 5

	q0	q1	q2	q3	q4
						q0	inf	7	7	inf	inf
q1	7	inf	7	inf	Inf
						q2	7	7	inf	7	7
q3	inf	inf	7	inf	7
						q4	inf	inf	7	7	inf

For example, a path, in particular a shortest path, from a first qubit to a second qubit may be determined by various suitable algorithms. For example, the calculation may be performed using Dijkstra's algorithm. In the calculation, the weights of the paths, for example, as shown in table 5, may be considered.

Through Dijkstra algorithm, a path tree or shortest path tree can be generated, and in the process of calculating the shortest path from the starting point to the ending point, the shortest path to all other points is also calculated by the path tree. These shortest paths may be stored in a buffer, for example. In the compiling process, the shortest path can be determined by querying the cache. For example, if the corresponding path is contained in the buffer, the path may be read directly from the buffer without performing a duplicate calculation. If the corresponding path is not included in the buffer, the shortest path between the start point and the end point is calculated. Therefore, Dijkstra's algorithm can greatly compress the number of repeated calculations.

At block 306, the underlying instruction for the quantum circuit corresponding to the logical instruction is generated by adding a single bit quantum gate based on the path. The underlying instructions may be used to control the corresponding quantum circuits. Because the single-bit quantum gate is easy to realize, the complexity of the quantum circuit is not increased too much.

It should be appreciated that although the present disclosure presents some technical problems in the current quantum circuit compilation process based on a non-strongly fully-connected topology, embodiments of the present disclosure may also be applied to strongly-fully-connected topologies. When the embodiment of the present disclosure is applied to a strongly fully connected topology, the calculation of the weight may not be performed any more.

Fig. 4 illustrates a quantum circuit 400 implemented by adding a single-bit quantum gate (e.g., a hadamard gate) to the quantum circuit 200, according to some embodiments of the present disclosure. In quantum circuit 400, not only qubit q3 may control qubit q2, but also qubit q2 may control qubit q3 due to the switching gates implemented by adding hadamard gates. In fig. 4, these reverse controls, which are achieved by supplementing the hadamard gate, are shown by dashed lines.

In some embodiments, the swap gate corresponding to the path may be determined such that the first qubit and the second qubit are operated using one dual-bit qubit gate in the path. For example, in the compilation result shown in table 3, q0 was swapped to the position of q3, and q3 was swapped to the position of q 2. Thus, q0 may control q3 through a CNOT.

The switching gate may be implemented by a two-bit quantum gate and a single-bit quantum gate. For example, the swap gate may be implemented by a CNOT and Hadamard gate. For example, fig. 5 shows a circuit configuration of the SWAP gate SWAP (a, b). SWAP (a, b) comprises three alternating CNOTs, wherein the CNOTs at both ends have the same control direction and opposite control directions to the CNOT in the middle. Since there is physically only one CNOT direction between two qubits, it is necessary to flip one CNOT direction to the other direction by way of flipping.

Fig. 6 illustrates an example implementation of a swap gate in which qubit a can control qubit b and qubit b cannot control qubit a due to the presence of only CNOT (a, b), according to some embodiments of the present disclosure. Accordingly, fig. 7 illustrates an example implementation of a swap gate in which qubit a cannot control qubit b and qubit b can control qubit a due to the presence of CNOT (b, a) only, according to some embodiments of the present disclosure.

Thus, a sequence of two-bit quantum gates and single-bit quantum gates corresponding to the swap gates may be determined and the underlying instructions corresponding to the logic instructions generated based on this sequence.

Fig. 8 illustrates a block diagram of an apparatus 500 for compiling quantum circuits, according to some embodiments of the present disclosure. The apparatus 500 may be implemented by, for example, the compiler 104 shown in fig. 1. For example, the quantum circuit may have a non-strongly connected topology or a strongly connected topology, and may include superconducting quantum circuits, nuclear magnetic resonance circuits, ion trap circuits, and/or silicon-based semiconductor quantum circuits, among others.

As shown in fig. 8, apparatus 500 includes a logical instruction fetch module 502 configured to fetch a logical instruction to be compiled for the quantum circuit, the quantum circuit including a plurality of qubits, the logical instruction being associated with a first qubit and a second qubit of the plurality of qubits. At least a portion of the plurality of qubits can be operated upon using a two-bit qubit gate.

The apparatus 500 also includes a path determination module 504 configured to determine a path between the first qubit and the second qubit in the quantum circuit.

The apparatus 500 also includes an underlying instruction generation module 506 configured to generate an underlying instruction for a quantum circuit corresponding to the logic instruction by adding a single-bit quantum gate based on the path.

In some embodiments, the underlying instruction generation module 506 includes: a swap gate determination module configured to determine a swap gate corresponding to a path such that the first qubit and the second qubit are operated using one bi-bit qubit gate in the path; a sequence determination module configured to determine a sequence of dibit quantum gates and single-bit quantum gates corresponding to the swap gates; and an underlying instruction generation submodule configured to generate an underlying instruction based on a sequence of the two-bit quantum gates and the single-bit quantum gates.

In some embodiments, the path determination module 504 includes a shortest path determination module configured to determine a shortest path between the first qubit and the second qubit.

In some embodiments, the shortest path determining module comprises: a shortest path reading module configured to read the shortest path from a buffer in response to determining that the buffer includes a shortest path tree with the first qubit as a starting point.

In some embodiments, the shortest path determining module comprises: a shortest path tree calculation module configured to determine a shortest path tree by a Dijkstra algorithm in response to determining that the shortest path tree with the first qubit as a starting point is not included in the buffer; a shortest path tree storage module configured to store the shortest path tree in a buffer; and a shortest path determining submodule configured to determine the shortest path based on the shortest path tree.

In some embodiments, the two-bit qubit gate is a CNOT gate and the single-bit qubit gate is a hadamard gate, and the logic instruction includes the CNOT gate controlling the second qubit by the first qubit.

In some embodiments, the apparatus 500 further includes a graph acquisition module configured to acquire a graph representing the quantum circuit, the nodes in the graph representing qubits in the quantum circuit, and the edges in the graph representing dibit quantum gates.

In some embodiments, the path determination module 504 includes: an edge determination module configured to determine an edge connecting together a first node representing a first qubit and a second node representing a second qubit.

In some embodiments, the graph comprises a weighted graph, the edges in the weighted graph having corresponding weights.

In some embodiments, the apparatus 500 further comprises a weight determination module configured to calculate a weight of the path based on the weights of the respective edges in the path.

FIG. 9 shows a schematic block diagram of a device 600 that may be used to implement embodiments of the present disclosure. The classical computer 102 as shown in fig. 1 and the apparatus 500 as shown in fig. 8 may be implemented by a device 600. As shown in fig. 9, device 600 includes a Central Processing Unit (CPU)601 that may perform various appropriate actions and processes in accordance with computer program instructions stored in a Read Only Memory (ROM)602 or loaded from a storage unit 608 into a Random Access Memory (RAM) 603. In the RAM 603, various programs and data required for the operation of the device 600 can also be stored. The CPU 601, ROM602, and RAM 603 are connected to each other via a bus 604. An input/output (I/O) interface 605 is also connected to bus 604.

A number of components in the device 600 are connected to the I/O interface 605, including: an input unit 606 such as a keyboard, a mouse, or the like; an output unit 607 such as various types of displays, speakers, and the like; a storage unit 608, such as a magnetic disk, optical disk, or the like; and a communication unit 609 such as a network card, modem, wireless communication transceiver, etc. The communication unit 609 allows the device 600 to exchange information/data with other devices via a computer network such as the internet and/or various telecommunication networks.

Various processes and processes described above, such as method 300, may be performed by processing unit 601. For example, in some embodiments, the method 300 may be implemented as a computer software program tangibly embodied in a machine-readable medium, such as the storage unit 608. In some embodiments, part or all of the computer program may be loaded and/or installed onto the device 600 via the ROM602 and/or the communication unit 609. When the computer program is loaded into RAM 603 and executed by CPU 601, one or more steps of method 300 described above may be performed. Alternatively, in other embodiments, CPU 601 may be configured to perform method 300 by any other suitable means (e.g., by way of firmware).

As mentioned above, Dijkstra's algorithm can significantly reduce the computational requirements in conjunction with the use of buffers. The buffer may be implemented by being included in or directly using one or more of the ROM602, the RAM 603, or the storage unit 608 as shown in fig. 9, and the disclosure is not limited thereto.

The present disclosure may be methods, apparatus, systems, and/or computer program products. The computer program product may include a computer-readable storage medium having computer-readable program instructions embodied thereon for carrying out various aspects of the present disclosure.

The computer readable storage medium may be a tangible device that can hold and store the instructions for use by the instruction execution device. The computer readable storage medium may be, for example, but not limited to, an electronic memory device, a magnetic memory device, an optical memory device, an electromagnetic memory device, a semiconductor memory device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: a portable computer diskette, a hard disk, a Random Access Memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), a Static Random Access Memory (SRAM), a portable compact disc read-only memory (CD-ROM), a Digital Versatile Disc (DVD), a memory stick, a floppy disk, a mechanical coding device, such as punch cards or in-groove projection structures having instructions stored thereon, and any suitable combination of the foregoing. Computer-readable storage media as used herein is not to be construed as transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission medium (e.g., optical pulses through a fiber optic cable), or electrical signals transmitted through electrical wires.

The computer-readable program instructions described herein may be downloaded from a computer-readable storage medium to a respective computing/processing device, or to an external computer or external storage device via a network, such as the internet, a local area network, a wide area network, and/or a wireless network. The network may include copper transmission cables, fiber optic transmission, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. The network adapter card or network interface in each computing/processing device receives computer-readable program instructions from the network and forwards the computer-readable program instructions for storage in a computer-readable storage medium in the respective computing/processing device.

The computer program instructions for carrying out operations of the present disclosure may be assembler instructions, Instruction Set Architecture (ISA) instructions, machine-related instructions, microcode, firmware instructions, state setting data, or source or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C + + or the like and conventional procedural programming languages, such as the "C" programming language or similar programming languages. The computer-readable program instructions may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the case of a remote computer, the remote computer may be connected to the user's computer through any type of network, including a Local Area Network (LAN) or a Wide Area Network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet service provider). In some embodiments, the electronic circuitry that can execute the computer-readable program instructions implements aspects of the present disclosure by utilizing the state information of the computer-readable program instructions to personalize the electronic circuitry, such as a programmable logic circuit, a Field Programmable Gate Array (FPGA), or a Programmable Logic Array (PLA).

Quantum program instructions for performing the operations of the present disclosure include, but are not limited to, quantum assembly instructions (QASM) and enhanced versions and variants thereof (quantum assembly language with feedback adjustment (f-QASM), extensible quantum assembly language (eQASM), quantum assembly language with layers and loops (QASM-HL), etc.), as well as general markup languages, such as extensible markup language (XML) or JavaScript object notation (JSON), and general unstructured instruction methods, such as simple configuration files or a single execution instruction.

Various aspects of the present disclosure are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the disclosure. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer-readable program instructions.

These computer-readable program instructions may be provided to a processing unit of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processing unit of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer-readable program instructions may also be stored in a computer-readable storage medium that can direct a computer, programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer-readable medium storing the instructions comprises an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer, other programmable apparatus or other devices implement the functions/acts specified in the flowchart and/or block diagram block or blocks.

The flowchart and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems which perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.

The foregoing description of the embodiments of the present disclosure has been presented for purposes of illustration and description, and is not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein is chosen in order to best explain the principles of the embodiments, the practical application, or improvements made to the technology in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

Claims

1. A method for compiling a quantum circuit, comprising:

obtaining a logical instruction to be compiled for the quantum circuit, the quantum circuit including a plurality of qubits, the logical instruction being associated with a first qubit and a second qubit of the plurality of qubits, at least a portion of the plurality of qubits being operable with a two-bit qubit gate therebetween;

determining, in the quantum circuit, a directed path from the first qubit to the second qubit; and

generating, based on the directed path, an underlying instruction for the quantum circuit corresponding to the logical instruction by adding a single-bit quantum gate.

2. The method of claim 1, wherein generating the underlying instructions comprises:

determining a swap gate corresponding to the directed path such that the first qubit and the second qubit are operated using one dual-bit qubit in the directed path;

determining a sequence of dibit quantum gates and single-bit quantum gates corresponding to the swap gates; and

generating the underlying instruction based on the sequence of dibit quantum gates and single-bit quantum gates.

3. The method of claim 1, wherein determining the directed path comprises determining a shortest path from the first qubit to the second qubit.

4. The method of claim 3, wherein determining the shortest path comprises:

reading the shortest path from a buffer in response to determining that the buffer includes a shortest path tree that starts with the first qubit.

5. The method of claim 3, wherein determining the shortest path comprises:

determining, by a Dijkstra algorithm, a shortest path tree starting at the first qubit in response to determining that the shortest path tree is not included in a buffer;

storing the shortest path tree in a buffer; and

determining the shortest path based on the shortest path tree.

6. The method of claim 1, wherein the two-bit qubit gate is a CNOT gate and the single-bit qubit gate is a hadamard gate, and the logic instruction comprises the CNOT gate controlling the second qubit by the first qubit.

7. The method of claim 1, further comprising:

obtaining a directed graph representing the quantum circuit, nodes in the directed graph representing qubits in the quantum circuit, and edges in the directed graph representing the two-bit quantum gates.

8. The method of claim 7, wherein determining the directed path comprises:

an edge is determined that connects a first node representing the first qubit and a second node representing the second qubit together.

9. The method of claim 7, wherein the directed graph comprises a weighted graph, edges in the weighted graph having respective weights.

10. The method of claim 9, further comprising:

calculating weights of the directed paths based on the weights of the edges in the directed paths.

11. The method of claim 1, the quantum circuit having a non-strongly connected topology or a strongly connected topology.

12. The method of claim 1, wherein the quantum circuit comprises at least one of a superconducting quantum circuit, a nuclear magnetic resonance circuit, an ion trap circuit, and a silicon-based semiconductor quantum circuit.

13. An apparatus for compiling a quantum circuit, comprising:

a logic instruction obtaining module configured to obtain a logic instruction to be compiled for the quantum circuit, the quantum circuit including a plurality of qubits, the logic instruction being associated with a first qubit and a second qubit of the plurality of qubits, at least a portion of the plurality of qubits being operable with a two-bit qubit gate therebetween;

a path determination module configured to determine a directed path in the quantum circuit from the first qubit to the second qubit; and

a bottom layer instruction generation module configured to generate a bottom layer instruction for the quantum circuit corresponding to the logic instruction by adding a single bit quantum gate based on the directed path.

14. The apparatus of claim 13, wherein the underlying instruction generation module comprises:

a swap gate determination module configured to determine a swap gate corresponding to the directed path such that the first qubit and the second qubit are operated using one bi-bit qubit gate in the directed path;

a sequence determination module configured to determine a sequence of dibit quantum gates and single-bit quantum gates corresponding to the swap gates; and

a bottom layer instruction generation submodule configured to generate the bottom layer instruction based on the sequence of two-bit quantum gates and single-bit quantum gates.

15. The apparatus of claim 13, wherein path determination module comprises a shortest path determination module configured to determine a shortest path from the first qubit to the second qubit.

16. The device of claim 15, wherein the shortest path determining module comprises:

a shortest path reading module configured to read the shortest path from a buffer in response to determining that the buffer includes a shortest path tree with the first qubit as a starting point.

17. The device of claim 15, wherein the shortest path determining module comprises:

a shortest path tree calculation module configured to determine a shortest path tree by a Dijkstra algorithm in response to determining that the shortest path tree with the first qubit as a starting point is not included in the buffer;

a shortest path tree storage module configured to store the shortest path tree in a buffer; and

a shortest path determining submodule configured to determine the shortest path based on the shortest path tree.

18. The apparatus of claim 13, wherein the two-bit qubit gate is a CNOT gate and the single-bit qubit gate is a hadamard gate, and the logic instruction comprises the CNOT gate controlling the second qubit by the first qubit.

19. The apparatus of claim 13, further comprising:

a graph acquisition module configured to acquire a directed graph representing the quantum circuit, nodes in the directed graph representing qubits in the quantum circuit and edges in the directed graph representing the bi-bit quantum gates.

20. The apparatus of claim 19, wherein the path determination module comprises:

an edge determination module configured to determine an edge connecting together a first node representing the first qubit and a second node representing the second qubit.

21. The device of claim 19, wherein the directed graph comprises a weighted graph, edges in the weighted graph having respective weights.

22. The apparatus of claim 21, further comprising:

a weight determination module configured to calculate weights of the directed paths based on weights of respective edges in the directed paths.

23. The apparatus of claim 13, the quantum circuit having a non-strongly connected topology or a strongly connected topology.

24. The apparatus of claim 13, wherein the quantum circuit comprises at least one of a superconducting quantum circuit, a nuclear magnetic resonance circuit, an ion trap circuit, and a silicon-based semiconductor quantum circuit.

25. An electronic device, the electronic device comprising:

one or more processors; and

memory storing one or more programs that, when executed by the one or more processors, cause the electronic device to implement the method of any of claims 1-12.

26. A computer-readable storage medium, on which a computer program is stored which, when being executed by a processor, carries out the method according to any one of claims 1-12.