[bug] mod5_4 get optimized to 5 gates if preprocessed separately

[xumingkuan]

@typerSniper found a bug: When running test_nam using a (4,3)-complete ECC set on the circuit mod5_4, we should (and we do) observe a final gate count of > 20. However, we get a result of only 5 gates if we do the preprocessing step separately: (steps to reproduce):

• Generate Nam_4_3_complete_ECC_set.json.
• Uncomment the line graph_before_search->to_qasm(input_fn + ".toffoli_flip", false, false); in test_nam.cpp, and run it on mod5_4.qasm to get mod5_4.qasm.toffoli_flip.
• Run test_nam.cpp on mod5_4.qasm.toffoli_flip with Nam_4_3_complete_ECC_set.json. You should observe the best cost going to 5 within 10 seconds.

If I print out the Graph object's circuit content before optimization after preprocessing, i.e., graph_before_search->to_qasm(true); immediately after the line graph_before_search->to_qasm(input_fn + ".toffoli_flip", false, false);, I get the same result for both mod5_4.qasm and mod5_4.qasm.toffoli_flip, and the result is exactly the same as the content of mod5_4.qasm.toffoli_flip (below). So I think the bug is not in the parser. I think it might be some information stored in the Context object that should not be there. @zikun-li Could you please take a look?

OPENQASM 2.0;
include "qelib1.inc";
qreg q[5];
x q[4];
h q[4];
cx q[3],q[4];
cx q[0],q[4];
rz(pi*0.250000) q[4];
cx q[3],q[4];
rz(pi*-0.250000) q[4];
cx q[0],q[4];
cx q[0],q[3];
rz(pi*-0.250000) q[3];
cx q[0],q[3];
cx q[3],q[4];
cx q[2],q[4];
rz(pi*-0.250000) q[4];
cx q[3],q[4];
rz(pi*0.250000) q[4];
cx q[2],q[4];
h q[4];
cx q[2],q[3];
rz(pi*0.250000) q[3];
cx q[2],q[3];
cx q[3],q[4];
h q[4];
cx q[2],q[4];
rz(pi*-0.250000) q[4];
cx q[1],q[4];
rz(pi*0.250000) q[4];
cx q[2],q[4];
rz(pi*-0.250000) q[4];
cx q[1],q[4];
cx q[1],q[2];
rz(pi*0.250000) q[4];
rz(pi*-0.250000) q[2];
h q[4];
cx q[1],q[2];
cx q[2],q[4];
h q[4];
cx q[1],q[4];
rz(pi*0.250000) q[4];
cx q[0],q[4];
rz(pi*-0.250000) q[4];
cx q[1],q[4];
rz(pi*0.250000) q[4];
cx q[0],q[4];
cx q[0],q[1];
rz(pi*-0.250000) q[4];
rz(pi*0.250000) q[1];
h q[4];
cx q[0],q[1];
cx q[1],q[4];
cx q[0],q[4];

[zikun-li]

I tried to reproduce this bug but failed, here's what I've done:

1. Generate Nam_4_3_complete_ECC_set.json.
2. Use test_nam.cpp to generate a .toffoli_flip file of the circuit mod5_4.
3. Then, to run test_nam.cpp on mod5_4.qasm.toffoli_flip, I have to comment out many lines. Here's the test_nam.cpp I used to run mod5_4.qasm.toffoli_flip.

   
   #include "quartz/parser/qasm_parser.h"
   #include "quartz/tasograph/substitution.h"
   #include "quartz/tasograph/tasograph.h"

using namespace quartz;

void parse_args(char **argv, int argc, bool &simulated_annealing, bool &early_stop, bool &disable_search, std::string &input_filename, std::string &output_filename, std::string &eqset_filename) { assert(argv[1] != nullptr); input_filename = std::string(argv[1]); early_stop = true; for (int i = 2; i < argc; i++) { if (!std::strcmp(argv[i], "--output")) { output_filename = std::string(argv[++i]); continue; } if (!std::strcmp(argv[i], "--eqset")) { eqset_filename = std::string(argv[++i]); continue; } if (!std::strcmp(argv[i], "--disable_search")) { disable_search = true; continue; } } }

int main(int argc, char **argv) { std::string input_fn, output_fn; std::string eqset_fn = "../Nam_4_3_complete_ECC_set.json"; bool simulated_annealing = false; bool early_stop = false; bool disable_search = false; parse_args(argv, argc, simulated_annealing, early_stop, disable_search, input_fn, output_fn, eqset_fn); auto fn = input_fn.substr(input_fn.rfind('/') + 1);

// Construct contexts Context src_ctx({GateType::h, GateType::ccz, GateType::x, GateType::cx, GateType::input_qubit, GateType::input_param}); Context dst_ctx({GateType::h, GateType::x, GateType::rz, GateType::add, GateType::cx, GateType::input_qubit, GateType::input_param}); // auto union_ctx = union_contexts(&src_ctx, &dst_ctx);

// auto xfer_pair = GraphXfer::ccz_cx_rz_xfer(&union_ctx); // // Load qasm file // QASMParser qasm_parser(&src_ctx); // CircuitSeq *dag = nullptr; // if (!qasm_parser.load_qasm(input_fn, dag)) { // std::cout << "Parser failed" << std::endl; // } // Graph graph(&src_ctx, dag);

auto start = std::chrono::steady_clock::now(); // // Greedy toffoli flip // auto graph_before_search = graph.toffoli_flip_greedy( // GateType::rz, xfer_pair.first, xfer_pair.second); // graph_before_search->to_qasm(input_fn + ".toffoli_flip", false, false);

auto end = std::chrono::steady_clock::now(); // if (disable_search) { // std::cout << "Optimization results of Quartz for " << fn // << " on Nam's gate set." // << " Gate count after optimization: " // << graph_before_search->gate_count() << ", " // << "Circuit depth: " << graph_before_search->circuit_depth() // << ", " // << // (double)std::chrono::duration_cast( // end - start) // .count() / // 1000.0 // << " seconds." << std::endl;

// return 0; // } auto graph_before_search = Graph::from_qasm_file(&dst_ctx, input_fn);

// Optimization auto graph_after_search = graph_before_search->optimize(&dst_ctx, eqset_fn, fn, /print_message=/ true); end = std::chrono::steady_clock::now(); std::cout << "Optimization results of Quartz for " << fn << " on Nam's gate set." << " Gate count after optimization: " << graph_after_search->gate_count() << ", " << "Circuit depth: " << graph_after_search->circuit_depth() << ", " << (double)std::chrono::duration_cast( end - start) .count() / 1000.0 << " seconds." << std::endl; graph_after_search->to_qasm(output_fn, false, false); }

And with these steps, I didn't observe the bug. 

[typerSniper]

Hey, I think you are probably running test_nam on the wrong file after preprocessing: mod5_4.qasm.toffoli_flip has rz gates and this test_nam file does not have rz in the source context. So it should give a parsing error.

[zikun-li]

In my above code, the input_fn is mod5_4.qasm.toffoli_filp, and I load it with the line auto graph_before_search = Graph::from_qasm_file(&dst_ctx, input_fn);. There won't be a parser error because I was using dst_ctx which contains rz.

[typerSniper]

oh good point. Can you try expanding the src_ctx with the rz gate, and then loading the circuit with src_ctx? It shouldn't make a difference, but maybe its a part of the bug.

[zikun-li]

I add rz and add to src_ctx and load graph_before_search with src_ctx and optimize it in src_ctx, and I still cannot reproduce. The code I'm using is here:

#include "quartz/parser/qasm_parser.h"
#include "quartz/tasograph/substitution.h"
#include "quartz/tasograph/tasograph.h"

using namespace quartz;

void parse_args(char **argv, int argc, bool &simulated_annealing,
                bool &early_stop, bool &disable_search,
                std::string &input_filename, std::string &output_filename,
                std::string &eqset_filename) {
  assert(argv[1] != nullptr);
  input_filename = std::string(argv[1]);
  early_stop = true;
  for (int i = 2; i < argc; i++) {
    if (!std::strcmp(argv[i], "--output")) {
      output_filename = std::string(argv[++i]);
      continue;
    }
    if (!std::strcmp(argv[i], "--eqset")) {
      eqset_filename = std::string(argv[++i]);
      continue;
    }
    if (!std::strcmp(argv[i], "--disable_search")) {
      disable_search = true;
      continue;
    }
  }
}

int main(int argc, char **argv) {
  std::string input_fn, output_fn;
  std::string eqset_fn = "../Nam_4_3_complete_ECC_set.json";
  bool simulated_annealing = false;
  bool early_stop = false;
  bool disable_search = false;
  parse_args(argv, argc, simulated_annealing, early_stop, disable_search,
             input_fn, output_fn, eqset_fn);
  auto fn = input_fn.substr(input_fn.rfind('/') + 1);

  // Construct contexts
  Context src_ctx({GateType::h, GateType::ccz, GateType::x, GateType::cx,
                   GateType::input_qubit, GateType::input_param, GateType::rz,
                   GateType::add});
  Context dst_ctx({GateType::h, GateType::x, GateType::rz, GateType::add,
                   GateType::cx, GateType::input_qubit, GateType::input_param});
  //   auto union_ctx = union_contexts(&src_ctx, &dst_ctx);

  //   auto xfer_pair = GraphXfer::ccz_cx_rz_xfer(&union_ctx);
  //   // Load qasm file
  //   QASMParser qasm_parser(&src_ctx);
  //   CircuitSeq *dag = nullptr;
  //   if (!qasm_parser.load_qasm(input_fn, dag)) {
  //     std::cout << "Parser failed" << std::endl;
  //   }
  //   Graph graph(&src_ctx, dag);

  auto start = std::chrono::steady_clock::now();
  //   // Greedy toffoli flip
  //   auto graph_before_search = graph.toffoli_flip_greedy(
  //       GateType::rz, xfer_pair.first, xfer_pair.second);
  //   graph_before_search->to_qasm(input_fn + ".toffoli_flip", false, false);

  auto end = std::chrono::steady_clock::now();
  //   if (disable_search) {
  //     std::cout << "Optimization results of Quartz for " << fn
  //               << " on Nam's gate set."
  //               << " Gate count after optimization: "
  //               << graph_before_search->gate_count() << ", "
  //               << "Circuit depth: " << graph_before_search->circuit_depth()
  //               << ", "
  //               <<
  //               (double)std::chrono::duration_cast<std::chrono::milliseconds>(
  //                      end - start)
  //                          .count() /
  //                      1000.0
  //               << " seconds." << std::endl;

  //     return 0;
  //   }
  auto graph_before_search = Graph::from_qasm_file(&src_ctx, input_fn);

  // Optimization
  auto graph_after_search =
      graph_before_search->optimize(&src_ctx, eqset_fn, fn, /*print_message=*/
                                    true);
  end = std::chrono::steady_clock::now();
  std::cout << "Optimization results of Quartz for " << fn
            << " on Nam's gate set."
            << " Gate count after optimization: "
            << graph_after_search->gate_count() << ", "
            << "Circuit depth: " << graph_after_search->circuit_depth() << ", "
            << (double)std::chrono::duration_cast<std::chrono::milliseconds>(
                   end - start)
                       .count() /
                   1000.0
            << " seconds." << std::endl;
  graph_after_search->to_qasm(output_fn, false, false);
}

[xumingkuan]

I can reproduce using the following code:

#include "quartz/parser/qasm_parser.h"
#include "quartz/tasograph/substitution.h"
#include "quartz/tasograph/tasograph.h"

using namespace quartz;

void parse_args(char **argv, int argc, bool &simulated_annealing,
                bool &early_stop, bool &disable_search,
                std::string &input_filename, std::string &output_filename,
                std::string &eqset_filename) {
  assert(argv[1] != nullptr);
  input_filename = std::string(argv[1]);
  early_stop = true;
  for (int i = 2; i < argc; i++) {
    if (!std::strcmp(argv[i], "--output")) {
      output_filename = std::string(argv[++i]);
      continue;
    }
    if (!std::strcmp(argv[i], "--eqset")) {
      eqset_filename = std::string(argv[++i]);
      continue;
    }
    if (!std::strcmp(argv[i], "--disable_search")) {
      disable_search = true;
      continue;
    }
  }
}

int main(int argc, char **argv) {
  std::string input_fn, output_fn;
  std::string eqset_fn = "Nam_4_3_complete_ECC_set.json";
  bool simulated_annealing = false;
  bool early_stop = false;
  bool disable_search = false;
  parse_args(argv, argc, simulated_annealing, early_stop, disable_search,
             input_fn, output_fn, eqset_fn);
  auto fn = input_fn.substr(input_fn.rfind('/') + 1);

  // Construct contexts
  Context src_ctx({GateType::h, GateType::ccz, GateType::x, GateType::cx,
                   GateType::input_qubit, GateType::input_param, GateType::rz,
                   GateType::add});
  Context dst_ctx({GateType::h, GateType::x, GateType::rz, GateType::add,
                   GateType::cx, GateType::input_qubit, GateType::input_param});
  auto union_ctx = union_contexts(&src_ctx, &dst_ctx);

  auto xfer_pair = GraphXfer::ccz_cx_rz_xfer(&union_ctx);
  // Load qasm file
  QASMParser qasm_parser(&src_ctx);
  CircuitSeq *dag = nullptr;
  if (!qasm_parser.load_qasm(input_fn, dag)) {
    std::cout << "Parser failed" << std::endl;
  }
  Graph graph(&src_ctx, dag);

  auto start = std::chrono::steady_clock::now();
  // Greedy toffoli flip
  auto graph_before_search = &graph;
//  auto graph_before_search = graph.toffoli_flip_greedy(
//      GateType::rz, xfer_pair.first, xfer_pair.second);
  //   graph_before_search->to_qasm(input_fn + ".toffoli_flip", false, false);

  auto end = std::chrono::steady_clock::now();
  // Optimization
  auto graph_after_search =
      graph_before_search->optimize(&src_ctx, eqset_fn, fn, /*print_message=*/
                                    true);
  end = std::chrono::steady_clock::now();
  std::cout << "Optimization results of Quartz for " << fn
            << " on Nam's gate set."
            << " Gate count after optimization: "
            << graph_after_search->gate_count() << ", "
            << "Circuit depth: " << graph_after_search->circuit_depth() << ", "
            << (double)std::chrono::duration_cast<std::chrono::milliseconds>(
                   end - start)
                       .count() /
                   1000.0
            << " seconds." << std::endl;
  graph_after_search->to_qasm(output_fn, false, false);
}

[xumingkuan]

I add rz and add to src_ctx and load graph_before_search with src_ctx and optimize it in src_ctx, and I still cannot reproduce. The code I'm using is here:

#include "quartz/parser/qasm_parser.h"
#include "quartz/tasograph/substitution.h"
#include "quartz/tasograph/tasograph.h"

using namespace quartz;

void parse_args(char **argv, int argc, bool &simulated_annealing,
                bool &early_stop, bool &disable_search,
                std::string &input_filename, std::string &output_filename,
                std::string &eqset_filename) {
  assert(argv[1] != nullptr);
  input_filename = std::string(argv[1]);
  early_stop = true;
  for (int i = 2; i < argc; i++) {
    if (!std::strcmp(argv[i], "--output")) {
      output_filename = std::string(argv[++i]);
      continue;
    }
    if (!std::strcmp(argv[i], "--eqset")) {
      eqset_filename = std::string(argv[++i]);
      continue;
    }
    if (!std::strcmp(argv[i], "--disable_search")) {
      disable_search = true;
      continue;
    }
  }
}

int main(int argc, char **argv) {
  std::string input_fn, output_fn;
  std::string eqset_fn = "../Nam_4_3_complete_ECC_set.json";
  bool simulated_annealing = false;
  bool early_stop = false;
  bool disable_search = false;
  parse_args(argv, argc, simulated_annealing, early_stop, disable_search,
             input_fn, output_fn, eqset_fn);
  auto fn = input_fn.substr(input_fn.rfind('/') + 1);

  // Construct contexts
  Context src_ctx({GateType::h, GateType::ccz, GateType::x, GateType::cx,
                   GateType::input_qubit, GateType::input_param, GateType::rz,
                   GateType::add});
  Context dst_ctx({GateType::h, GateType::x, GateType::rz, GateType::add,
                   GateType::cx, GateType::input_qubit, GateType::input_param});
  //   auto union_ctx = union_contexts(&src_ctx, &dst_ctx);

  //   auto xfer_pair = GraphXfer::ccz_cx_rz_xfer(&union_ctx);
  //   // Load qasm file
  //   QASMParser qasm_parser(&src_ctx);
  //   CircuitSeq *dag = nullptr;
  //   if (!qasm_parser.load_qasm(input_fn, dag)) {
  //     std::cout << "Parser failed" << std::endl;
  //   }
  //   Graph graph(&src_ctx, dag);

  auto start = std::chrono::steady_clock::now();
  //   // Greedy toffoli flip
  //   auto graph_before_search = graph.toffoli_flip_greedy(
  //       GateType::rz, xfer_pair.first, xfer_pair.second);
  //   graph_before_search->to_qasm(input_fn + ".toffoli_flip", false, false);

  auto end = std::chrono::steady_clock::now();
  //   if (disable_search) {
  //     std::cout << "Optimization results of Quartz for " << fn
  //               << " on Nam's gate set."
  //               << " Gate count after optimization: "
  //               << graph_before_search->gate_count() << ", "
  //               << "Circuit depth: " << graph_before_search->circuit_depth()
  //               << ", "
  //               <<
  //               (double)std::chrono::duration_cast<std::chrono::milliseconds>(
  //                      end - start)
  //                          .count() /
  //                      1000.0
  //               << " seconds." << std::endl;

  //     return 0;
  //   }
  auto graph_before_search = Graph::from_qasm_file(&src_ctx, input_fn);

  // Optimization
  auto graph_after_search =
      graph_before_search->optimize(&src_ctx, eqset_fn, fn, /*print_message=*/
                                    true);
  end = std::chrono::steady_clock::now();
  std::cout << "Optimization results of Quartz for " << fn
            << " on Nam's gate set."
            << " Gate count after optimization: "
            << graph_after_search->gate_count() << ", "
            << "Circuit depth: " << graph_after_search->circuit_depth() << ", "
            << (double)std::chrono::duration_cast<std::chrono::milliseconds>(
                   end - start)
                       .count() /
                   1000.0
            << " seconds." << std::endl;
  graph_after_search->to_qasm(output_fn, false, false);
}

I can reproduce it by replacing

  auto graph_before_search = Graph::from_qasm_file(&src_ctx, input_fn);

with

  auto seq = CircuitSeq::from_qasm_file(&src_ctx, input_fn);
  Graph graph(&src_ctx, seq.get());
  auto graph_before_search = &graph;

This suggests a bug when using CircuitSeq::from_qasm_file and Graph::Graph together?

[zikun-li]

I see. I reproduced successfully with @xumingkuan's code. But interestingly, when I switch to the RL branch, the bug disappears.

[xumingkuan]

I found one difference: the buggy one has rz(pi*-0.250000), while auto graph_before_search = Graph::from_qasm_file(&src_ctx, input_fn); gets rz(pi*1.750000). Are negative parameters not properly handled somewhere?

[zikun-li]

I see. Currently, in qasm_parser.h, we don't normalize the parameters to [0, 2*pi), but in Graph::_from_qasm_stream we do the normalization. However, I think this bug only leads to false negative in the pattern matching, but it seems that this mod5_4 issue here is due to false positive. And even though I add normalization to qasm_parser.h, the mod5_4 issue still exists.

[zikun-li]

I think this could related to some bug fix on the RL branch, maybe we should first merge #120, and see if this issue still exists.

[xumingkuan]

Sounds good. I've just merged it.

[zikun-li]

Okay, seems the issue still exists :(. I'll try to fix it tomorrow.

[zikun-li]

I know where the issue is. It seems that for input parameters to different gates with the same value, CircuitSeq only use a single CircuitWire to store it. However, in Graph, we each input parameter is stored in a Op no matter its value. So we cannot add parameters as #116.

[zikun-li]

This issue is fixed by #123.