JuliaSymbolics/Metatheory.jl

project that manipulate quantum circuit using Metatheory.jl

overshiki opened this issue · 11 comments

overshiki commented

Hi,
I wrote a package SymbolicCircuit.jl. It provides a symbolic system for the representation of quantum circuit, in which, one can manipulate quantum circuit using term rewriting & equality saturation techniques.

This project is highly dependent on and highly motivated by Metatheory.jl. So, thanks a lot for your great work!

Roger-luo commented

Hi I noticed you forked YaoEgraph a while ago, I can see the design of your IR is quite similar, I'm wondering if you know YaoHIR/YaoBlocks? For the compilation efforts it seems you are building something similar to YaoCompiler's IR or YaoBlocks with egraph.

we have been working on this direction for a while too, the old fork from @0x0f0f0f was for helping us fix a bug, we recently made it private because we want to improve it more before releasing. We have been working towards better circuit compilation for a while, e.g we also have ZX calculus, Quon, and YaoCompiler.

I'm happy to chat over zoom if you want to join efforts. See below, I think it would be nice if you could instead work on Yao which provides more advanced tools.

GiggleLiu commented

Neat work! I want invite you to the monthly Yao community call, where you can get more resources and information. From the next month, I and @Roger-luo will introduce each modules in detail, and we are polishing the documentation now (this time it is real!).

The reason why I want to invite you is because I saw some duplicated efforts here, for example,

I do not mean you should have known this, I mean if you can join the community call, we can avoid such duplicated efforts. You can focus on the creative part, while your need will also help improve Yao too. Yao is well maintained, and light weighted quantum simulator, it is not a formidable at all to add it as a dependency. I and Roger are both happy to play a supportive role, like change the protocal to support new features.

julia> @time using Yao
  1.754890 seconds (4.92 M allocations: 328.584 MiB, 0.78% gc time, 34.27% compilation time)

julia> @time rand_state(3) |> put(3, 2=>X)
  0.068815 seconds (261.49 k allocations: 13.971 MiB, 99.32% compilation time)
ArrayReg{2, ComplexF64, Array...}
    active qubits: 3/3
    nlevel: 2

@Roger-luo do you have any idea how to invite @overshiki to the community call?

Roger-luo commented

@Roger-luo do you have any idea how to invite @overshiki to the community call?

Just join Julia slack, find #yao-dev channel, we will post the link&posts there

overshiki commented

Hi @Roger-luo,
Yes, of course, I know YaoBlocks. Yao.jl(and the paper by you guys) is very educative to me and I really appreciate it!
And I'm happy to join the efforts of Yao.jl! We can talk about it over the #yao-dev channel, if available.

And there are some reasons why SimbolicCircuit.jl didn't use YaoBlocks IR:

When I got the symbolic idea from the JuliaSymbolics community(thanks a lot), I had an intuition that the circuit IR should be as simple as possible for a symbolic system to work. Then I realized that a chain of gates from left to right connected by a single symbol such as * is a perfect fit! One of the benefits of this is that the associative rule could be easily defined.

I also read about YaoEgraph.jl and considered the possibility of directly using Yao.jl's IR. But at that time, it seems complicated, since YaoBlock is not just a chain of gate, it has a lot of powerful and flexible building blocks, which is a distraction from my goal.

It is a pity that I don't know much about YaoCompiler.jl. If there are more documents about it, I'm willing to learn!

And ZX calculus is a really powerful framework for circuit simplification, but currently, it is not easy to do it symbolically(graph manipulation is hard). One of my goals in building SimbolicCircuit.jl is to see if the symbolic system for circuit could have similar performance with ZX calculus, I'm just curious.

In summary, yes, if Yao.jl has a similar goal for a symbolic system, I'm willing to give it a try!

overshiki commented

Hi @GiggleLiu,
Thanks a lot for your invitation! Yes, it is a pleasure to join, and I'm eager to learn more about Yao.jl, it is such a great work.

And you are right, I can take advantage of a lot of features provided by Yao.jl to avoid duplicated efforts.

  • The constants and ConstantGate link you provided are very helpful, I think I could give it a try for the next step.
  • And also YaoToEinsum.jl, yes, it is helpful, just turning my circuit object into YaoBlock will save me a lot of time.

Actually, I just newly implemented an interface to turn the circuit in SymbolicCircuit.jl into YaoBlock, see example here. Doing so, I immediately get the plot function using YaoPlots.jl! Connecting to Yao.jl is such a beneficial step. So, thanks a lot to the Yao community!

Roger-luo commented

When I got the symbolic idea from the JuliaSymbolics community(thanks a lot), I had an intuition that the circuit IR should be as simple as possible for a symbolic system to work. Then I realized that a chain of gates from left to right connected by a single symbol such as * is a perfect fit! One of the benefits of this is that the associative rule could be easily defined.

You don't need a * operator to make it work. That's just syntax.

I also read about YaoEgraph.jl and considered the possibility of directly using Yao.jl's IR. But at that time, it seems complicated, since YaoBlock is not just a chain of gate, it has a lot of powerful and flexible building blocks, which is a distraction from my goal.

This is exactly why YaoHIR was created and it works directly with metatheory as well as MLStyle. That's why I'm saying this is duplicating efforts. And we put a lot effort to make sure this IR also works with Julia compiler.

One of my goals in building SimbolicCircuit.jl is to see if the symbolic system for circuit could have similar performance with ZX calculus, I'm just curious.

This is also what we are tying to see in YaoEgraph 😅

overshiki commented

You don't need a * operator to make it work. That's just syntax.

I mean, in my case * symbol is the most straightforward way, and it looks more symbolic :). Of course, you can use chain(gate, gate) style, they are equivalent in julia AST.

And we put a lot effort to make sure this IR also works with Julia compiler

That is really cool! and I'm willing to learn more. However, currently, it seems to lack documentation. And I'm also looking forward to the release of YaoEgraph. As you mentioned, it is now in a private development state.

One of my goals in building SimbolicCircuit.jl is to see if the symbolic system for circuit could have similar performance with ZX calculus, I'm just curious.

This is also what we are tying to see in YaoEgraph

Currently, the Eqsat solution is not a perfect one, for a long circuit, the system may need too long time and too much resources to saturate, see an issue here. One of the reasons is the expensive associative rule(I guess), and much effort should be laid in this direction(I suppose). To improve the performance of egraph on the symbolic circuit system is my next key plan, and of course, I'm willing to join the effort of Yao community to make the symbolic idea really helpful to the field of quantum computation.

overshiki commented

To all who may concern, the goal of SymbolicCircuit.jl is to build a lightweight package that focuses on symbolic system. It is symbolic first and allows users to easily define any syntactic rules they would like. Future plans include a user-friendly egraph interface based on Metatheory.jl, so that egraph algorithm suitable for symbolic quantum circuits could be more easily designed. Applications of this symbolic system are not limited to circuit simplification, any circuit generator based on syntactic rules is possible.

Thanks to the reminder of @Roger-luo and @GiggleLiu, SymbolicCircuit.jl will take advantage of many Yao.jl functions to handle the plot and numerical task, to avoid duplicated efforts and keep it lightweight.

And thanks @0x0f0f0f for allowing me to post such an issue here:)

Again, Metatheory.jl is excellent work! I could see a lot of possible applications based on it.

overshiki commented

Hi @Roger-luo

I noticed you forked YaoEgraph a while ago, I can see the design of your IR is quite similar, I'm wondering if you know YaoHIR/YaoBlocks? For the compilation efforts it seems you are building something similar to YaoCompiler's IR or YaoBlocks with egraph

I think I got what you mean. I must say that the version of my fork of YaoEgraph is quite broken, I can barely know anything about the progress of YaoEgraph from it. And the similarity about the IR, I have to say, most framework of quantum computation looks alike, especially if you want to do it symbolically. My intuition about the circuit IR actually comes from mindquantum, it treats circuit as a List in python, much more intuitive than YaoBlock.

The key point of a symbolic system on quantum circuit, is not how it looks like, it is how it solves the problem of defining rules! Unfortunately, currently, I can see no rules related with YaoEgraph. SymbolicCircuit.jl currently provide single gate mutate rules, CNOT & T gate mutate rules, unitary cancel rules, and block simplification collapse rule for numerical simulation, there are more rules awaiting and could be easily defined within the system.

The development of SymbolicCircuit.jl is totally independent of YaoEgraph and YaoHIR. Actually, I have posted a lot of issues in Metatheory.jl to help solving the problems I have encountered.

Hope this clarified your concern.

Roger-luo commented

The development of SymbolicCircuit.jl is totally independent of YaoEgraph and YaoHIR. Actually, I have posted a lot of issues in Metatheory.jl to help solving the problems I have encountered.

Hope this clarified your concern.

Thanks for your clarification. I guess we just happen to be working on the same thing then! There's a lot problems to explore in this area. We should chat directly, I sent you an email.

overshiki commented

There's a lot problems to explore in this area

Cool, happy to cooperate!