softwareQinc
Optimization by self-annihilating sequences
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 staq with 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 staq wants to achieve. Nevertheless, the authors introduced an interesting idea of removing self-annihilating sequences. I am wondering if staq could borrow the idea and repurpose it to optimize similar sequences for staq applications.
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 staq can 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.
@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!
Indeed, ccx works well now. Thanks!
I'm glad you guys are doing research constantly in this area. I hope staq will 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 cccx or gates with arbitrary number of control bits. So, I will post a test case for cccx here 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];