search

rigetti / pyquil

A Python library for quantum programming using Quil.
http://docs.rigetti.com
Apache License 2.0
1.4k stars 342 forks source link

Program comparison #24

Closed ncrubin closed 7 years ago

ncrubin commented 7 years ago

Compare two programs for equality. For simplicity start with programs built with protoquil.

willzeng commented 7 years ago

Do you mean exact syntactical equality or semantic equality?

ncrubin commented 7 years ago

I think starting with syntactical equality is easiest. I would imagine semantic equality checks would require examination of the associated unitaries.

willzeng commented 7 years ago

I agree, this issue can be scoped for syntactic equality for now. Figuring out semantic control flow equivalence is also non-trivial.

willzeng commented 7 years ago

@ampolloreno @stevenheidel We could start with .out() but what would really be useful to add would be to tell equivalence as quantum circuits, e.g. not going as far as calculating if the circuits are the same unitary but noticing that

X 0
X 1

and 

X 1
X 0

are the same program.

I know that @ecp-rigetti implemented some functionality for generating quantum circuit data structures from Quil programs that would be useful for this. @ecp-rigetti how close was that to being PR ready?

willzeng commented 7 years ago

We could also use that data structure to help with #33

ecpeterson commented 7 years ago

It's in decent shape: what's written organizes pyQuil circuits into "logically parallelizable units", which falls somewhat short of the original goals of (1) drawing circuits and (2) actually doing any gate compression, but it's totally suitable for this purpose. If the PR has serious errors, I think they stem from me not understanding what pyQuil's resource_manager passing is really doing, so if someone is going to pick the PR up, they should spend a while looking at that specifically to make sure that it's OK.

I wrote the PR as we were moving to internal tools, and I wasn't sure what repos were staying where, so I moved the PR inside for caution's sake. I'll send you all the link in a moment.

stevenheidel commented 7 years ago

So I've been thinking more about this: it seems like the majority use case for program comparison is in testing. I ran into this when writing the parser and grove has several custom util functions for defining that programs are the same.

I suggest we add a default 'eq' method that essentially checks if the python structures are the same.

Eric's code should be merged in too but under a custom name. Following the principle of least surprise: I personally would not expect == to do any sort of fancy scheduling or qubit swapping.