TW202134959A - Control method for a distributed processing system including a quantum information processor - Google Patents

Abstract

A method of transpiling a classical-quantum hybrid program to be executed by a distributed processing system is disclosed, the distributed processing system comprising one or more classical processors and a quantum information processor interrogable via classical analogue interaction means. The classical-quantum hybrid program includes a function to be executed by the quantum information processor. The method comprises parsing the classical-quantum hybrid program to generate an intermediate representation of the classical-quantum hybrid program, the intermediate representation comprising a series of basic blocks, each basic block comprising a sequence of instructions. The method comprises identifying basic blocks for which the sequence of instructions comprises one or more stream operation instructions, the one or more stream operation instructions configured to control interactions with the quantum information processor. The method comprises analysing the identified basic blocks to identify one or more subprograms for implementation on the one or more classical processor and quantum information processor. The method comprises, based on a target hardware configuration description for the analogue interaction means, replacing the one or more stream operation instructions of the subprograms with target hardware-specific code for controlling the analogue interaction means to interact with the quantum information processor, to generate a hardware-specific intermediate representation of the classical-quantum hybrid program. The method comprises translating the hardware-specific intermediate representation of the classical-quantum hybrid program into a transpiled classical-quantum hybrid program. A computer-readable medium, a distributed system controller, and a distributed processing system are also disclosed.

Description

Control method for distributed processing system including quantum information processor

This disclosure relates to a distributed computing system. More specifically, the present disclosure relates to a distributed computing system including at least one quantum information processor.

Current quantum computers usually cannot interpret instructions/codes by themselves. On the contrary, people usually interact with quantum information processors through some analog interaction tools to perform quantum operations and retrieve/read information. This has led to the development of the classical-quantum hybrid programming paradigm. As a powerful auxiliary processor of classical computers, quantum computers bear the elements of the inefficiency of classical methods.

Such classical quantum hybrid programs are usually hardware-specific, which may mean that they are inflexible and have limited functionality.

According to one aspect of the present invention, a method of transpiling a classical quantum hybrid program to be executed by a distributed processing system is provided. The distributed processing system includes one or more classical processors and a quantum information processor interrogable via classical analog interactive tools. The classical quantum hybrid program includes functions to be executed by the quantum information processor. The method includes parsing the classical quantum hybrid program to generate an intermediate representation of the classical quantum hybrid program, the intermediate representation including a series of basic blocks, each basic block including a sequence of instructions. The method includes identifying basic blocks whose instruction sequence includes one or more stream operation instructions configured to control interaction with the quantum information processor. The method includes analyzing the identified program blocks to identify one or more subroutines for implementation on one or more classical processors and quantum information processors. The method includes, based on the description of the target hardware setting of the analog interactive tool, replacing one or more stream operation instructions of the subroutine with specific code of the target hardware used to control the interaction of the analog interactive tool with the quantum information processor to generate The hardware-specific intermediate representation of the classical quantum hybrid program. The method includes converting the hardware-specific intermediate representation of the classical quantum hybrid program into a translated classical quantum hybrid program.

The method may further include marking a program call for inlining after identifying a basic block whose instruction sequence includes one or more stream operation instructions. The program can include one or more basic blocks. The method may also include inserting a basic block containing a program call marked for insertion. Marking the program call for insertion may include marking the program containing one or more basic blocks as belonging to the first set, for which the instruction sequence includes one or more flow operation instructions. Marking a program call for insertion may also include marking the program of any marked program from which the first set is reachable as belonging to the second set. Marking the program call for insertion may also include combining the first set and the second set to form a third set. Marking the program call for insertion may also include, for each program in the third set, identifying all calling programs that called the program, and if the calling program is already in the third set, or if the calling program is in the second set And call another program in the second set, then mark the call for insertion. In addition, if the calling program is in the second set and another program in the second set is called, the calling program is added to the third set.

Analyzing the identified basic block to identify one or more subroutines may include converting the identified basic block into a static single-assignment form, and additionally ensuring that each stream operation instruction depends on at most one dominating stream operation instruction (dominating stream operation instruction). instruction). Analyzing the identified basic block to identify one or more subroutines may also include analyzing the static single assignment form of the identified basic block to identify one or more subroutines for use in one or more classic processors. And implemented on the quantum information processor.

Analyzing the static single assignment form may include marking a loop for expansion within the identified basic block; and expanding the loop marked for expansion. Marking the loop for expansion in the recognized basic block may include locating a non-constant flow identifier in the recognized basic block; and may also include, if the non-constant flow identifier depends on the loop induction variable, then marking Used to expand the loop.

The stream operation instruction may include one of an OPEN instruction for starting a stream, a READ instruction for reading from an open stream, a WRITE instruction for writing an open stream, and a CLOSE instruction for deactivating an open stream. .

Ensuring that each flow operation instruction depends on at most one dominating flow operation instruction can include inserting a placeholder flow function where the branch paths of the flow operation merge.

Converting the identified basic block into a static single assignment form may include analyzing one or more of the control flow, the domination hierarchy, and the control dependency of the classical quantum hybrid program.

Analyzing the static single assignment form may include performing one or more of data flow analysis or constant propagation.

Replacing one or more stream operation instructions of the subroutine with the specific code of the target hardware used to control the analog interactive tool may include: identifying the subroutine of the subroutine, according to the subroutine's stream operation instruction and the target hardware setting description Subroutines are passed to the hardware/hardware backend so that the hardware backend can generate hardware configuration data and commands and define the hardware data flow, and insert commands into the classical quantum hybrid based on the configuration data, commands and hardware data flow The static single assignment form of the program to push data to/pull data from the hardware backend.

Analyzing the static single assignment form of the identified basic block to identify one or more subroutines for implementation on one or more classical processors and quantum information processors may include analyzing the flow dependency of the static single assignment form To construct a flow dependency graph, and modify the connected subgraph of the flow dependency graph to a strongly connected subgraph. Analyzing the static single assignment form can also include constructing the dependency graph based on the modified flow dependency graph, control dependency and data dependency of the static single assignment form of the classical quantum hybrid program; and identifying the strongly connected components of the dependency graph as subprograms.

The method may also include receiving source code for the classical quantum hybrid program.

One or more classic processors may include a field programmable gate array.

The method may also include allocating at least a part of the translated classical quantum hybrid program to one or more classical processors.

According to one aspect of the present invention, there is provided a computer-readable storage medium having instructions stored on the computer-readable medium, which when executed by one or more processors cause the one or more processors to execute such as The method of translating classical quantum hybrid program described in this article.

According to one aspect of the present invention, there is provided a computer-readable storage medium having a translated classical quantum hybrid program stored on the computer-readable medium, and the classical quantum hybrid program is performed according to the method for translating a classical quantum hybrid program as described herein Translation.

According to one aspect of the present invention, a distributed system controller is disclosed. The distributed system controller is configured to translate the classical quantum hybrid program to be executed by the distributed processing system. The distributed processing system includes the distributed system controller, one or more classical processors and interrogable via classical analog interactive tools. The quantum information processor, the classical quantum hybrid program includes functions to be executed by the quantum information processor. The distributed system controller includes one or more memories. The distributed system controller also includes one or more processors. The one or more processors are configured to parse the classical quantum hybrid program to generate an intermediate representation of the classical quantum hybrid program, the intermediate representation including a series of basic blocks, each basic block including a sequence of instructions. One or more processors are configured to identify basic blocks: the instruction sequence of these basic blocks includes one or more stream operation instructions, and the one or more stream operation instructions are configured to control the quantum information processor Interaction. One or more processors are configured to analyze the identified basic blocks to identify one or more subroutines for implementation on one or more classical processors and quantum information processors. The one or more processors are configured to replace one or more of the sub-programs with specific codes of the target hardware used to control the interaction between the analog interactive tool and the quantum information processor based on the description of the target hardware setting of the analog interactive tool. Multiple stream operation instructions are represented by the hardware-specific intermediate of the classical quantum hybrid program. The one or more processors are configured to translate the hardware-specific intermediate representation of the classical quantum hybrid program into a translated classical quantum hybrid program.

According to one aspect of the present invention, a distributed processing system is provided. The distributed system includes a quantum information processor. The decentralized system also includes one or more classic processors. The distributed system also includes a distributed system controller as described herein.

The computer program and/or code/instructions for executing the method as described herein can be provided to a device such as a computer on a computer-readable medium or computer program product. The computer-readable medium may be, for example, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, or a transmission medium used for data transmission (for example, for downloading codes via the Internet). Alternatively, the computer-readable medium may be a physical computer-readable medium (such as semiconductor or solid-state memory, magnetic tape, removable computer disk, random access memory (RAM), read-only memory (ROM), hard magnetic The form of film and optical disc (such as CD-ROM, CD-R/W or DVD).

Based on the teachings given herein, those skilled in the art to which the invention pertains will come to mind many modifications and other embodiments of the invention set forth herein. Therefore, it will be understood that the disclosure herein is not limited to the specific embodiments disclosed herein. In addition, although the description provided herein provides example embodiments in the context of certain combinations of elements, steps and/or functions may be provided by alternative embodiments without departing from the scope of the present invention.

Although various embodiments are described below, the present invention is not limited to these embodiments, and variations of these embodiments can well fall within the scope of the present invention defined only by the appended claims.

Quantum information processing focuses on information processing and calculation based on quantum mechanics. Although current digital computers encode data with binary digits (bits), quantum computers are not limited to two states. They encode information into quantum bits, or qubits, which can exist in superposition. Qubit is the unit of quantum information. Qubits can be implemented with atoms, ions, photons or electrons (for example) and work together to act as suitable control devices for computer memory and processors. In the following, the terms quantum information processor and quantum computer are used interchangeably. It should be understood that the quantum information processor includes complex quantum bits and the devices required to keep the qubits in a superposition state.

Quantum computers are expected to provide unprecedented advances in their ability to solve several types of problems exponentially faster than the best classical computers. However, fulfilling this prospect may require overcoming considerable technical challenges.

的特徵值，該矩陣

可以表示實體系統的哈密頓量（Hamiltonian）。量子子常式在經典最佳化迴圈內部運行。量子子常式包括準備由參數

參數化的擬設（ansatz）量子態

並測量期望值

。變分原理確保這個期望值總是大於矩陣

的最小特徵值。在經典最佳化迴圈中，可以反覆運算地調整參數

，直到滿足收斂條件。In order to at least partially alleviate the burden of these challenges, several classical quantum hybrid algorithms have been proposed. A classical quantum hybrid program is a program that includes one or more such classical quantum hybrid algorithms. In the classical quantum hybrid algorithm, both classical resources and quantum resources are used to perform computing tasks. This calculation task can be simple or complex. A non-trivial example is the Variational Quantum Eigensolver (VQE) algorithm, which uses quantum resources and classical resources to find variational solutions for eigenvalues and optimization problems that traditional classical computers cannot obtain. More specifically, the VQE algorithm is used to find (usually large) matrices

Eigenvalues of the matrix

It can represent the Hamiltonian of the entity system. Quantum routines operate inside the classical optimization loop. Quantum routines include preparation of parameters

Parameterized quasi hypothesis (ansatz) quantum state

And measure the expected value

. The variational principle ensures that this expected value is always greater than the matrix

The smallest eigenvalue. In the classic optimization loop, the parameters can be adjusted repeatedly

, Until the convergence condition is met.

In order to make the best use of the capabilities of the classical quantum hybrid program, a hybrid computing system is required, in which one or more classical processors execute most of the instructions of the program and are only outsourced to the quantum information processor for very specific tasks. This kind of hybrid computing system reduces the number of operations that the quantum information processor needs to perform, which means that errors can also be corrected more effectively. The computing tasks are distributed between the classical and quantum information processors.

Current quantum computers usually cannot interpret quantum computer programs by themselves. On the contrary, people usually use some classically controlled interactive tools (such as microwave generators) to interact with the quantum information processor to perform quantum operations on the quantum information processor and read information from the quantum information processor. Software is needed to configure analog interactive tools, prepare and process data, perform quantum information processor calibration, execute user-supplied programs, and perform classical parts of classical quantum hybrid algorithms. Standard solutions usually include the construction of classic programs that generate subroutines. These quantity subroutines are processed separately to generate, for example, microwave-level commands for execution by interactive tools. These microwave-level commands are usually interpreted by software in the laboratory to configure specific hardware settings. The hardware is set up and then the experiment is performed. Since there are many fixed interfaces between the user and the final system, this method is inflexible and has limited functions.

The inventor designed a compilation method for obtaining a single input program including classical instructions and quantum instructions, and outputting the translated program based on the target hardware specification to coordinate the distribution of processing tasks on appropriate hardware. The translated programs can be distributed accordingly on related classic processors, low-latency programmable hardware and interactive tools. This method has several obvious advantages. First, the variable control levels in the hybrid program enable quantum engineers, software engineers, and application end users to use the same system. This reduces the maintenance burden from multiple data packages and ensures a consistent experience between users and developers. Second, different hardware targets can be easily selected and updated. The hardware can be updated, which is needed to support the program or enable the program to be compiled more efficiently. Without any necessary changes, the program can be compiled to take advantage of newly available functions in the hardware, if available. Third, by entering a program that accurately describes what a person wants to do, but does not clearly state how or where it is done, the compiler has the best chance to find a way to use hardware targets to make the program run. method. This allows for fully customizable, extremely low-latency control of quantum hardware.

In the most general form, a compiler is a program that accepts program text in the first language as input and produces program text in another language as output, while retaining the meaning of the text. Most compilers convert high-level programming languages (such as C language) into machine instructions for executing functions on machine hardware.

Typically, the compiler includes a front-end software module that performs analysis of the input program text and generates a semantic representation of the input program text. The compiler usually also includes a back-end software module, which generates appropriate machine instructions according to the semantic representation of the input program. If the compiler has a clear design, the front end may not know the target language at all, and the back end may not know the source language at all. However, there are technical reasons that this strict separation may be inefficient, and in fact most compilers have some form of compromise. For this reason, terms such as "front-end" and "back-end" should be interpreted broadly.

A transcompiler, also known as a source-to-source compiler or translator, is a type of compiler that takes the original code of a program written in a programming language as its input and uses the same or different The programming language produces basically equivalent programs. Therefore, translators convert between programming languages at a similar level of abstraction.

In the translation method described in this article, the classical quantum hybrid program is provided in the first programming language or equivalent data representation, and the hybrid program can be hardware-agnostic, or only the target hardware can be provided specification. Classical quantum hybrid programs are deconstructed into semantic representations, and then certain hardware-specific codes are provided to execute certain commands on the distributed processing system. The translated classical quantum hybrid program is expressed in a second programming language or equivalent data (which can be the same as or different from the first programming language). Therefore, the method described herein converts high-level cross-hardware programs into at least part of hardware-specific high-level programs. In particular, the translated hybrid program is suitable for execution on one or more classical processors and quantum information processors.

Fig. 1 shows a distributed processing system 100 according to an embodiment of the present invention. The distributed processing system 100 includes a network 110, a distributed system controller 120, classic computing devices 130 and 135, and a hybrid computing device 140. The distributed processing system 100 may include more or fewer devices and components. The distributed system controller 120 and the hybrid computing device 140 will be described in further detail below.

The network 110 may be any known type of computer network, which implements wired or wireless communication between the computing device 130/135 and the distributed system controller 120 and between the distributed system controller and the hybrid computing device 140. The network may include, for example, a local area network (LAN), a wide area network (WAN), or the Internet. The distributed processing system may include a plurality of networks. For example, the computing devices 130 and 135 may communicate with the distributed system controller 120 wirelessly, and the distributed system controller 120 may communicate with the hybrid computing device 140 via a wired connection.

The hybrid computing device 140 includes one or more classical processors 150, an interaction module 160, and a quantum information processor 170. The hybrid computing device 140 of this example is configured to perform quantum operations on the quantum information processor 170 via the interaction module 160, while performing complementary classical operations on the low-latency dedicated classical processor 150 (for example, a field programmable gate array). These will be discussed in more detail further below.

The distributed system controller 120 can receive the classical quantum hybrid program from the user. For example, a user can send a computer executable file containing a classical quantum hybrid program from a third-party computer (such as the classical computing device 130) to the distributed system controller. Optionally, the distributed system controller 120 itself can support the programming function, so that the user can directly design the classical quantum hybrid program on the distributed system controller 120. In other embodiments, the hybrid computing device 140 itself may be configured to act as a decentralized system controller.

The distributed system controller 120 is configured to translate the classical quantum hybrid program according to the method described herein to generate the translated classical quantum hybrid program. The translated classical quantum hybrid program includes hardware specific codes used to control the interaction between the analog interaction tool of the interaction module 160 and the quantum information processor 170, as well as the hardware specific code used in one or more classical processors (such as the classical processor 150 or 135) the code executed on the computing device.

The distributed system controller 120 may be further configured to coordinate the execution of the program. This can be performed in any of several possible ways.

For example, the distributed system controller 120 can generate a translated classical quantum hybrid program, which can be executed on the controller 120 itself to directly control the quantum information processor 170, the classical processor 150, and optionally the device 130. And 135 operations performed on the classic computing device. In another example, the translated classical quantum hybrid program may include several code parts, and each code part is allocated to the classical processor and the interaction module 160 for execution from there.

In another example, the hybrid computing device 140 may be configured to act as a decentralized system controller. Therefore, the hybrid computing device can directly execute the instructions of the translated classical quantum hybrid program itself. In other examples, the distributed system controller 120 may only be responsible for creating the translated classical quantum hybrid program. The host device can be responsible for coordinating the execution of the translated program. The host device may include, for example, a computing device 130 or a computing device 135.

FIG. 2 depicts a block diagram of the distributed system controller 200, which can play the role of the distributed system controller 120 of FIG. The distributed system controller 200 is an example of a computer, in which computer-usable program codes or instructions that implement programs can be located and executed. Those skilled in the art will recognize that other architectures can be envisaged. The distributed system controller 200 is configured to perform methods such as those described below with respect to FIGS. 4 to 10.

The distributed system controller 200 includes a plurality of user interfaces, and these user interfaces include visualization tools such as a visual display 280 and a virtual or dedicated user input/output unit 240. The input/output unit 240 allows data registration and output with other devices/users connectable to the device 200. For example, the input/output unit 240 may provide a connection for the user to input through a keyboard, a mouse, and/or some other suitable input device. In addition, the input/output unit 240 may send output to the printer.

The distributed system controller 200 also includes one or more (classic) processors 210, a memory 220, a permanent memory 230, and a power system 260.

The distributed system controller 200 includes a communication module 250, which is used to send and receive communication between the processor 210 and the remote system. For example, the communication module 250 can be used to send and receive communications via a network 110 (such as the Internet). The communication module 250 can provide communication by using any one or both of a physical communication link and a wireless communication link.

The distributed system controller 200 also includes a port 270 for receiving, for example, a non-transitory machine-readable/computer-readable medium containing instructions to be processed by the processor 210.

The memory 220 and the permanent storage device 230 are examples of storage devices. A storage device is any piece of hardware that can temporarily and/or permanently store information, such as but not limited to data, functional form code, and/or other appropriate information. In these examples, the memory 220 may be, for example, a random access memory or any other suitable volatile or non-volatile storage device. The permanent storage device 230 may take various forms, depending on the specific implementation. For example, the permanent storage device 230 may contain one or more components or devices. For example, the permanent storage device 230 may be a hard disk drive, flash memory, rewritable optical disc, rewritable tape, or some combination of the above. The media used by the permanent storage device 230 may also be detachable. For example, a removable hard disk drive can be used for the permanent storage device 230.

The instructions of the processor 210 can be stored. For example, the instructions may be stored on the permanent storage device 230 in a functional form. These instructions can be loaded into the memory 220 for execution by the processor 210.

The processor 210 is used to execute software instructions that can be loaded into the memory 220. The processor unit 210 may be a group of one or more processors, or may be a multi-processor core, depending on the specific implementation. In addition, the processor unit 210 may be implemented using one or more heterogeneous processor systems, where the primary processor and the secondary processor are located on a single chip. As another illustrative example, the processor unit 210 may be a symmetric multi-processor system containing plural processors of the same type.

The processor 210 is configured to receive data, access the memory 220 and the permanent storage device 230, and respond to commands received from the memory 220 or the permanent storage device 230, from the communication module 250 or from the user input device 240. effect.

Those skilled in the art will recognize that the distributed system controller 200 of FIG. 2 is only an example. The distributed system controller can include more or fewer components and modules. For example, the distributed system controller may not have visual display capabilities.

FIG. 3 depicts a block diagram of a hybrid computing device 300, which can play the role of the hybrid computing device 140 of FIG.

The hybrid computing device 300 includes an input/output unit 240', a communication module 250', a memory 220', a permanent memory 230', and a power supply 260', and these components are configured to perform similar to those of the distributed system controller 200 The task performed by the component is similar to the task.

The hybrid computing device 300 also includes a quantum information processor 170 and an interaction module 160 for interacting with the quantum information processor 170.

The quantum information processor 170 may be any device capable of generating quantum states for processing. The quantum information processor 170 can be of any suitable type, and can use any known method to process qubits, including but not limited to the following methods: nuclear magnetic resonance, ion traps, superconductors, quantum dots, electrons on liquid helium, solid state auto Spin spectroscopy, cavity QED.

In one example, the quantum information processor 170 may include a superconducting circuit. In the superconducting circuit implementation of a quantum computer, the basic unit (qubit) of quantum computing can be physically realized in many different ways. One or more Josephson junctions can be combined with capacitors and/or inductors to form a high-quality non-resonant circuit whose lowest quantized energy level is used to define qubits. For example, a commonly implemented and successful design (called a charge qubit or transmon) exists in its simplest form: a single Josephson junction in parallel with a capacitor. The two electrodes of a qubit can be arranged in a variety of ways; examples include collinear arrangement of electrodes in a geometry similar to a dipole antenna, or the use of interdigitated capacitors, or one electrode in a cross shape and the other electrode. It is a common ground plane.

The interaction module 160 is configured to receive instructions for interacting with the quantum information processor 170 and execute these instructions. The interaction module 160 may include dedicated memory and/or permanent memory for converting some input commands into machine instructions for controlling the quantum information processor 170. For example, the interaction module 160 may include "back-end" software Modules are used to configure the intermediate representation of the classical quantum hybrid program for operation with analog interactive tools. The interaction module 160 can be additionally or alternatively configured to interact with the memory 220' and the permanent memory 230' of the hybrid computing device, and the memory 220' and the permanent memory 230' can be shared with the classic processor 150 .

The interaction module 160 includes an analog interaction tool for controlling interaction with the quantum information processor 170 to manipulate qubits, thereby performing quantum operations and measuring. In superconducting qubit quantum computers, the control and measurement circuit systems are usually realized by using planar circuit systems integrated with qubits on a chip, and/or using 3D electromagnetic waveguides and cavities embedded in the qubit chip . Therefore, although the interaction module 160 and the quantum information processor 170 of FIG. 3 are shown as independent components, they can be integrated to some extent. The interaction module 160 may include a circuit system for applying voltage to a specific point in the superconducting circuit or device, and for coordinating the microwave pulse applied to the quantum information processor 170.

Any single qubit gate can be realized by the rotation of the Bloch sphere. The rotation between the different energy levels of a single qubit is caused by microwave pulses sent to the antenna or transmission line coupled with the qubit, and its frequency resonates with the energy interval between the energy levels. In this case, the interactive module 160 may include an interactive tool in the form of a microwave generator. Coupling two qubits can be achieved by connecting them to an intermediate electrical coupling circuit. The coupling circuit can be a fixed element (such as a capacitor) or controllable (such as a DC-SQUID). In the first case, the decoupling of the qubits (during the time the gate is closed) can be achieved by tuning the qubits not to resonate with each other, that is, to make the energy gaps between their computational states different.

The interaction module 160 correspondingly includes an analog interaction tool for querying/controlling the quantum information processor 170.

The hybrid computing device 300 also includes one or more classic processors 150. The classic processor 150 is a low-latency hardware for performing classic operations. The classic processor 150 may include, for example, a field programmable gate array (FPGA). FPGAs usually include an array of programmable logic blocks and a hierarchical structure of reconfigurable interconnects that allow the programmable logic blocks to be connected in any of several different configurations. Logic blocks can be configured to perform complex combinatorial functions, or just simple logic gates (such as AND gates and exclusive OR (XOR) gates). In most FPGAs, the logic block also includes memory components, which can be simple flip-flops or more complete memory blocks. Many FPGAs can be reprogrammed to implement different logic functions, allowing flexible and reconfigurable calculations to be performed in computer software.

The hybrid computing device 300 is shown in FIG. 3 as if it is within a single device, where all components are tightly connected. However, those skilled in the art will recognize that other architectures can be envisaged. For example, the hybrid computing device itself can be distributed on multiple spatially separated equipment and components.

Those skilled in the art will recognize that the above-described distributed processing system, distributed system controller, and hybrid computing device are only examples, and other architectures can be envisaged.

For example, the distributed processing system 100 may include more or fewer devices. The distributed processing system may include, for example, a single classical processor, an interactive module, and a quantum information processor. In this case, the classic processor can be configured to translate the classic quantum hybrid program for use with the available classic processor, interactive tools, and available quantum information processor. Therefore, a dedicated distributed system controller 120 may not be needed. The classic processor can be further configured to execute the translated program after further compilation. Similarly, the dedicated low-latency processing hardware 150 of FIGS. 1 and 3 may or may not be required.

In use, the distributed system controller 120 may be configured to receive a classical quantum hybrid program. The program may include the target hardware specification, or the distributed system controller 120 may be configured to receive the target hardware specification for the program in some other way, such as via separate communication from an external device, or by consulting its memory. The target hardware specification includes information about the distributed processing system, such as which hardware is available and what component each hardware is connected to (and which analog hardware is available and which analog connection is available). The target hardware specification may include the minimum requirements for the implementation of the program, which includes detailed information, such as the number of qubits required to perform a quantum operation.

The distributed system controller 120 is also configured to translate the classical quantum hybrid program based on the target hardware specification according to a method substantially as described herein. The obtained translated classical quantum hybrid program correspondingly includes hardware specific instructions for implementing one or more quantum operations on the quantum information processor 170 using the interaction module 160. The translated classic subprogram may also include hardware specific instructions for implementing one or more classic operations on the dedicated classic processor 150. The translated classic subprograms can also include high-level (ie, basically cross-hardware) instructions for execution on other classic processors, such as classic computing devices 130, 135, or distributed system controller 120 On its own internal processor.

After translation/compilation, the obtained program can be executed by any suitable classical device combined with the hybrid computing device 140. For example, the translated program may be executed by the distributed system controller 120. If necessary, the distributed system controller 120 can compile any remaining cross-hardware parts of the compiler accordingly for execution on its processor or on the processor of an external device. When executing the translated program, the processor of the distributed system controller 120 can directly control the interaction module 160 and the dedicated processor 150 of the hybrid computing device 140. Optionally, the distributed system controller 120 may be configured to add a scheduling module (which may be in the memory/permanent memory of the distributed system controller or in the memory/permanent memory of a hybrid computing device). Provided software modules) to submit the configuration for scheduling processing. Optionally, the translated classic subprograms can be further converted into plural executable files, and these files can then be transferred to the relevant processor/interaction module for execution. The distributed system controller 120 may operate in some combination of these ways.

Roughly speaking, the translated program is a sequence of instructions that can be executed by a host system, which has the "net effect" of executing the original program. The instructions of the translated program itself can include instructions for configuring other subsystems, sending data to them, triggering them to execute code, and retrieving data from them. The final translated program can be very clear in nature; all instructions retained in the program can be directly executed on the host, but it will include configuring other machines to execute part of the program.

The translated classical quantum hybrid program can be executed by a separate host device (such as the classical computing device 130) instead. If necessary, the classic computing device 130 may correspondingly compile any remaining cross-hardware parts for execution on its processor or on the processor of an external device. When executing the translated program, the processor of the classic computing device 130 can directly control the interaction module 160 and the dedicated processor 150 of the hybrid computing device 140. Optionally, the classic computing device 130 can be configured to send a scheduling module (which can be the memory/permanent memory of the distributed system controller 120 or the classic computing device 130 or the memory/permanent memory of a hybrid computing device). The software module provided in the sexual memory) submits the configuration for scheduling processing. Optionally, the translated classic subprograms can be further converted into plural executable files, and these files can then be transferred to the relevant processor/interaction module for execution.

The method of translating the classical quantum hybrid program will now be described with reference to FIG. 4. In the following description, the quantum information processor is described as a superconducting qubit quantum information processor in some places, and the interactive module is described as an analog interactive tool in the form of a microwave signal generator. However, those skilled in the art will recognize that this is for descriptive purposes only and not for limitation. In particular, the quantum information processor may include any suitable quantum information processor, and the analog interaction tool may be any analog interaction tool suitable for interacting with the quantum information processor. The method of FIG. 4 may be executed by, for example, the distributed system controller 120 described above with respect to FIG. 1.

Fig. 4 shows a flowchart of a method of translating a classical quantum hybrid program to be executed by a distributed processing system. The distributed processing system includes one or more classical processors 150 and a quantum information processor 170, which can be interrogated via a classical analog interaction tool (included in the interaction module 160 in this example). The classical quantum hybrid program includes at least one function to be executed on the quantum information processor 170.

The classical quantum hybrid program can be expressed in any high-level programming language that is not hardware specific. For example, a classical quantum hybrid program can be written in Python, C, C++, Fortran, Pascal, or any other such language. The classical quantum hybrid program may include a program for calibrating the quantum information processor, and may include a program for implementing quantum logic operations on the quantum information processor. The program implemented by the quantum information processor usually includes one or more stream operation instructions, which correspond to the instructions of the analog interactive tool after the translation method. Therefore, the stream operation instruction can be considered as the interface between the processing operation performed on the quantum information processor and the processing operation performed by the rest of the distributed processing system. The stream operation instruction describes the interaction with the quantum information processor. For example, the stream operation instructions may include instructions for a microwave signal generator to generate microwave signals for interaction with the quantum information processor.

At 410, the classical quantum mixing formula is parsed to produce an intermediate representation. The middle representation includes a series of basic blocks, and each basic block includes a sequence of instructions. Therefore, the intermediate representation is essentially similar to assembly. As a result of this intermediate representation, each instruction is essentially a "single-effect". The instructions are organized into lists, single-effect instructions one after the other (though technicians will understand that the intermediate representation can contain several multiple-effect instructions). Jumps and/or conditional jumps realize non-linear flow through instruction lists. The basic block can be a continuous code block, starting with a label instruction, so that the block can be recognized, and ending with a final jump instruction. A basic block includes a sequence of instructions with an entry point and an exit point. You cannot jump to the middle of the basic block from anywhere in the program, nor can you exit the basic block from the middle.

An example of a basic block is as follows: LABEL("A") //Each block starts with the label "instruction" that identifies the block MOV("X", 3)//The movement instruction sets the variable "x" to the value 3 JMP "B"//Each block ends with a jump (or conditional jump) instruction, specifying (or allowing calculation) the next block to be executed.

The basic instructions in the basic block can take one of the following forms: LABEL(unique_label_name)//Specify a unique id for the basic block EVAL(expr)//Evaluate the expression in expr MOV(unique_var_name, expr)//Move the value in expr to the specified variable JUMP(label_name) //Jump to label CJUMP(expr, label_name, label_name)//Jump to one of the two labels according to the value condition of expr And expressions can be stored as a tree structure, which can include basic structures, such as constant values, references to variables, and arithmetic operations: CONST(const_value) //Description of constant value TEMP(unique_var_name) //reference to variable value ADD(expr, expr) // expression, its value is the sum of two expressions

Expressions can also include more complex structures, such as function calls. In traditional compilers, these function calls will eventually be converted into more basic instructions, such as those described above, but in this method, these functions Calls are converted more selectively. The form of the calling expression can be, for example: CALL(function_name, expr_list)

"Special" function calls are methods that provide stream operations (for example, OPEN, READ, WRITE, CLOSE) in the input program. These function calls can have their own function_name value, strm_open, strm_read, strm_write, strm_close.

The compiler can support, for example, four low-level instructions that perform operations on streams: OPEN: The list of one or more streams is opened immediately, marking their use as synchronized. Similar to data analysis, this can be considered as an assignment to these opened streams; READ: Read from a specific (open) stream, and specify the data array or the length of the data to be returned; WRITE: Write to a specific (open) stream, and also specify the data array or the length of the data to be returned; CLOSE: The list of one or more streams is closed. For these same streams, the command must logically follow the OPEN command. Similar to data analysis, this can be thought of as assigning values to these streams.

At 420, a basic block with one or more stream operation instructions is identified. Stream operation instructions involve instructions that will be executed by an analog interactive tool (in this example, a microwave signal generator). Since stream operation instructions usually involve commands for microwave signal generators that interact with the superconducting qubits of the quantum information processor, the identification of basic blocks containing stream operation instructions can be outsourced to microwave signals for identification The operation of the generator is useful (as opposed to classic processors).

At 430, the identified basic blocks are analyzed to identify one or more subroutines for implementation on one or more classical processors and quantum information processors. This may include converting the identified basic block into a single-stream assignment (SSA) form, and further ensuring that the basic block is converted into a form in which each stream operation instruction depends on at most one dominant stream instruction. In the design of the compiler, the SSA form is an attribute of the intermediate representation. It requires that each variable be assigned only once, and each variable is defined before it is used. Converting the identified basic block into the SSA form may include, for example, replacing the target of each assignment with a new variable, and replacing each use of the variable with the version of the variable that reaches that point.

By converting the code into SSA format, data flow analysis becomes easier. Consider an example: MOV(TEMP(‘x’), CONST(3)) // x=3 MOV(TEMP(‘y’), ADD(TEMP(‘x’), CONST(2)) // y=x+2 The second statement is data dependent on the first instruction, so the data flow analysis will find that there is a "use" of temp "x" in the second instruction, which is linked to the first instruction " The "definition"/"def" of x". Data flow analysis is the process of establishing a use-def chain. Consider the next example: MOV(TEMP(‘x’), CONST(3)) // x=3 MOV(TEMP(‘y’), ADD(TEMP(‘x’), CONST(2)) // y=x+2 MOV(TEMP(‘z’), ADD(TEMP(‘x’), CONST(2)) // z=x+2 Instruction 2 uses the definition of x in instruction 1. Instruction 3 uses the definition of x in instruction 1. Since instruction 3 has no dependency on instruction 2, the order of execution of instruction 3 and instruction 2 does not matter, so it is possible to switch them or execute them concurrently. Consider the next example: MOV(TEMP(‘x’), CONST(3)) // x=3 MOV(TEMP(‘y’), ADD(TEMP(‘x’), CONST(2)) // y=x+2 MOV(TEMP(‘z’), ADD(TEMP(‘y’), CONST(2)) // z=y+2 Instruction 2 uses the definition of x in instruction 1. Instruction 3 uses the definition of y in instruction 2. Since 3 is dependent on 2 and 2 is dependent on 1, the order in which instructions can be executed is fixed. Consider the next example: MOV(TEMP(‘x’), CONST(3)) // x=3 MOV(TEMP(‘x’), ADD(TEMP(‘x’), CONST(2)) // x=x+2 MOV(TEMP(‘x’), ADD(TEMP(‘x’), CONST(2)) // x=y+2 Instruction 2 uses the definition of x in instruction 1. Instruction 3 uses the definition of x in instruction 2.

Sometimes, control flow makes it impossible to determine the latest version of a variable. In these cases, the compiler will insert an artificial definition named Phi(Φ) function or Phi node for the variable. This new definition merges all the incoming versions of the variable to create a new name for it. Since it is impossible to determine which of the several branches will be followed at runtime (for example, whether the conditions in the IF statement are met), the conversion to the SSA form may involve inserting such a Phi function, which is the result of "merging" different options. The Phi function can be implemented by, for example, using the same location in memory as the destination of any operation that generates input to the Phi function. The Phi function is a reserved position function, which is explained during the compilation and optimization steps, but does not need to be actually executed.

Take the following high-level pseudo code as an example: if(y) then: x = 3; else: x = 2; y = x+2; This pseudocode can be represented in the intermediate representation as a series of basic blocks in the following form: LABEL("START") MOV(TEMP(‘y’), ?) // y is set to "something" in advance CJUMP( TEMP(y), LABEL("A"), LABEL("B")) //If y is true, then execute A, if y is false, then execute B LABEL("A") MOV(TEMP(‘x’), CONST(3)) // x=3 JUMP("C") LABEL("B") MOV(TEMP(‘x’), CONST(2)) // x=2 JUMP("C") LABEL("C") MOV(TEMP(‘y’),ADD(TEMP(‘x’),CONST(2))) // y = x + 2 JUMP("END") LABEL("END") JUMP("END") In this pseudo code, the statement y=x+2 is obviously the "usage" of temp x. According to the program flow, the definition of x it uses is either the definition in the "x=3" instruction or the definition in the "x=2" instruction. Therefore, the use-def chain constructed in this way is many-to-many, because any definition may have plural usage, and any usage may have plural definitions. The SSA form simplifies data analysis by ensuring that the use-def chain is many-to-one. There is only one definition for any given use of a variable. This is achieved by converting pseudo-code as follows: LABEL("START") MOV(TEMP(‘y’), ?) // y is set to "something" in advance CJUMP( TEMP(y), LABEL("A"), LABEL("B")) //If y is true, then execute A, if y is false, then execute B LABEL("A") MOV(TEMP(‘x1’), CONST(3)) // x1=3 JUMP("C") LABEL("B") MOV(TEMP(‘x2’), CONST(2)) // x2=2 JUMP("C") LABEL("C") MOV(TEMP(‘x’), PHI(TEMP(‘x1’), TEMP(‘x2’)//x = x1 or x = x2, as indicated by the previous program flow MOV(TEMP(‘y’), ADD(TEMP(‘x’), CONST(2))//y = x+2 JUMP("END") LABEL("END") JUMP("END")

The method used to insert the Phi function to ensure the SSA form is well known and given in the standard compiler documentation. They include the analysis of the potential path of the "flow" of the general procedure (control flow analysis), and can be effectively performed by further analysis of the control flow to produce the so-called dominance hierarchy, from which each can be calculated The dominance frontier of the block. If all paths in the control flow from "A" to the end of the program pass through "B", then block "A" dominates another "B". If block "C" is the first block that arrives on any control flow path starting from "A" and is not dominated by "A", then it is located on the dominated boundary of "A".

The SSA format is well known. However, current methods extend the principles of the SSA form to the concept of stream operations.

Logically, flow operations both affect the state of a particular flow ("define" a new flow state), but also depend on the state of a particular flow (the "usage" of the current flow state). One exception is the strm_open instruction, which does not depend on the ("usage") stream; instead, it sets the stream to an open and blank state, similar to "defining" them to a specific initial state.

The strm_open instruction can be defined as having the following form: EVAL(CALL(‘strm_open’, exprlist(CONST(‘unique_strm_name_1’), CONST(‘unique_strm_name_2’), …) ))

The strm_close instruction can be defined as having the following form: EVAL(CALL(‘strm_close’, exprlist(CONST(‘unique_strm_name_1’), CONST(‘unique_strm_name_2’), …) ))

The strm_read instruction can be defined as having the following form: EVAL(CALL(‘strm_read’, exprlist(CONST(‘unique_strm_name’), EXPR, …) )) Among them, EXPR is an expression that evaluates the number of samples to be read from the stream.

The strm_write instruction can be defined as having the following form: EVAL(CALL(‘strm_write’, exprlist(CONST(‘unique_strm_name’), EXPR, …) )) Among them, EXPR is an expression for evaluating samples or sample arrays to be written to the stream.

In the above, the provided stream name is given as a constant expression. This allows the construction of a use-def chain of stream operations. Need to deal with the situation where these expressions are non-constant, but will be discussed later.

Similar to the Phi function/Phi node, when it is impossible to determine which branch of the program will be followed at runtime, the Phi function/Phi node helps to represent the variable. In this extended form of SSA, in the bifurcation path of the flow operation Insert a similar placeholder stream operation at the merge place, which is called StreamPhi operation (or "strm_phi") in this article. By using such StreamPhi operations, each stream operation depends on at most one previous (dominant) stream operation instruction.

People can introduce the strm_phi operation in the form: EVAL(CALL(‘strm_phi’, exprlist(CONST(‘unique_strm_name’)))) strm_phi is also considered a usage and definition of stream.

As in the standard SSA format, the strm_phi operation can be inserted by analyzing the control flow, the generated dominance information, and the current use-def chain. This produces a set of use-def chains, where each strm_open, strm_write, strm_read, strm_close command has a dependency on only one previous stream_operation.

The Strm_phi operation still relies on the plural previous stream_operation, as can be seen in this example, there is no renaming of the streams to ensure that there is only one definition for each stream (we work implicitly rather than explicitly in the form of SSA): data1 =? data2 =? y =? strm_open(‘strm1’,) if(y) then: strm_write(‘strm1’, data1) x = 3; else: strm_write(‘strm1’, data2) x = 2; y = x + 2; strm_phi(‘strm1’,)//This strm_phi command is inserted because two different control flow paths merge with strm1 in different states. strm_write(‘strm1’, data1) strm_close(‘strm1’)

It is now possible to construct a stream dependency chain, where individual stream operation instructions are marked as dependent on previous operations where appropriate, and StreamPhi operations are marked as dependent on plural previous operations. The flow dependency graph/flow dependency chain is a directed graph, in which each node represents a flow operation instruction, and each directed edge represents the dependence of one flow operation instruction on another.

This extension of the SSA format also covers stream operation instructions, sometimes referred to as the single stream state format in this article.

Those skilled in the art will recognize that the entire intermediate representation of the classical quantum hybrid formula can be converted into SSA form. In other examples, only the basic block identified at 420 can be converted into SSA form.

By converting the identified basic block into this SSA form, the program can be optimized to a certain extent to perform control flow analysis and data flow analysis, and perform appropriate transformation and optimization of the program.

Control flow analysis (CFA) is a static code analysis technique used to determine the control flow of a program. The control flow can be expressed as a control flow graph (CFG). CFG is a graphical symbol representation of all paths that may pass through the program in the program execution process. In CFG, each node in the graph represents a basic block (at least some basic blocks are in the form of SSA), and the directed edges between adjacent nodes can be used to represent jumps in the control flow. The CFG includes at least one entry block and at least one exit block. The entry block enters the CFG through the entry block, and the exit block exits the CFG through the exit block. The operation or basic block is said to dominate the second operation or second basic block when every path from the entrance to the second operation or second basic block passes through the first operation or basic block. Although the control flow graph and the graph operations on the control flow graph may be further described below, those skilled in the art will recognize that such graphs and graph operations are described for illustrative purposes only. CFA is usually performed by known calculation procedures.

Data flow analysis is a technique used to collect information about possible sets of values calculated at different points in a computer program. The control flow graph (CFG) of a program can be used to determine the parts of the program to which a specific value assigned to a variable can be propagated. Data flow analysis can be performed by any known calculation program.

Analyzing the identified basic blocks to identify one or more subprograms for implementation on one or more classical processors and quantum information processors may also include analyzing the single-stream state form of the classical quantum hybrid program for identification Used for any subprograms implemented on the quantum information processor 170. The subroutine includes a collection of single instructions. Any block that contains one such instruction is regarded as a subroutine block, but not all instructions in these blocks are necessarily instructions within the subroutine. The main purpose of subprogram identification is to identify instructions that have strict timing requirements for other instructions, or to perform stream operations. These instructions are not suitable for execution on the host controller, and must be executed (directly or indirectly) in a specific hardware component(s) that has the physical ability to cause any streaming operation to occur, and realizes the quantum The actual query of the device, and has the ability to execute any other instructions relative to other instructions and stream operations within a specific short time window.

Stream flow dependencies can be considered time-critical, so all such dependent instructions can be added to independent subroutines. Any other instruction (or set of instructions) that has a dependency on it already in the subroutine and any other instruction (or instruction set) that has a dependency on the instruction already in the subroutine can be added to the subroutine, and any instruction that now satisfies the constraint is also added to the subroutine. Can be added to the subroutine.

An example method for efficiently discovering all such instructions is as follows. First, generate a directed graph of all dependencies, where nodes represent instructions, and edges point to the direction of dependency (from an instruction to the instruction it depends on). Second, insert additional pseudo-dependencies so that any stream instruction can be reached from any other stream instruction on the graph (in typical cases, this can be as simple as inserting a dependency from strm_open to strm_close). This ensures that all flow instructions form a strongly connected component of the graph (by definition). Third, use Kosaraju's algorithm or similar algorithms to detect strong connected components. The strongly connected components of the graph will now contain all the instructions required by the subroutine, because any instruction on the dependent path that both leaves the subroutine and enters the subroutine again will obviously constitute a part of the strongly connected component itself.

A more detailed method of identifying this subroutine will be further described below.

The single-stream state form of the classical quantum hybrid program can be analyzed to identify any sub-programs for implementation on the classical processor 150 or the classical computing devices 130, 135.

At 440, based on the description of the target hardware setting of the microwave signal generator, one or more low-level flow operation instructions of the identified subprogram are used to control the target hardware specific of the interaction between the analog interactive tool 160 and the quantum information processor 170 Code replacement to produce a hardware-specific intermediate representation of the classical quantum hybrid program. As will be described in further detail below, the target hardware specific code used to control the analog interactive tool is provided by passing relevant commands to the relevant target hardware back-end module, and the relevant commands can be stored in the memory of the interactive module 160 Or in the memory of the distributed system controller 120. The target hardware specific code provides, for example, hardware setting instructions required for generating microwave signals for interacting with the quantum information processor 170.

Similarly, the subprogram used to control the low-latency classic processor 150 is identified, and the target hardware specific code for controlling the low-latency classic processor 150 is inserted with the help of the related target hardware back-end module.

The target hardware specific codes of the classic processor 150 and the quantum information processor realize fast and effective processing of the classic quantum hybrid operation. For example, such an instruction may specify the inductive variables that the classic processor 150 relies on, for example, iterate through the operation of the microwave signal generator.

At 450, the hardware-specific intermediate representation of the classical quantum hybrid program is translated into the translated classical quantum hybrid program. In particular, the translated classical quantum hybrid programs mainly include high-level codes. However, any operations that are now required to run on the classical processor 150 or the quantum information processor 170 are represented by hardware specific codes used to implement those operations on the relevant processor.

Fig. 5 shows a flowchart of the method for translating a classical quantum hybrid program as shown in Fig. 4, and provides further details. The method starts at 502.

At 504, the classical quantum hybrid formula is parsed into an intermediate representation (as at step 410).

At 506, several basic blocks are marked for insertion, especially those basic blocks that contain one or more stream operation instructions. Marking the basic block for insertion may include marking the basic block whose instruction sequence includes one or more stream operation instructions as belonging to the first set, and marking the basic block of any marked basic block from which the first set can be reached To belong to the second set, and combine the first set and the second set to form a third set, then, for each basic block in the third set, identify all callers of the basic block, and if the basic block is in the first set In one set, or if the basic block is in the second set and call the basic block in the second set, mark the basic block for insertion. Insertion (also called insertion extension) is a form of compiler optimization that replaces the function call point with the body of the called function.

At 508, the basic block marked for insertion is inserted.

Fig. 6 shows a flowchart of a method of marking basic blocks for insertion. At 602, the method starts. At 604, a directed graph is constructed. A directed graph is a graph composed of a set of vertices/nodes connected by edges, where the edges have directions associated with them. In particular, programs/basic blocks are allocated to nodes. The edges of the graph are related to the relationship between the basic blocks. In particular, directed edges are formed between any calling program and the called program. Those skilled in the art will recognize that the graph does not need to be generated in any physical sense, and only performs an analysis similar to this graph construction.

If there is a path between all pairs of vertices, the directed graph is said to be strongly connected. The strongly connected components of the directed graph are maximally strongly connected subgraphs. At 606, any strongly connected components of the directed graph constructed at 604 are identified and marked as looped.

。在610處，從其可到達第一集合

中的基本塊的任何基本塊被表示為屬於第二集合

。At 608, any basic block containing stream operation instructions is marked as belonging to the first set, represented here as

. At 610, the first collection can be reached from it

Any basic block in the basic block is represented as belonging to the second set

.

。At 612, the first set and the second set are combined to form a third set,

.

的程序建構工作列表

。At 614, from the third set

Procedural construction work list

.

是否為空的確定。如果

為空，則方法在618處結束。如果

不是空的，則該方法前進到620，在620處，從

中移除第一程序A 。At 616, make a statement about

Is it empty? if

If it is empty, the method ends at 618. if

Is not empty, then the method proceeds to 620, at 620, from

Remove the first program A.

的所有調用者。在624處，針對每個調用者做出關於該調用者是在第三集合

中還是該調用者在

中並調用

中的另一個程序的確定。如果確定為否定的，則方法前進到步驟616。可選地，如果確定是肯定的，那麼調用被標記用於插入。如果調用者不在

中，則調用者被添加到

和

。At 622, find

All callers of. At 624, for each caller, make a statement about whether the caller is in the third set

Or the caller is in

And call

The determination of another program in. If the determination is negative, the method proceeds to step 616. Optionally, if the determination is positive, then the call is marked for insertion. If the caller is not there

, The caller is added to

with

.

In this way, the relevant basic block is marked for insertion.

Referring again to FIG. 5, at 510, an analysis of the control flow, domination hierarchy, and control dependency of the program is executed. Control flow, domination hierarchy, and control dependency can be recalculated at several stages in the entire execution program of the translation method.

At 512, the intermediate representation of the basic block containing one or more stream operations is converted into a single static analysis form. At this stage, each variable is assigned only once, and each variable is defined before use, but the flow operation instruction itself may not be arranged in SSA form.

At step 514, data flow analysis is performed. The use of a variable is mapped to the previous assignment of the variable, so that for any given instruction, it is clear that the given instruction has "data dependence" of the previous instruction, and vice versa. Since the generated code is in SSA form, if the assignment is not in the same basic block, you can simply move up the dominance tree until you find an assignment.

At 516, constant propagation is performed. According to the data flow analysis, you can check the expressions to find out whether they are constants, or simple expressions with constant parameters (or even internal/external program calls). In this case, these expressions can be constant values replace. This reduces the data dependence in the program and makes the parameter analysis of key instructions (such as stream operation instructions) easier/possible to execute.

At 520, a basic block containing a loop is identified, where the loop contains one or more flow operation instructions, and the associated loop is marked for expansion. Loop unwinding (also called loop unwinding) is a loop transformation technique that tries to optimize the execution speed of the program at the expense of the binary size of the program. At 522, the marked loop is expanded, and at 524, constant propagation is performed again.

In any loop in the program (where the accessed stream is marked as a variable in the loop), it is beneficial to expand (copy and repeat the code to eliminate the loop) so that the accessed stream is constant. Once the basic block containing the flow operation instruction in the loop is identified, the loop can be marked for expansion by locating the non-constant flow identifier in the recognized basic block, and if the non-constant flow identifier depends on When loop induction variables are used, the loop mark is used for expansion. Figure 7 shows a flowchart of a method 700 for marking loops for expansion, expanding marked loops, and performing constant propagation. At 702, the method starts.

At 704, identify any natural loops in the program. This can be performed using any known method. In one example, if the control flow dependency graph is considered, any edge from the dominating block in the control flow is considered to form the back edge of the loop, where the head of the loop is the dominator, and the loop body contains Any basic block that can be reached by the path through the back edge. Those skilled in the art will recognize that any method can be used to detect loops in the program.

At 706, any combinable natural loops are combined, that is, any natural loops in the head of the same loop form a single natural loop.

At 708, the inductive variable is tested. Inductive variables especially refer to any variable that only adds or subtracts a constant value to itself in the loop body.

At 710, search for any non-constant flow identifier in the flow operation instruction. If any identifier depends on the loop induction variable (ie, if the flow identifier is non-constant within the loop), then the loop is marked for expansion (712).

For any marked loop, find the value of any escape expression from the loop constant and induction variable at each iteration to calculate the iteration count (714).

At 716, any marked loop blocks are replaced with duplicates (the loop is expanded), and it is ensured that the jump instructions change their corresponding targets accordingly.

At 718, constant propagation is performed to make the stream identifier constant.

The method ends at 720. By expanding the loop in this way, it is easier to put the program in a single-flow state.

Referring again to FIG. 5, at 526, the program is placed in a single-stream state form. As described above with respect to FIG. 4, the single-stream state form is an extension of the SSA form, in which the basic block is converted into a form in which each flow operation instruction depends on at most one dominating flow instruction.

According to the single-stream state form of the program, a stream dependency chain can be established at 528, where each operation is marked as dependent on the previous operation, and the StreamPhi operation is marked as dependent on the plural previous operation. The OPEN and CLOSE operations enable the same stream to be accessed without complete dependence, effectively enabling the program to clearly state where uninterrupted control of the quantum information processor is needed and where it is not needed.

At 530, this single-stream state form of the program is analyzed to identify any subprograms for implementation on one or more classical processors, and one or more for implementation on the quantum information processor Subroutines. The method for detecting the subroutine is further defined in relation to Figure 8 below. Figure 8 shows a flow chart of a method for analyzing (extended) static single-assignment forms (also known as single-flow state forms) to identify applications in one or more classical processors and quantum information One or more subroutines implemented on the processor. In particular, according to the analysis of the single-flow state form of the program, each flow operation instruction can be associated with a node of the flow dependency graph, where the directed edges of the flow dependency graph indicate that one flow operation instruction depends on another. At 802, the method starts.

The flow dependency graph can be divided into connected subgraphs (804) (ignoring the directionality of the edges). When a graph or subgraph has at least one vertex and there is a path between each pair of vertices, it is said to be connected.

Each connected subgraph of the flow dependency graph is modified to ensure strong connectivity (806). If every vertex of the graph is reachable from every other vertex, the graph is said to be strongly connected. If there is a path in each direction between each pair of vertices in a directed graph or subgraph, the graph is strongly connected. Therefore, modifying each flow-dependent subgraph may include ignoring the directionality of the edges and/or introducing additional edges.

At 808, the dependency graph is constructed by combining the edges of the control dependency graph, the data dependency graph, and the flow dependency graph. The dependency graph is a directed graph, which represents the dependency relationship between several objects. Correspondingly, the dependency graph captures the dependency relationship between the various variables of the program and the flow.

At 810, Kosaraju's algorithm is used to find the strongly connected components of the dependency graph. Kosaraju's algorithm (also known as the kosaraju-Sharir algorithm) is a linear-time algorithm used to find the strongly connected components of a directed graph. Those skilled in the art will recognize that other suitable algorithms can be used to determine the strongly connected components of the directed graph. Each strongly connected component of the directed graph represents a subroutine (812). The subroutine entry point is designated as the lowest common ancestor of all subroutine elements in the control dominance tree (814). The dominant boundary of the entry point marks the guaranteed exit point, and the subroutine points that flow into these nodes are marked as the exit (816).

At 818, the method ends.

Referring again to FIG. 5, based on the description of the target hardware setting, any flow operation in the identified subroutine is replaced by the target hardware specific code used to control the interaction between the analog interaction tool and the quantum information processor. The method for changing the formula in this manner is further described below with respect to FIG. 9. At 902, the method begins.

At 904, the subroutine is decomposed into basic blocks of stream operations, or called subroutines. In particular, the subroutine spans multiple basic blocks. For processing, it is useful to group flow operation instructions in blocks (because when an instruction is executed, all flow operation instructions are executed). Flow subroutine refers to a group of flow operation instructions in the same subroutine.

At 906, based on the stream used and any available target hardware configuration information, the subroutine is passed to the relevant hardware backend. The back-end can define the execution type for each subroutine, and insert the statement into the main program where the execution needs to be triggered based on the execution type.

The backend can query the data source/target, including any actual data of constants (912). The backend can define what data to send (914). In addition, statements are inserted into the main program to push data to/pull data from related hardware as needed (916). At 918, the method of FIG. 9 ends.

The subroutine does not necessarily consist of consecutive instructions in the entire program. They can be interlaced with other program elements, or even interlaced with each other. They also have dependencies on external programs (for example, data dependencies on variables used or set). Subroutines are those parts of a program that are intended for distributed execution on the various available components of a distributed processing system. Referring again to FIG. 5, at 534, these subroutines are correspondingly separated from those subroutines that appear before and after the subroutine from the subroutine itself. This includes the configuration and data retrieval commands generated at 532. The method for isolating subroutines is further provided with respect to Figure 10 below.

Referring to Figure 10, the method starts at 1002. At 1004, the basic block that can be reached from the entry of the subroutine without the exit is marked as the subroutine block. Insert an "execute" block (1006) between the exit block and the non-subprogram block. The exit block of the subroutine is defined as the block that can be executed just before the execution of the non-subroutine block in the subroutine.

At 1008, the block structure is copied and inserted between the execution block and the non-subroutine block. The original block is referred to herein as a "pre-processing block", and the new block is referred to as a "post-processing" block. The subroutine command is the command (1010) in the subroutine.

At 1012, 1014, and 1016, various blocks are marked. In particular, an instruction is marked as an "input" instruction, in which a subroutine or another input instruction depends on it; if an instruction depends on a program, the instruction is marked as an "output" instruction; and if an instruction depends on being absent If the instruction in the subroutine is not in the subroutine, the instruction can be marked as "parallel".

At 1018, the output instruction is moved to the corresponding position in the post-processing block. In the case of variable assignment in the preprocessing block, insert instructions to push the variable value into the pipeline (1020). The pipeline includes first-in-first-out stacking of variable values. This value can be retrieved in post-processing (1022). The conditional jump instruction in the post-processing is also modified to retrieve the value (1024) from the pre-processing block via the pipeline. The method of FIG. 10 ends at 1026.

Referring again to Figure 5, at 536, the program is converted to a standard high-level representation. That is, at 536, the code is converted into a translated classical quantum hybrid program. The translated classical quantum hybrid program is different from the original classical quantum hybrid program in several respects. The most obvious one is that it contains some hardware-specific codes to replace the codes related to stream operations. The translated classical quantum hybrid program is accordingly generated for execution by the distributed system controller.

Those skilled in the art will recognize that although in FIG. 5, the translated classical quantum hybrid program is used for execution on the distributed system controller, which in turn controls the classical processor 150 and the quantum information processor, The translated program can be designed to be executed by another device. For example, the translated program can be executed on a PC, which is located in a laboratory, or has low-latency communication with hardware in the laboratory. The program can be configured to directly and seamlessly configure the hardware to execute subroutines as needed during execution, or it can be configured to submit the configuration to the scheduling system.

At 538, the method ends.

FIG. 11 shows a computer-readable medium 1100 according to some examples.

The computer-readable medium 1100 stores units, where each unit includes instructions 1110 that, when executed, cause a processor or other processing device to perform a specific operation. The computer-readable medium 1100 includes instructions 1110 that, when executed, cause a processing device to implement a method as described herein.

The computer-readable medium, such as the computer-readable medium 1000, can interact with the device such as the distributed system controller 200 via the port of the device 200 (for example, the port 270).

Variations of the described embodiments are envisaged, for example, the features of all the disclosed embodiments can be combined in any way.

For example, in one application, the method used herein can be used as part of the calibration/tuning procedure of a distributed processing system.

It will be understood that the embodiments of the present invention can be implemented in the form of hardware, software, or a combination of hardware and software. Any such software can be stored in the form of volatile or non-volatile storage devices (such as storage devices like ROM (whether erasable or rewritable)), or in the form of memory (such as RAM, memory chips, It is stored in the form of equipment or integrated circuit), or stored on optical or magnetic readable media (such as CD, DVD, magnetic disk or tape). It will be understood that the storage device and the storage medium are embodiments of a machine-readable storage device, which are suitable for storing one or more programs that, when executed, implement the embodiments of the present invention. Correspondingly, the embodiments provide a program and a machine-readable storage device storing such a program. The program includes code for implementing the system or method as claimed in any of the foregoing claims. Furthermore, the embodiment of the present invention can be electronically transmitted via any medium (such as a communication signal carried by a wired or wireless connection), and the embodiment appropriately includes the same content.

All the features disclosed in this specification (including any attached claims, abstracts and drawings) and/or all steps of any method or procedure disclosed in this way can be combined in any combination, except for such features and/ Or at least some of the steps are outside of mutually exclusive combinations.

Unless expressly stated otherwise, each feature disclosed in this specification (including any attached claims, abstracts and drawings) can be replaced by optional features serving the same, equivalent or similar purpose. Therefore, unless expressly stated otherwise, each feature disclosed is only an example of a generic series of equivalent or similar features. The invention is not limited to the details of any of the foregoing embodiments. The present invention extends to any novel feature or any novel combination of features disclosed in this specification (including any attached claims, abstracts and drawings), or extends to any method or procedure step disclosed in this way Any novel step or any novel combination of steps in the. The claim should not be construed as covering only the foregoing embodiments, but should also cover any embodiments falling within the scope of the claim.

:第一集合

:第二集合

:第三集合

:工作列表A:第一程序100: Distributed processing system 110: Network 120, 200: Distributed system controller 130, 135: Classical computing device 140, 300: Hybrid computing device 150: Classical processor 160: Interactive module 170: Quantum information processor 210 , 1120: processor 220, 220': memory 230, 230': permanent storage device 240, 240': input/output unit 250, 250': communication module 260, 260': power supply 270: port 280: vision Display 1100: computer readable media 1110: instruction RAM: random access memory ROM: read-only memory FPGA: field programmable gate array SSA: single-flow assignment CFA: control flow analysis CFG: control flow graph

: The first set

: The second set

: The third set

: Work list A : First program

The embodiments of the present invention will now be described by way of example only with reference to the drawings, in which: Figure 1 shows a distributed processing system including a quantum information processor; Figure 2 shows a block diagram of a computing device used as a distributed system controller; Figure 3 shows a block diagram of a hybrid computing device; Figure 4 shows a flowchart of a method for translating a classical quantum hybrid program; Figure 5 shows in more detail a flowchart of a method for translating a classical quantum hybrid program; Figure 6 shows a flowchart of a method for marking basic blocks for insertion; Figure 7 shows a flowchart of a method for marking a loop for deployment; and Figure 8 shows a flowchart of a method for identifying subroutines; Figure 9 shows a flowchart of a method of configuring a subroutine for use with target hardware; Figure 10 shows a flowchart of a method for isolating subroutines; and Figure 11 shows a block diagram of a machine-readable storage medium. Throughout the description and drawings, similar reference numbers refer to similar parts.

Claims (19)

A method for translating a classical quantum hybrid program to be executed by a distributed processing system. The distributed processing system includes one or more classical processors and a quantum information processor that can be interrogated via a classical analog interaction tool. The classical quantum The hybrid program includes functions to be executed by the quantum information processor, and the method includes: Parse the classical quantum hybrid program to generate an intermediate representation of the classical quantum hybrid program, the intermediate representation includes a series of basic blocks, and each basic block includes a sequence of instructions; The identification instruction sequence includes a basic block of one or more stream operation instructions, the one or more stream operation instructions are configured to control interaction with the quantum information processor; Analyze the identified basic blocks to identify one or more subprograms for implementation on the one or more classical processors and quantum information processors; Based on the description of a target hardware setting of the analog interactive tool, one or more stream operation instructions of the subprogram are replaced with the target hardware specific code used to control the interaction between the analog interactive tool and the quantum information processor to The hardware-specific intermediate representation of the classical quantum hybrid program is generated; and The hardware specific intermediate representation of the classical quantum hybrid program is converted into a translated classical quantum hybrid program. The method according to claim 1, further comprising, after identifying the basic block of the instruction sequence including one or more stream operation instructions: Mark the program call for insertion, where the program includes one or more basic blocks; and Insertion contains the basic blocks of the program call that are marked for insertion. The method according to claim 2, wherein the procedure call marked for insertion includes: Mark a program containing one or more basic blocks as belonging to a first set. For the one or more basic blocks, the instruction sequence includes one or more stream operation instructions; Mark such programs as belonging to a second set: any marked program that can reach the first set from these programs; Combining the first set and the second set to form a third set; For each program in this third set; Identify all calling programs that called the program; and If the calling program is in the third set, then the call is marked for insertion; If the calling program is in the second set and another program in the second set is called, the call is marked for insertion and the calling program is added to the third set. The method according to any one of the preceding claims, wherein analyzing the identified basic block to identify one or more subroutines includes: Convert the identified basic block into a static single assignment form, and additionally ensure that each flow operation instruction depends on at most one dominating flow operation instruction; The static single assignment form of the identified basic block is analyzed to identify one or more subprograms for implementation on the one or more classical processors and quantum information processors. The method according to any one of the preceding claims, wherein analyzing the identified basic block includes: Mark the loop used to expand within the identified basic block; and Expand the loop that is marked for expansion. The method according to claim 5, wherein the circle for expansion in the basic block identified by the mark includes: Locate a non-constant flow identifier within the recognized basic block; and If the non-constant flow identifier relies on a loop of induction variables, mark the loop for expansion. The method according to any one of the preceding claims, wherein the stream operation instruction includes one of the following: OPEN instruction used to start the stream; READ instruction used to read from the open stream; WRITE instruction for writing to an open stream; The CLOSE instruction used to deactivate an open stream. The method according to any one of the preceding claims, wherein ensuring that each flow operation instruction depends on at most one dominating flow operation instruction includes: inserting a reserved position flow function where the branch paths of the flow operation are merged. The method according to claim 4, wherein converting the identified basic block into a static single assignment form includes analyzing the control flow, dominance hierarchy, and control dependency of the classical quantum hybrid program. The method according to claim 4 or claim 9, wherein analyzing the basic block in the form of static single assignment includes performing one or more of data flow analysis or constant propagation. The method according to any one of the preceding claims, wherein replacing one or more stream operation instructions of the subprogram with a target hardware specific code for controlling the analog interactive tool includes: Identify a subroutine of the subroutine; For example, the flow operation command of the subprogram and the target hardware setting description transfer the subroutine to a hardware backend, so that the hardware backend can generate hardware setting data and commands, and define the hardware data flow; Based on the configuration data, commands, and hardware data flow, the commands are inserted into the static single assignment form of the classical quantum hybrid program to push data to/pull data from the hardware. The method according to claim 4 or claim 9 or claim 10, wherein a static single assignment form of the identified basic block is analyzed to identify the method used in the one or more classical processors and quantum information processors One or more subroutines implemented above include: Analyze the flow dependency of the static single-assignment form to construct a first-class dependency graph; Modify the connected subgraph of the flow dependency graph to a strongly connected subgraph; Construct a dependency graph based on the modified flow dependency graph and the control dependency and data dependency of the static single-assignment form of the classical quantum hybrid program; and Identify the strongly connected subgraph of the dependency graph as a subroutine. The method according to any one of the preceding claims, further comprising receiving the original code of the classical quantum hybrid program. The method according to any one of the preceding claims, wherein the one or more classic processors include a field programmable gate array. The method according to any one of the preceding claims, further comprising allocating at least a part of the translated classical quantum hybrid program to the one or more classical processors. A computer-readable storage medium has an instruction stored thereon, which, when executed by one or more processors, causes the one or more processors to perform the method according to any one of the preceding claims. A computer-readable storage medium on which a translated classical quantum hybrid program is stored, and the classical quantum hybrid program is translated according to any one of claim 1 to claim 15. A distributed system controller configured to translate a classical quantum hybrid program to be executed by a distributed processing system. The distributed processing system includes a distributed system controller, one or more classical processors, and a classical analogy. A quantum information processor interrogable by interactive tools, the classical quantum hybrid program includes functions to be executed by the quantum information processor, and the distributed system controller includes: One or more memories; and One or more processors, the one or more processors are configured to: Parse the classical quantum hybrid program to generate an intermediate representation of the classical quantum hybrid program, the intermediate representation includes a series of basic blocks, and each basic block includes a sequence of instructions; The identification instruction sequence includes a basic block of one or more stream operation instructions, the one or more stream operation instructions are configured to control interaction with the quantum information processor; Analyze the identified basic blocks to identify one or more subprograms for implementation on the one or more classical processors and quantum information processors; Based on the description of a target hardware setting of the analog interactive tool, one or more stream operation instructions of the subprogram are replaced with the target hardware specific code used to control the interaction between the analog interactive tool and the quantum information processor to The hardware-specific intermediate representation of the classical quantum hybrid program; and The hardware specific intermediate representation of the classical quantum hybrid program is converted into a translated classical quantum hybrid program. A distributed processing system, including: A quantum information processor; One or more classic processors; and A distributed system controller configured to: Parse the classical quantum hybrid program to generate an intermediate representation of the classical quantum hybrid program, the intermediate representation includes a series of basic blocks, and each basic block includes a sequence of instructions; The identification instruction sequence includes a basic block of one or more stream operation instructions, the one or more stream operation instructions are configured to control interaction with the quantum information processor; Analyze the identified basic blocks to identify one or more subprograms for implementation on the one or more classical processors and quantum information processors; Based on the description of a target hardware setting of the analog interactive tool, one or more stream operation instructions of the subprogram are replaced with the target hardware specific code used to control the interaction between the analog interactive tool and the quantum information processor to The hardware-specific intermediate representation of the classical quantum hybrid program; and The hardware specific intermediate representation of the classical quantum hybrid program is converted into a translated classical quantum hybrid program.

Images