CN-122021960-A - General shuttle scheduling method and system

CN122021960ACN 122021960 ACN122021960 ACN 122021960ACN-122021960-A

Abstract

The invention relates to the technical field of quantum computing, and discloses a general shuttle scheduling method and system. The method comprises the steps of formalizing modeling of architecture constraints of quantum computing hardware, converting hardware physical limitations into a Boolean satisfiability constraint set through a Boolean satisfiability expression, extracting characteristics of input quantum circuits, constructing a directed acyclic graph model, extracting dependency relations among operations to form logic constraints, generating a shuttle scheduling scheme based on the Boolean satisfiability constraint set and the logic constraints, wherein the shuttle scheduling scheme comprises an accurate optimal scheduling mode and a high-efficiency approximate scheduling mode, establishing a standardized shuttle scheduling flow, being capable of rapidly adapting to various quantum computing hardware architectures, and achieving high-efficiency processing of large-scale quantum circuits while guaranteeing the optimality of the small-scale quantum circuits through binary search optimization and divide-and-conquer approximation strategies.

Inventors

ZHANG YU
Deng Haopi

Assignees

中国科学技术大学

Dates

Publication Date: 20260512
Application Date: 20260413

Claims (10)

1. A universal shuttle scheduling method, comprising: formalized modeling is carried out on the architecture constraint of the quantum computing hardware, and the physical limitation of the hardware is converted into a Boolean satisfaction constraint set through a Boolean satisfaction expression; Extracting features of an input quantum circuit, constructing a directed acyclic graph model, extracting dependency relations among operations, and forming logic constraint; The method comprises the steps of generating a shuttle scheduling scheme based on the Boolean satisfaction constraint set and logic constraint, wherein the shuttle scheduling scheme comprises an accurate optimal scheduling mode and a high-efficiency approximate scheduling mode, the accurate optimal scheduling mode adopts a binary search strategy to iteratively solve the minimum time step number until a solution can be met, the high-efficiency approximate scheduling mode adopts a divide-and-conquer strategy to divide a quantum circuit into subunits, the subunits are dynamically spliced into a global scheduling sequence after being solved respectively, and redundant segment elimination optimization is carried out on the spliced global scheduling sequence.
2. The universal shuttle scheduling method according to claim 1, wherein the converting the hardware physical constraint into the boolean satisfiability constraint set by boolean satisfiability expression specifically comprises: position presence and uniqueness constraints of each qubit in a quantum circuit At any time step Must occupy exactly one physical location; position capacity mutual exclusion constraint, each physical position At most one qubit can be accommodated at the same time step, i.e. for any two different qubits And Does not allow to occupy the same physical location at the same time; More recently shuttle constraints, if qubits At a time step Located in a physical position Then qubit At a time step Is only a set of physical locations For boundary physical locations, out-of-range options may be omitted; Non-traversable constraints qubits And Cannot skip each other.
3. The universal shuttle scheduling method according to claim 1, wherein the feature extraction is performed on the input quantum circuit, a directed acyclic graph model is constructed, dependency relationships among operations are extracted, and logic constraints are formed, specifically including: Each node in the directed acyclic graph model uniquely corresponds to one quantum operation in the quantum circuit, a Boolean variable is defined for each node and used for representing the completion state of the corresponding quantum operation, each side in the directed acyclic graph model reflects the quantum bit dependency and the control dependency among the quantum operations, and the directed acyclic graph model needs to meet the topological order binding constraint that if one quantum operation is marked as completed, all the front quantum operations of the quantum operation must be in the completion state.
4. A universal shuttle scheduling method according to claim 3 wherein said quantum operations comprise single bit gate operations, double bit gate operations and measurement operations; When two gate operations share at least one quantum bit, a predecessor-successor relationship must be established successively according to the time sequence of the two gate operations in the quantum circuit; Control dependence-for controlled quantum gate operation, the operation on the control bit must take precedence over the target bit operation and be connected by a directed edge.
5. The universal shuttle scheduling method according to claim 1, wherein the binary search strategy adopted by the precise optimal scheduling mode specifically comprises the steps of presetting an upper bound and a lower bound of time steps, taking an intermediate value to solve the Boolean satisfiability, updating the upper bound if the intermediate value can be met, otherwise updating the lower bound, and iterating until the upper bound and the lower bound converge to obtain a minimum time step.
6. The general purpose shuttle scheduling method according to claim 5, wherein the preset time steps are upper and lower bounds, the intermediate value is taken to perform boolean satisfiability solution, if the intermediate value is satisfied, the upper bound is updated, otherwise, the lower bound is updated, and the iteration is performed until the upper and lower bounds converge to obtain a minimum time step, and the method specifically comprises: the binary search strategy is based on monotonicity of the scheduling solution space for less than a minimum number of time steps The method comprises the steps of (1) calculating an intermediate value in each iteration by maintaining left and right boundaries of a search interval to solve, updating an upper boundary and recording a current solution if the result is satisfied, updating a lower boundary if the result is unsatisfiable, introducing an auxiliary boundary variable to perform pruning optimization, and terminating the search when the search interval is detected to be adjacent.
7. The general shuttle scheduling method according to claim 1, wherein the efficient approximate scheduling mode adopts a divide-and-conquer strategy to divide the quantum circuit into sub-units, and the sub-units are dynamically spliced into a global scheduling sequence after being solved respectively, and the method specifically comprises the following steps: Dividing a quantum circuit into a plurality of subunits according to the topological structure of the directed acyclic graph, maintaining the original topological order among the subunits and completely preserving the dependency relationship among quantum operations in the subunits, adopting a self-adaptive time window mechanism to estimate preset initial time constraint based on hardware characteristics when each subunit is independently solved, dynamically expanding the time window by using an elastic coefficient and re-solving if the solution is not available under the current constraint, and finally splicing the local scheduling sequences of the subunits into a global scheduling sequence.
8. The universal shuttle scheduling method according to claim 1, wherein the performing redundant segment elimination optimization on the spliced global scheduling sequence specifically comprises: the method comprises the steps of dividing a global scheduling sequence into non-operation intervals according to quantum gate operation execution time points, mapping quantum bit layouts in each non-operation interval into layout codes in an integer form to obtain an integer sequence, and eliminating redundant subsequences in the integer sequence through a dynamic programming algorithm, wherein the redundant subsequences are defined as continuous time steps with identical head-to-tail layout codes and no quantum gate operation in the middle.
9. The universal shuttle scheduling method according to claim 8, wherein the eliminating redundant subsequences in the integer sequence by the dynamic programming algorithm specifically comprises: Constructing a state array result, and the ith element of result Representing the shortest length of a sub-sequence consisting of layout codes of the first i time steps of the integer sequence after all redundancies are eliminated; Traversing each layout code of the integer sequence in order, for the (i+1) th layout code : If it is Not before, then ; If it is Before it appears, then for all the satisfaction And is also provided with Calculating candidate result k, and taking the minimum value of all candidate values to be Is set as And the smaller of the minima; And simultaneously maintaining an auxiliary record table, and storing the minimum result k corresponding to each layout code currently in real time.
10. A computer system comprising a memory and a processor, the memory storing a computer program, characterized in that the processor implements the steps of the method of any one of claims 1 to 9 when the computer program is executed.

Description

General shuttle scheduling method and system Technical Field The invention relates to the technical field of quantum computing, in particular to a general shuttle scheduling method and system. Background Quantum computing is expected to achieve advantages over classical computing over specific problems, where physical platforms such as ion traps and neutral atoms are of great interest due to their advantages of high fidelity gate operation and long coherence time. In these architectures (e.g., quantum charge coupled device QCCD) that implement scalability based on qubit shuttling (Shuttling), the qubits need to be moved between different physical regions to complete interactions, and the efficiency of the shuttling scheme directly determines the execution time and fidelity of the quantum wires. The existing shuttle scheduling technology is mainly divided into two directions. Firstly, a method based on accurate solution is used for searching a global optimal scheduling sequence through a Boolean Satisfiability (SAT) solver or integer programming, so that the theoretical minimum time step number can be found under given constraint. However, the method faces serious scalability problems with the increase of the number of qubits and the depth of a line, the solving time increases exponentially, and the method is extremely easy to fail overtime in practical application. Secondly, a method based on heuristic search or rules can be used for rapidly generating a feasible scheduling scheme through greedy strategy or staged planning, so that a larger-scale line can be processed. However, due to lack of global optimality guarantee, such methods tend to generate a large number of redundant move operations, resulting in reduced scheduling efficiency and extended execution time. More importantly, most of the prior art designs are customized for specific hardware architecture (such as one-dimensional linear ion trap or specific topology), and lack cross-platform versatility. When the hardware layout or physical constraint changes, the scheduling algorithm needs to be redesigned or greatly adjusted, and is difficult to adapt to the development requirements of diversified quantum computing chips. In view of the foregoing, there is a need for a shuttle scheduling framework that can compromise versatility, optimality, and scalability to support efficient scheduling of different quantum computing hardware platforms. Disclosure of Invention In order to solve the technical problems, the invention provides a general shuttle scheduling method and a system. The method and the system have the advantages that an algorithm and a framework are decoupled through Boolean Satisfiability (SAT) modeling, a set of standardized shuttle scheduling flow is established, multiple quantum computing hardware frameworks can be quickly adapted, high-efficiency processing of a large-scale quantum circuit is realized while the optimality of the small-scale quantum circuit is ensured through a binary search optimization and divide-and-conquer approximation strategy, and the decoherence risk of quantum bits is effectively reduced through a dynamic programming algorithm in a linear time aiming at the problem that invalid movement is easy to generate in the approximation scheme. In order to solve the technical problems, the invention adopts the following technical scheme: In a first aspect, the present invention provides a general shuttle scheduling method, including: formalized modeling is carried out on the architecture constraint of the quantum computing hardware, and the physical limitation of the hardware is converted into a Boolean satisfaction constraint set through a Boolean satisfaction expression; Extracting features of an input quantum circuit, constructing a directed acyclic graph model, extracting dependency relations among operations, and forming logic constraint; The method comprises the steps of generating a shuttle scheduling scheme based on the Boolean satisfaction constraint set and logic constraint, wherein the shuttle scheduling scheme comprises an accurate optimal scheduling mode and a high-efficiency approximate scheduling mode, the accurate optimal scheduling mode adopts a binary search strategy to iteratively solve the minimum time step number until a solution can be met, the high-efficiency approximate scheduling mode adopts a divide-and-conquer strategy to divide a quantum circuit into subunits, the subunits are dynamically spliced into a global scheduling sequence after being solved respectively, and redundant segment elimination optimization is carried out on the spliced global scheduling sequence. In one embodiment, the converting the hardware physical constraint into the boolean satisfiability constraint set by the boolean satisfiability expression specifically includes: position presence and uniqueness constraints of each qubit in a quantum circuit At any time stepMust occupy exactly one physical location; position capacity