Parser failed

[IsolatedMy]

Hi. I want to evaluate the compilation of Quartz. I generate the test_nam file and execute it.

$ ./test_nam ../circuit/nam_circs/adder_8.qasm

The adder_8.qasm is a program with 900 quantum gates. The test_nam program output the error as follows. I'd like to know what to do to correctly execute the compilation process. Thanks.

Gate rz not in current context (gate set).
Unsupported gate in current context: rz
Parser failed
EquivalenceSet fails to open ../Nam_6_3_complete_ECC_set.json
Failed to load equivalence file "../Nam_6_3_complete_ECC_set.json".
Number of xfers: 0
EquivalenceSet fails to open ../Nam_6_3_complete_ECC_set.json
Failed to load equivalence file "../Nam_6_3_complete_ECC_set.json".
greedy_optimize(): Number of xfers that reduce cost: 0
greedy_optimize(): cost optimized from 24 to 24
[adder_8.qasm] Best cost: 24.000000	candidate number: 0	after 0.000 seconds.
Optimization results of Quartz for adder_8.qasm on Nam's gate set. Gate count after optimization: 24, Circuit depth: 4, 0 seconds.

[xumingkuan]

Hi, sorry for the confusion. There are two issues here:

1. There are many versions of the circuits from Nam et al.'s paper. For this specific executable test_nam, please use circuits in the nam-benchmarks folder, for example, circuit/nam-benchmarks/adder_8.qasm.
2. Nam_6_3_complete_ECC_set.json is not included in the repo because it is too large. You can make and run gen_ecc_set to generate it, and make sure the path to the ECC Set file (../Nam_6_3_complete_ECC_set.json) is correct. I'm not sure how to make this issue easier for you, and please let me know if you have any suggestions.

You can also try running test_optimize from the root of the project. If running from other directories, you may want to change the path of the circuit in the code.

[IsolatedMy]

Thanks for your reply.

For this specific executable test_nam, please use circuits in the nam-benchmarks folder, for example, circuit/nam-benchmarks/adder_8.qasm.

If I want to optimize the circuits in the nam_circs folder, which version of executable should I use?

[xumingkuan]

If I want to optimize the circuits in the nam_circs folder, which version of executable should I use?

Please use test_optimize. I just updated this file so that you can run it from any directory, and you can also use command line arguments to optimize other circuits than the default barenco_tof_3. For now, the first argument (if exists) is the circuit directory to be optimized, and the second argument (if exists) is the circuit name to be printed on the screen.

[IsolatedMy]

I notice the number of generated transformation rules and ECCs are not aligned with the number shown in the paper.

Num_total_dags = 66, num_equivalence_classes = 23
*** Number of transformations of /home/d1/cmy/quartz/eccset/Nam_3_3 = 86
*** ch(/home/d1/cmy/quartz/eccset/Nam,q=3) = 27

I get 86 transformation rules for Nam_3_3 setting, but the paper says the number is 196. Is it because the data in the paper is outdated, or is there an issue with my configuration?

[xumingkuan]

I notice the number of generated transformation rules and ECCs are not aligned with the number shown in the paper.

Num_total_dags = 66, num_equivalence_classes = 23
*** Number of transformations of /home/d1/cmy/quartz/eccset/Nam_3_3 = 86
*** ch(/home/d1/cmy/quartz/eccset/Nam,q=3) = 27

I get 86 transformation rules for Nam_3_3 setting, but the paper says the number is 196. Is it because the data in the paper is outdated, or is there an issue with my configuration?

There are more prunings (in addition to the common subcircuit pruning in the paper) in Quartz now. The ECC set should still be complete but smaller (or the same size) for all configurations compared to the paper. See also https://github.com/quantum-compiler/quartz/blob/master/src/quartz/dataset/equivalence_set.h if you're interested in the prunings used in Quartz now.

[IsolatedMy]

When I generate transformation for Nam_3_6 setting, the program outputs log like the followings. I wonder if it means something is wrong.

Cannot find equivalence for dags (vector approach):
[[3, 6, ['85f8ae22e8ff'], [-0.2742579387317384, 0.10758912389291395]], [['h', ['Q1'], ['Q1']], ['rz', ['Q2'], ['Q2', 'P1']], ['cx', ['Q1', 'Q2'], ['Q1', 'Q2']], ['h', ['Q1'], ['Q1']], ['cx', ['Q2', 'Q1'], ['Q2', 'Q1']], ['h', ['Q2'], ['Q2']]]]
[[3, 5, ['85f8ae22e8ff'], [-0.2742579387317383, 0.10758912389291389]], [['x', ['Q1'], ['Q1']], ['rz', ['Q2'], ['Q2', 'P1']], ['cx', ['Q2', 'Q1'], ['Q2', 'Q1']], ['h', ['Q2'], ['Q2']], ['cx', ['Q2', 'Q1'], ['Q2', 'Q1']]]]

And I use the old version of Quartz to generate transformation with Nam_3_6, and optimize adder_8.qasm in Nam benchmark with it. The optimization result with 1-hour execution is 892. Is it reasonable, or does it mean something is wrong like that the preprocess is not turned on?

BTW, if I want to regenerate gate count results for Rigetti set in Table.4 of Quartz, what should I do? The only Rigetti-related benchmark in circuit/ folder is rigetti_rm_circs, but the gate count does not match the Orig. column in Table.4.

[xumingkuan]

When I generate transformation for Nam_3_6 setting, the program outputs log like the followings. I wonder if it means something is wrong.

Cannot find equivalence for dags (vector approach):
[[3, 6, ['85f8ae22e8ff'], [-0.2742579387317384, 0.10758912389291395]], [['h', ['Q1'], ['Q1']], ['rz', ['Q2'], ['Q2', 'P1']], ['cx', ['Q1', 'Q2'], ['Q1', 'Q2']], ['h', ['Q1'], ['Q1']], ['cx', ['Q2', 'Q1'], ['Q2', 'Q1']], ['h', ['Q2'], ['Q2']]]]
[[3, 5, ['85f8ae22e8ff'], [-0.2742579387317383, 0.10758912389291389]], [['x', ['Q1'], ['Q1']], ['rz', ['Q2'], ['Q2', 'P1']], ['cx', ['Q2', 'Q1'], ['Q2', 'Q1']], ['h', ['Q2'], ['Q2']], ['cx', ['Q2', 'Q1'], ['Q2', 'Q1']]]]

Could you please confirm your Quartz and Z3 versions? And are you using the repo https://github.com/quantum-compiler/quartz-artifact if you want to use the old version?

And I use the old version of Quartz to generate transformation with Nam_3_6, and optimize adder_8.qasm in Nam benchmark with it. The optimization result with 1-hour execution is 892. Is it reasonable, or does it mean something is wrong like that the preprocess is not turned on?

I think something is wrong. adder_8 has 900 gates, and preprocessing alone brings it down to 732. Note that test_optimize does not run preprocessing -- it's only for the "optimize" part. You should use test_nam to optimize if you want to include preprocessing.

BTW, if I want to regenerate gate count results for Rigetti set in Table.4 of Quartz, what should I do? The only Rigetti-related benchmark in circuit/ folder is rigetti_rm_circs, but the gate count does not match the Orig. column in Table.4.

Quartz focuses on the compilation/transpilation process of circuits. The "Orig." numbers are the gate count if we transpile the Toffoli gates (ccz) to the Rigetti gate set naively. In other words, the gate count equals the number of Toffoli gates times 13 plus the number of non-Toffoli gates. We use the circuits in the folder circuit/nam-benchmarks/.

[IsolatedMy]

Current Quartz version is a59332d and z3-solver version is 4.14.1.

z3                 0.2.0
z3-solver          4.14.1.0

[xumingkuan]

I encounter the same issue now:

[[3, 4, ['6160030d22bd'], [-0.12575252004527826, 0.17331461891876027]], [['h', ['Q0'], ['Q0']], ['cx', ['Q0', 'Q2'], ['Q0', 'Q2']], ['h', ['Q0'], ['Q0']], ['rz', ['Q0'], ['Q0', 'P3']]]]
[[3, 4, ['6160030d22bd'], [-0.12575252004527826, 0.17331461891876027]], [['h', ['Q2'], ['Q2']], ['cx', ['Q2', 'Q0'], ['Q2', 'Q0']], ['rz', ['Q0'], ['Q0', 'P3']], ['h', ['Q2'], ['Q2']]]]

I might be able to take a deeper look in one or two weeks. Meanwhile, you can try to use the old version of ECC sets in the artifact (https://zenodo.org/records/6508992) (with the artifact repo https://github.com/quantum-compiler/quartz-artifact). Or you can also use the ECC set generated now -- these Cannot find equivalence for dags (vector approach): messages only indicate that the generated ECC set might not be complete (and just missing at most one equivalence per message), and the generated ECC set is still sound (all equivalences are verified). I don't expect any degradation in optimization performance if you use the ECC sets generated even with a few of these messages.

[IsolatedMy]

Hi. I used ./test_nam to check the optimization of preprocessing.

 $ ./test_nam ../circuit/nam-benchmarks/adder_8.qasm --output result.qasm
Number of xfers: 293
greedy_optimize(): Number of xfers that reduce cost: 55
greedy_optimize(): cost optimized from 732 to 644
...

The original gate count of adder_8.qasm is 900. According to the output, there seems to two preprocessing procedure. The first one is performed in the graph.toffoli_flip_greedy function, while the second one is performed in the graph_before_search->optimize function.

What confused me is that the paper says the gate count after preprocessing is 732 instead of 644 or less. Is there something wrong in my understanding, or is the preprocessing procedure updated?

[xumingkuan]

Hi. I used ./test_nam to check the optimization of preprocessing.

$ ./test_nam ../circuit/nam-benchmarks/adder_8.qasm --output result.qasm
Number of xfers: 293
greedy_optimize(): Number of xfers that reduce cost: 55
greedy_optimize(): cost optimized from 732 to 644
...
The original gate count of adder_8.qasm is 900. According to the output, there seems to two preprocessing procedure. The first one is performed in the graph.toffoli_flip_greedy function, while the second one is performed in the graph_before_search->optimize function.

The preprocessing is just graph.toffoli_flip_greedy. graph_before_search->optimize is the main optimization function, using the beam search to optimize.

What confused me is that the paper says the gate count after preprocessing is 732 instead of 644 or less. Is there something wrong in my understanding, or is the preprocessing procedure updated?

The gate count after preprocessing is indeed 732, as shown in the line greedy_optimize(): cost optimized from 732 to 644. In the search, we first apply a greedy phase, which uses Quartz's transformation rules instead of (for example) manually written Toffoli decompositions. This message simply shows that the gate count after preprocessing is 732, and the gate count after the greedy phase is 644. After that, we must apply some cost-preserving transformations (instead of only cost-decreasing transformations) to continue optimizing the circuit.

[IsolatedMy]

Thanks for your reply. I don't quite understand this part.

This message simply shows that the gate count after preprocessing is 732, and the gate count after the greedy phase is 644. After that, we must apply some cost-preserving transformations (instead of only cost-decreasing transformations) to continue optimizing the circuit.

Since the final optimization result shown in Quartz paper is 724 but the one in Quarl paper is 624, does this mean that this greedy strategy is newly implemented? It seems the greedy part is not a search-based phase but still a rule-based phase. If it doesn't involve your future work, could you briefly explain the mechanism of greedy phase?

[xumingkuan]

Thanks for your reply. I don't quite understand this part.

This message simply shows that the gate count after preprocessing is 732, and the gate count after the greedy phase is 644. After that, we must apply some cost-preserving transformations (instead of only cost-decreasing transformations) to continue optimizing the circuit.

Since the final optimization result shown in Quartz paper is 724 but the one in Quarl paper is 624, does this mean that this greedy strategy is newly implemented? It seems the greedy part is not a search-based phase but still a rule-based phase. If it doesn't involve your future work, could you briefly explain the mechanism of greedy phase?

Oh right, it was relatively "newly" implemented if you compare the current repo with the Quartz paper. In Quartz's paper's search, we conduct a search and only accept the transformations that almost always either keep the gate count the same or reduce the gate count in the evaluation, while keeping other choices in the queue to search. This is an optimization that accepts all transformations that reduce the gate count, without keeping the option to not accept them, so as to not blow up the search queue size exponentially at the beginning. For example, if a circuit contains 1 qubit with 100 Hadamard gates, Quartz's paper would try to search for the cancellation of each adjacent pair of Hadamard gates, while this optimization will simply cancel all gates without searching.

[xumingkuan]

I encounter the same issue now:

[[3, 4, ['6160030d22bd'], [-0.12575252004527826, 0.17331461891876027]], [['h', ['Q0'], ['Q0']], ['cx', ['Q0', 'Q2'], ['Q0', 'Q2']], ['h', ['Q0'], ['Q0']], ['rz', ['Q0'], ['Q0', 'P3']]]]
[[3, 4, ['6160030d22bd'], [-0.12575252004527826, 0.17331461891876027]], [['h', ['Q2'], ['Q2']], ['cx', ['Q2', 'Q0'], ['Q2', 'Q0']], ['rz', ['Q0'], ['Q0', 'P3']], ['h', ['Q2'], ['Q2']]]]

I might be able to take a deeper look in one or two weeks. Meanwhile, you can try to use the old version of ECC sets in the artifact (https://zenodo.org/records/6508992) (with the artifact repo https://github.com/quantum-compiler/quartz-artifact). Or you can also use the ECC set generated now -- these Cannot find equivalence for dags (vector approach): messages only indicate that the generated ECC set might not be complete (and just missing at most one equivalence per message), and the generated ECC set is still sound (all equivalences are verified). I don't expect any degradation in optimization performance if you use the ECC sets generated even with a few of these messages.

For this, I made a PR #217 recently to use SymPy instead of Z3 to make the result more deterministic. Please let me know if any equivalences are still unverified after this PR.