Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimization by self-annihilating sequences #37

Open
DevelopDaily opened this issue Feb 2, 2021 · 2 comments
Open

Optimization by self-annihilating sequences #37

DevelopDaily opened this issue Feb 2, 2021 · 2 comments
Assignees
Labels
enhancement New feature or request

Comments

@DevelopDaily
Copy link

DevelopDaily commented Feb 2, 2021

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.

@meamy
Copy link
Collaborator

meamy commented Feb 2, 2021

@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
Copy link
Author

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];


@meamy meamy added the enhancement New feature or request label Feb 3, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

3 participants