search

quil-lang / quilc

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

Controlled gates (other than RX,RY, RZ) with symbolic parameters don't compile #887

Open steve-jeffrey opened 1 year ago

steve-jeffrey commented 1 year ago

Description

Controlled gates (other than RX, RY, RZ) with symbolic parameters will not compile.

Controlled RX, RY, RZ gates with symbolic parameters will compile (see related issue).

How to Reproduce

Either run the example code provided, or:

echo 'DECLARE phi REAL[1];CONTROLLED PHASE(phi) 1 0' | docker run --rm -i rigetti/quilc

and

echo 'DECLARE phi REAL[1];CONTROLLED XY(phi) 2 0 1' | docker run --rm -i rigetti/quilc

Code Snippet

from pyquil import Program, get_qc
from pyquil.gates import RY, XY, PHASE

program = Program()
phi = program.declare("phi", "REAL")
program += RY(phi, 0).controlled(1)  # Works
program += XY(1.23, 0, 1).controlled(2)  # Works
program += PHASE(phi, 0).controlled(1)  # Fails: Condition CL-QUIL::COMPILER-DOES-NOT-APPLY was signalled.
program += XY(phi, 0, 1).controlled(2)  # Fails: Condition CL-QUIL::UNKNOWN-GATE-PARAMETER was signalled.

qc = get_qc("3q-qvm")
native = qc.compiler.quil_to_native_quil(program)

Error Output

Condition CL-QUIL::COMPILER-DOES-NOT-APPLY was signalled

or

Condition CL-QUIL::UNKNOWN-GATE-PARAMETER was signalled

Environment

Quilc version 1.26.0

ecpeterson commented 1 year ago

Fair enough. A generic analytic compilation routine for parametric gates, including controlled versions of simple gates, is somewhere between hard and impossible — but for specific cases, we can probably figure it out.

Definitely CONTROLLED PHASE is a variant of CONTROLLED RZ up to local phase. I think, but I am not certain, that CONTROLLED XY p q r is XY q r followed by a (CZ p q)-conjugate of XY q r, maybe with some more local gates to balance out phases. One would have to chase it out.

ecpeterson commented 1 year ago

It doesn't look like there's any phase to chase. Here's some quilc -P -m output:

XY(0.4) 0 1
CZ 2 1
XY(-0.4) 0 1
CZ 2 1

#Matrix read off from input code (unitary)
#<MATRIX/COMPLEX-DOUBLE-FLOAT (8x8):
#   1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.921 + 0.000j     0.000 + 0.389j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.389j     0.921 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j>

which looks like the controlled version of

XY(0.8) 0 1

#Matrix read off from input code (unitary)
#<MATRIX/COMPLEX-DOUBLE-FLOAT (4x4):
#   1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.921 + 0.000j     0.000 + 0.389j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.389j     0.921 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j>

For funsies, here's a recipe for CONTROLLED CONTROLLED XY(0.8) 3 2 1 0:

CONTROLLED CONTROLLED Z 3 2 1
XY(-0.4) 0 1
CONTROLLED CONTROLLED Z 3 2 1
XY(0.4) 0 1

#Matrix read off from input code (unitary)
#<MATRIX/COMPLEX-DOUBLE-FLOAT (16x16):
#   1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.921 + 0.000j     0.000 + 0.389j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.389j     0.921 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j>

and a recipe for FORKED XY(0.35, 0.25) 2 1 0:

XY(0.3) 0 1
CZ 2 1
XY(0.05) 0 1
CZ 2 1

#<MATRIX/COMPLEX-DOUBLE-FLOAT (8x8):
#   1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.985 + 0.000j     0.000 + 0.174j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.174j     0.985 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.992 + 0.000j     0.000 + 0.125j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.125j     0.992 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     1.000 + 0.000j>

@stylewarning: This sounds like it should be tagged "good first issue". I don't have tag permissions, myself.

ecpeterson commented 1 year ago

Just to finish the job, here's an example circuit which relates CONTROLLED PHASE and CONTROLLED RZ by implementing the identity:

CONTROLLED RZ(0.4) 1 0
RZ(0.2) 1

CONTROLLED PHASE(-0.4) 1 0

#Matrix read off from input code (unitary)
#<MATRIX/COMPLEX-DOUBLE-FLOAT (4x4):
#   0.995 - 0.100j     0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.995 - 0.100j     0.000 + 0.000j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.995 - 0.100j     0.000 + 0.000j
#   0.000 + 0.000j     0.000 + 0.000j     0.000 + 0.000j     0.995 - 0.100j>
ecpeterson commented 4 months ago

The decomposition of FORKED ... FORKED XY proposed here is what's already done in ucr-explode.lisp . To extend that to handle CZ decompositions of FORKED XY, we need only change uniformly-controlled-roll-p to permit "XY" as a gate name. To make this more ergonomic, there are then some other translators to write, like converting CONTROLLED XY into FORKED XY.

Dunno about the ISWAP version of the same change, since that compiler is also guarded by uniformly-controlled-roll-p. The easiest fix is to change the error in the cond to a try-next-compiler. Another thought, though, is to try dropping the ISWAP version entirely; since we began trampolining, I'm not sure we've (in the relevant era: I've) checked that the ISWAP-specific decomposition is giving something better than chaining UCR->CZ->ISWAP + compressor. If it isn't, let's drop it. If it is, then it shouldn't be hard to bang out the same hand-optimizations that went into building the old ISWAP decompositions, which are based off of the CZ->ISWAP translator anyway.