Efficient scheduling of pauli-terms for quantum computing

Abstract

A method, apparatus, and computer product for scheduling Pauli-terms by selecting an order for the Pauli-terms, comprising: obtaining first and second ordered sets of Pauli-terms; obtaining first and second multitree data structures representing the first and second ordered sets, respectively; and determining whether or not the first and second ordered sets should be concatenated by: generating a third multitree data structure that represents all Pauli-terms of the first and second ordered sets; calculating a difference between a resource utilization score of the third multitree data structure and between resource utilization scores of the first and second multitree data structures; and based on the difference, determining whether or not the first and second ordered sets should be concatenated.

What is claimed is: 
     
         1 . A method for scheduling a plurality of Pauli-terms, said scheduling comprising selecting an order for the plurality of Pauli-terms, the method comprising:
 obtaining first and second ordered sets of one or more Pauli-terms of the plurality of Pauli-terms;   obtaining first and second multitree data structures for the first and second ordered sets, respectively, the first and second multitree data structures representing the first and second ordered sets, respectively, wherein a given multitree data structure of a set of Pauli-terms comprises:
 a set of root nodes representing the set of Pauli-terms, respectively; and 
 a plurality of leaf nodes representing a plurality of qubits associated with the set of Pauli-terms, wherein every leaf node that represents a qubit of a Pauli-term is a descendant of a root node that represents the Pauli-term, wherein every non-leaf node of the multitree data structure forms a connected tree that comprises all descendants of the non-leaf node; and 
   determining whether or not the first and second ordered sets should be concatenated by:
 generating a third multitree data structure that represents all Pauli-terms of the first and second ordered sets; 
 calculating a difference between a resource utilization score of the third multitree data structure and between resource utilization scores of the first and second multitree data structures, wherein a resource utilization score of a multitree data structure is determined based on a number of Controlled-X (CX) gates in the multitree data structure; and 
 based on the difference, determining whether or not the first and second ordered sets should be concatenated. 
   
     
     
         2 . The method of  claim 1 , wherein said generating the third multitree data structure is performed from scratch based on the first and second ordered sets. 
     
     
         3 . The method of  claim 1 , wherein said generating the third multitree data structure comprises utilizing the first multitree data structure as a basis and modifying the first multitree data structure according to the second ordered set. 
     
     
         4 . The method of  claim 3 , wherein the first multitree data structure is greater in size than the second multitree data structure. 
     
     
         5 . The method of  claim 1  further comprising calculating the difference by subtracting a sum of the resource utilization scores of the first and second multitree data structures from the resource utilization score of the third multitree data structure. 
     
     
         6 . The method of  claim 1 , wherein said determining whether or not the first and second ordered sets should be concatenated is performed based on whether or not the difference complies with a threshold. 
     
     
         7 . The method of  claim 1  further comprising:
 generating a plurality of multitree data structures for the plurality of Pauli-terms, respectively; 
 based on one or more properties of the plurality of multitree data structures, determining a plurality of priority scores for the plurality of multitree data structures, respectively; 
 selecting two candidate multitree data structures from the plurality of multitree data structures based on the plurality of priority scores; and 
 performing said obtaining the first and second ordered sets with the two candidate multitree data structures. 
 
     
     
         8 . The method of  claim 7 , wherein said selecting the two candidate multitree data structures comprises selecting matching multitree data structures that have a greatest number of overlapping active qubits as the first and second ordered sets. 
     
     
         9 . The method of  claim 7 , wherein a priority score of a multitree data structure is determined based on a number of child nodes of each non-leaf node in the multitree data structure. 
     
     
         10 . The method of  claim 9 , wherein the priority score is calculated as: Σ n∈N  2 (child (n)−1), wherein n is a non-leaf node selected from a set of non-leaf nodes, N, and wherein child (n) is the number of child nodes of the non-leaf node n. 
     
     
         11 . The method of  claim 7  further comprising:
 determining to concatenate the first and second ordered sets, thereby obtaining a concatenated ordered set; 
 modifying the plurality of multitree data structures to exclude the first and second multitree data structures and include the third multitree data structure, thereby obtaining a modified plurality of multitree data structures; and 
 performing said selecting the two candidate multitree data structures from the modified plurality of multitree data structures. 
 
     
     
         12 . The method of  claim 7  further comprising iteratively performing said determining whether or not the first and second ordered sets should be concatenated for one or more pairs of Pauli-terms represented by respective pairs of multitree data structures from the two candidate multitree data structures. 
     
     
         13 . The method of  claim 12 , wherein the one or more pairs are selected based on sizes of the respective pairs of multitree data structures. 
     
     
         14 . The method of  claim 1 , wherein the resource utilization score of a multitree data structure is determined based on an estimated depth of a quantum circuit that can be synthesized from the multitree data structure. 
     
     
         15 . An apparatus comprising a processor and coupled memory, said processor being adapted to schedule a plurality of Pauli-terms, said scheduling comprising selecting an order for the plurality of Pauli-terms, said processor is adapted to:
 obtain first and second ordered sets of one or more Pauli-terms of the plurality of Pauli-terms;   obtain first and second multitree data structures for the first and second ordered sets, respectively, the first and second multitree data structures representing the first and second ordered sets, respectively, wherein a given multitree data structure of a set of Pauli-terms comprises:
 a set of root nodes representing the set of Pauli-terms, respectively; and 
 a plurality of leaf nodes representing a plurality of qubits associated with the set of Pauli-terms, wherein every leaf node that represents a qubit of a Pauli-term is a descendant of a root node that represents the Pauli-term, wherein every non-leaf node of the multitree data structure forms a connected tree that comprises all descendants of the non-leaf node; and 
   determine whether or not the first and second ordered sets should be concatenated by:
 generating a third multitree data structure that represents all Pauli-terms of the first and second ordered sets; 
 calculating a difference between a resource utilization score of the third multitree data structure and between resource utilization scores of the first and second multitree data structures, wherein a resource utilization score of a multitree data structure is determined based on a number of Controlled-X (CX) gates in the multitree data structure; and 
 based on the difference, determining whether or not the first and second ordered sets should be concatenated. 
   
     
     
         16 . The apparatus of  claim 15 , wherein said generating the third multitree data structure is performed from scratch based on the first and second ordered sets. 
     
     
         17 . The apparatus of  claim 15 , wherein said generating the third multitree data structure comprises utilizing the first multitree data structure as a basis and modifying the first multitree data structure according to the second ordered set. 
     
     
         18 . The apparatus of  claim 15 , wherein the processor is further adapted to calculate the difference by subtracting a sum of the resource utilization scores of the first and second multitree data structures from the resource utilization score of the third multitree data structure. 
     
     
         19 . The apparatus of  claim 15 , wherein the processor is further adapted to:
 generate a plurality of multitree data structures for the plurality of Pauli-terms, respectively;   based on one or more properties of the plurality of multitree data structures, determine a plurality of priority scores for the plurality of multitree data structures, respectively;   select two candidate multitree data structures from the plurality of multitree data structures based on the plurality of priority scores; and   perform said obtaining the first and second ordered sets with the two candidate multitree data structures.   
     
     
         20 . A computer program product comprising a non-transitory computer readable medium retaining program instructions, the program instructions, when read by a processor, cause the processor to schedule a plurality of Pauli-terms, said scheduling comprising selecting an order for the plurality of Pauli-terms, the program instructions, when read by the processor, cause the processor to:
 obtain first and second ordered sets of one or more Pauli-terms of the plurality of Pauli-terms;   obtain first and second multitree data structures for the first and second ordered sets, respectively, the first and second multitree data structures representing the first and second ordered sets, respectively, wherein a given multitree data structure of a set of Pauli-terms comprises:
 a set of root nodes representing the set of Pauli-terms, respectively; and 
 a plurality of leaf nodes representing a plurality of qubits associated with the set of Pauli-terms, wherein every leaf node that represents a qubit of a Pauli-term is a descendant of a root node that represents the Pauli-term, wherein every non-leaf node of the multitree data structure forms a connected tree that comprises all descendants of the non-leaf node; and 
   determine whether or not the first and second ordered sets should be concatenated by:
 generating a third multitree data structure that represents all Pauli-terms of the first and second ordered sets; 
 calculating a difference between a resource utilization score of the third multitree data structure and between resource utilization scores of the first and second multitree data structures, wherein a resource utilization score of a multitree data structure is determined based on a number of Controlled-X (CX) gates in the multitree data structure; and 
 based on the difference, determining whether or not the first and second ordered sets should be concatenated.