search

quil-lang / quilc

The optimizing Quil compiler.
Apache License 2.0
454 stars 73 forks source link

Defgate as sequence #785

Closed Spin1Half closed 2 years ago

Spin1Half commented 2 years ago

Proposed implementation of defgate as sequence outlined in issue #762

This adds syntax to Quil and rudimentary integration with the compilation pipeline.

ecpeterson commented 2 years ago

Responding to the general RFC from the Quil stack meeting a couple weeks ago:

I very much like the spirit of this PR / extension to the Quil spec. I don't much care for DEFCIRCUIT, and I think this captures many of the parts of that which are in common use while avoiding some of the snares.

One main concern: what does the second instance of CNOT mean in the following?

DEFGATE CNOT p q AS GATE-SEQUENCE:
    H q
    H p
    CNOT q p
    H q
    H p

Other DEFGATE instances don't suffer from this potential recursion, and I think it's legal in a DEFCIRCUIT (though the compiler's "expand" pass may complain). I believe there's something semantic to pin down here related to name resolution — which, AFAIK, is part of the compiler internals but whose behavior is not expressly prescribed at the level of the language spec.

Spin1Half commented 2 years ago

@ecpeterson The plan right now is to consider any circularity in the definitions invalid (i.e. its fine for one defgate to depend on another, as long as there are no circular dependencies). I have made a validation routine to identify any circular dependencies and produce an error in this case (not pushed yet, stay tuned).

ecpeterson commented 2 years ago

Reasonable 👍, but also restrictive — my understanding from the meeting was that this was to be one way to describe “translators” to the compiler, and the quoted case is such a translator which is presently used.

Just something to think about. Should gates be permitted to have multiple compatible definitions — some potentially “self”-referencing another definition? Maybe! Sounds like a lot of work to make use of, but it could be worth consciously avoiding making the present guts deeply incompatible with such a future.

stylewarning commented 2 years ago

I think it's a reasonable restriction if these must act as unambiguous gate definitions. I think the restriction could be lifted if we go in the direction of adding a keyword (eg DEFGATE blah AS ALTERNATIVE blah) or a pragma (I'm less enthusiastic) which won't install the gate as a definition, but rather as an identity to be dwelled upon. Something like ALTERNATIVE implies there was already an unambiguous definition somewhere.

Spin1Half commented 2 years ago

I believe this PR to be functionally complete, so I will take it out of draft. Though I certainly expect there are spots that can be improved. Looking forward to any feedback!

Spin1Half commented 2 years ago

I've just noticed that nothing is preventing multiple sequence gate definitions with the same name from happening. But this seems to also be the case for other def gates as well (I tested with pauli sum and it seemed to compile, though I didnt nail down the behavior, e.g. which gate it will actually use if they are different unitaries).

Not sure if its worth having some sort of validation to prevent this (until something like defgate alternatives is implemented)

Edit: This is not within the scope of this PR and I've opened a separate issue which I plan to take care of soon https://github.com/quil-lang/quilc/issues/797