Compiler outputs different programs non-deterministically

[mhodson-rigetti]

Compiling the following bell-state program via pyquil on "9q-square-qvm":

    program = Program()
    ro = program.declare("ro", "BIT", 2)
    program.inst(H(1))
    program.inst(CNOT(1, 4))
    program.inst(MEASURE(1, ro[0]))
    program.inst(MEASURE(4, ro[1]))

... using the following quilc ISA patched to remove CZ gates (force use of XY)

{'1Q': {'1': {'gates': [{'operator': 'I', 'parameters': [], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [0], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [1.5707963267948966], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [-1.5707963267948966], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [3.141592653589793], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [-3.141592653589793], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RZ', 'parameters': ['theta'], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'MEASURE', 'qubit': '_', 'target': '_', 'duration': None, 'fidelity': None}, {'operator': 'MEASURE', 'qubit': '_', 'target': None, 'duration': None, 'fidelity': None}]}, '4': {'gates': [{'operator': 'I', 'parameters': [], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [0], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [1.5707963267948966], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [-1.5707963267948966], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [3.141592653589793], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RX', 'parameters': [-3.141592653589793], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'RZ', 'parameters': ['theta'], 'arguments': ['_'], 'fidelity': None, 'duration': None}, {'operator': 'MEASURE', 'qubit': '_', 'target': '_', 'duration': None, 'fidelity': None}, {'operator': 'MEASURE', 'qubit': '_', 'target': None, 'duration': None, 'fidelity': None}]}}, '2Q': {'1-4': {'gates': [{'operator': 'XY', 'parameters': ['theta'], 'arguments': ['_', '_'], 'fidelity': None, 'duration': None}]}}}

... generates two different native programs with seemingly non-deterministic behavior:

DECLARE ro BIT[2]
RZ(-pi/2) 1
RX(-pi/2) 1
RZ(pi) 4
XY(pi) 1 4
RZ(pi/2) 1
RX(pi/2) 1
RZ(-pi/2) 1
XY(pi) 1 4
RX(-pi/2) 4
MEASURE 4 ro[1]
MEASURE 1 ro[0]

(most of the time)

DECLARE ro BIT[2]
RZ(pi/2) 1
RX(pi/2) 1
RZ(pi) 4
RX(-pi/2) 4
XY(pi) 1 4
RZ(-pi/2) 1
RX(pi/2) 1
RZ(pi/2) 1
XY(pi) 1 4
MEASURE 4 ro[1]
MEASURE 1 ro[0]

(occasionally)

[colescott]

Are you able to upload the verbose output of quilc for both outputs to see what the compiler is up to?

[mimigdal]

I have a similar problem. See attached script. Sometimes I get the answer reported in the last cell and sometimes the answer in the one before the last cell. I couldn't identify any pattern of when I get one answer or another. I noticed that if I use "device_name=40q-qvm" instead of "device_name=Aspen-9-qvm", the program is compiled differently (i.e. CZ gate is used instead of CPHASE(pi)) and there's no problem. Interestingly, both the program reported here and the one I used involve the XY gate.

compiler_question.zip

[stylewarning]

I've noticed this non-determinism more as-of-late as well, and it's irksome. I sometimes have to run the compiler 2-3 times to find the "best" one of the bunch, and I'm not yet sure of the source of the issue.

[stylewarning]

I labeled this as a bug due to its woeful disregard of expectations, even though it may not be "wrong".

@mimigdal It's almost surely due to some routines in the compiler which depend on non-determinism. Those are being looked into now.

[mimigdal]

Thanks Robert, my wild guess is that this is due to numerical precision, something like an if clause asking whether 0.999999997 is smaller or bigger than 1.00000003. These are things that can change randomly from run to run. I noticed that these problems are generated when the compiler tries to substitute a CZ gate with the product of two XY gates. So, I would start looking at the place where XY gates are first introduced by the compiler.

On Mon, Oct 25, 2021, 14:54 Robert Smith @.***> wrote:

I labeled this as a bug due to its woeful disregard of expectations, even though it may not be "wrong".

@mimigdal https://github.com/mimigdal It's almost surely due to some routines in the compiler which depend on non-determinism. Those are being looked into now.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/quil-lang/quilc/issues/676#issuecomment-951257105, or unsubscribe https://github.com/notifications/unsubscribe-auth/APEAB2UXRE25PRZ5ALTGYQDUIWYWHANCNFSM4SRLQRZA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

[stylewarning]

CC @macrologist