Optimization by self-annihilating sequences

[DevelopDaily]

I use two test cases to illustrate an issue.

Case 1 - cx gates

OPENQASM 2.0;
include "qelib1.inc";

qreg q[2];
h q;

cx q[0], q[1];
cx q[0], q[1];
cx q[0], q[1];
cx q[0], q[1];

After staq with optimization:

OPENQASM 2.0;
include "qelib1.inc";

qreg q[2];
h q[0];
h q[1];

The cx gates have been cancelled nicely.

Case 2 - ccx gates

OPENQASM 2.0;
include "qelib1.inc";

qreg q[3];
h q;

ccx q[0], q[1], q[2];
ccx q[0], q[1], q[2];
ccx q[0], q[1], q[2];
ccx q[0], q[1], q[2];

After staqwith optimization:

OPENQASM 2.0;
include "qelib1.inc";

qreg q[3];
h q[0];
h q[1];
z q[2];
z q[1];
cx q[2],q[1];
rz(((pi*3)/2)+((pi*3)/2)) q[1];
s q[0];
cx q[2],q[0];
rz(((pi*3)/2)+((pi*3)/2)) q[0];
cx q[1],q[0];
sdg q[0];
cx q[2],q[0];
z q[0];
cx q[2],q[1];
cx q[2],q[0];
cx q[1],q[0];
h q[2];
s q[0];
cx q[1],q[0];
sdg q[0];
cx q[1],q[0];

The ccx gates should also cancel each other out, shouldn't they?

I read an old article, which may not be directly related to what the staqwants to achieve. Nevertheless, the authors introduced an interesting idea of removing self-annihilating sequences. I am wondering if staqcould borrow the idea and repurpose it to optimize similar sequences for staqapplications.

In the classical world, a decent modern IDE can use static analysis to identify a lot of redundant code, dead code, suspicious code, no-op blocks, obvious stupidity, etc., before the complier is run. Do you think if staqcan introduce a pass to target those usual suspects as well, especially the self-annihilating sequences? In the long run, that may even help the IDE vendors.

[meamy]

@DevelopDaily Absolutely it would be nice to have this optimization (and others)! Curiously, I thought we already had something that would do this in staq. I just had a look at the code in /include/optimization/simplify.hpp and it looks like was no rule for ccx gates. I just added a rule and pushed an update, the output for the ccx version I'm getting now is (as expected)

OPENQASM 2.0;
include "qelib1.inc";

qreg q[3];
h q[0];
h q[1];
h q[2];

Thanks for pointing this out!

In general we're always looking to get more optimizations into staq, and Vlad and I both do research in quantum compiler optimizations. I've got a few in the works that will hopefully be added into staq in the future, but new ideas are always helpful too!

[DevelopDaily]

Indeed, ccxworks well now. Thanks!

I'm glad you guys are doing research constantly in this area. I hope staqwill be able to trim the fat from all kinds of obese code eventually.

Since ccx simplification is implemented with a rule-based approach, it won't be able to deal with cccxor gates with arbitrary number of control bits. So, I will post a test case for cccxhere for the record. One day, I will come back to test it:-)

OPENQASM 2.0;
include "qelib1.inc";

gate cccx ctrl_0, ctrl_1, ctrl_2, q0
{
    s q0;
    h q0;
    t q0;
    cx ctrl_0,q0;
    tdg q0;
    h q0;
    rz((pi/4)/2) ctrl_2;
    t ctrl_0;
    cx ctrl_2,ctrl_0;
    rz(-(pi/4)/2) ctrl_0;
    rz(((pi*3)/2)+((pi/4)/2)) q0;
    cx ctrl_0,q0;
    cx ctrl_2,q0;
    rz(-(pi/4)/2) q0;
    cx ctrl_2,ctrl_0;
    cx ctrl_0,q0;
    h q0;
    t q0;
    cx ctrl_2,q0;
    tdg q0;
    cx ctrl_0,q0;
    t q0;
    cx ctrl_2,q0;
    tdg q0;
    cx ctrl_0,q0;
    h q0;
    rz((-pi/4)/2) q0;
    rz((pi/4)+((-pi/4)/2)) ctrl_0;
    cx ctrl_2,ctrl_0;
    tdg ctrl_0;
    cx q0,ctrl_0;
    cx ctrl_2,ctrl_0;
    rz(-(-pi/4)/2) ctrl_0;
    cx q0,ctrl_0;
    h q0;
    t q0;
    cx ctrl_1,q0;
    tdg q0;
    cx ctrl_0,q0;
    t q0;
    cx ctrl_1,q0;
    tdg q0;
    cx ctrl_0,q0;
    h q0;
    rz((pi/4)/2) q0;
    rz((pi/4)+((pi/4)/2)) ctrl_0;
    cx ctrl_1,ctrl_0;
    tdg ctrl_0;
    cx q0,ctrl_0;
    cx ctrl_1,ctrl_0;
    rz(-(pi/4)/2) ctrl_0;
    cx q0,ctrl_0;
    h q0;
    s ctrl_2;
    t q0;
    cx ctrl_2,q0;
    tdg q0;
    cx ctrl_0,q0;
    t q0;
    cx ctrl_2,q0;
    tdg q0;
    cx ctrl_0,q0;
    h q0;
    rz((-pi/4)/2) q0;
    rz((pi/4)+((-pi/4)/2)) ctrl_0;
    cx ctrl_2,ctrl_0;
    tdg ctrl_0;
    cx q0,ctrl_0;
    cx ctrl_2,ctrl_0;
    rz(-(-pi/4)/2) ctrl_0;
    cx q0,ctrl_0;
    h q0;
    s ctrl_1;
    t q0;
    cx ctrl_1,q0;
    tdg q0;
    cx ctrl_0,q0;
    t q0;
    cx ctrl_1,q0;
    tdg q0;
    cx ctrl_0,q0;
    h q0;
    t ctrl_0;
    cx ctrl_1,ctrl_0;
    tdg ctrl_0;
    s q0;
    cx ctrl_1,ctrl_0;
    h q0;
    t q0;
    cx ctrl_0,q0;
    tdg q0;
    h q0;
    rz((pi/4)/2) ctrl_1;
    rz((pi/4)/2) ctrl_0;
    cx ctrl_1,ctrl_0;
    rz(-(pi/4)/2) ctrl_0;
    sdg q0;
    cx ctrl_1,ctrl_0;
    h ctrl_1;
    t ctrl_1;
    cx ctrl_2,ctrl_1;
    tdg ctrl_1;
    cx ctrl_0,ctrl_1;
    t ctrl_1;
    cx ctrl_2,ctrl_1;
    tdg ctrl_1;
    cx ctrl_0,ctrl_1;
    h ctrl_1;
    rz((-pi/4)/2) ctrl_1;
    rz((pi/4)+((-pi/4)/2)) ctrl_0;
    cx ctrl_2,ctrl_0;
    tdg ctrl_0;
    cx ctrl_1,ctrl_0;
    cx ctrl_2,ctrl_0;
    rz(-(-pi/4)/2) ctrl_0;
    cx ctrl_1,ctrl_0;
    h ctrl_1;
    s ctrl_2;
    t ctrl_1;
    cx ctrl_2,ctrl_1;
    tdg ctrl_1;
    cx ctrl_0,ctrl_1;
    t ctrl_1;
    cx ctrl_2,ctrl_1;
    tdg ctrl_1;
    cx ctrl_0,ctrl_1;
    h ctrl_1;
    t ctrl_0;
    cx ctrl_2,ctrl_0;
    tdg ctrl_0;
    cx ctrl_2,ctrl_0;
}

qreg q[4];

cccx q[0],q[1],q[2],q[3];
cccx q[0],q[1],q[2],q[3];