quantum-compiler / quartz

The Quartz Quantum Compiler
Apache License 2.0
76 stars 19 forks source link

[Generator] Parameter-related pruning on ECC Set #161

Closed xumingkuan closed 7 months ago

xumingkuan commented 7 months ago

159 enables more systematic parameter-related pruning on the ECC Set.

This PR does the following two prunings:

  1. If an ECC does not use a prefix of the input symbolic parameters, e.g., uses P1 but not P0 (they are both input symbolic parameters), remove this ECC because the complete ECC Set should have an ECC that is replacing each occurrence of P1 with P0 in this ECC.
  2. If an ECC uses one input symbolic parameter only in one non-trivial expression, e.g., uses P1+P2 but neither P2 nor any other expression containing P2, remove this ECC because the complete ECC Set should have an ECC that is replacing each occurrence of P1+P2 with P2 in this ECC.

(These two prunings are implemented assuming there are no more than 63 input symbolic parameters, and they have the smallest indices in [0, 63) in the Context object.)

Also updates the document string for each ECC Set simplification/optimization.

Benchmark: gen_ecc_set on Nam gate set. Before: (3,3)-complete:

Before ECC simplification: num_total_dags = 4496, num_equivalence_classes = 4179, #transformations Nam_3_3 = 634
Nam_3_3 generated. Running Time (s): 3.943
Pruning Time (s): 0.009
Verification Time (s): 3.848
Num_total_dags = 94, num_equivalence_classes = 37
*** Number of transformations of Nam_3_3 = 114

(4,3)-complete (70.1KiB):

Before ECC simplification: num_total_dags = 38357, num_equivalence_classes = 36177, #transformations Nam_4_3 = 4360
Nam_4_3 generated. Running Time (s): 29.053
Pruning Time (s): 0.143
Verification Time (s): 27.874
Num_total_dags = 542, num_equivalence_classes = 250
*** Number of transformations of Nam_4_3 = 584

After (better than before #159 now): (3,3)-complete:

Before ECC simplification: num_total_dags = 4496, num_equivalence_classes = 4179, #transformations Nam_3_3 = 634
Nam_3_3 generated. Running Time (s): 3.992
Pruning Time (s): 0.008
Verification Time (s): 3.895
Num_total_dags = 66, num_equivalence_classes = 23
*** Number of transformations of Nam_3_3 = 86

(4,3)-complete (34.2KiB):

Before ECC simplification: num_total_dags = 38357, num_equivalence_classes = 36177, #transformations Nam_4_3 = 4360
Nam_4_3 generated. Running Time (s): 31.04
Pruning Time (s): 0.116
Verification Time (s): 29.865
Num_total_dags = 272, num_equivalence_classes = 117
*** Number of transformations of Nam_4_3 = 310