staq
staq copied to clipboard
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];