DefPermutationGate compilation may be incorrect for some permutations

[steve-jeffrey]

The code shown below indicates there is a problem compiling selected permutation gates (DefPermutationGate). The code uses four methods:

1. Wavefunction simulator
2. QVM, with the circuit compiled using quilc
3. QVM, without compilation
4. Manual calculation of the gate matrices using numpy,

to evaluate a circuit consisting of one X gate and one permutation gate. The results indicate:

• If the permutation corresponds to a single SWAP, all four methods yield the same result.
• If the permutation corresponds to multiple SWAPs, or an arbitrary permutation, the result from method 2 (QVM with compilation) appears to differ from the other three methods.

from collections import Counter
import numpy as np
from pyquil.gates import X, MEASURE
from pyquil import Program, get_qc
from pyquil.quilbase import DefPermutationGate
from pyquil.api import WavefunctionSimulator

permutation = [0, 4, 2, 6, 1, 5, 3, 7]   # Corresponds to SWAP(0,2) - results from all methods agree
permutation = [0, 2, 1, 3, 4, 6, 5, 7]   # Corresponds to SWAP(1,2) - results from all methods agree
permutation = [0, 4, 1, 5, 2, 6, 3, 7]   # Corresponds to SWAP(1,2) + SWAP(0,2) - results from method 2 disagree
permutation = [5, 1, 2, 6, 7, 0, 4, 3]   # Arbitrary permutation - results from method 2 disagree

permutation_gate_def = DefPermutationGate("permutation_gate", permutation)
permutation_gate = permutation_gate_def.get_constructor()
program = Program()
program.declare("ro", "BIT", 3)
program += permutation_gate_def
program += X(0)
program += permutation_gate(0, 1, 2)
program += MEASURE(0, ("ro", 0))
program += MEASURE(1, ("ro", 1))
program += MEASURE(2, ("ro", 2))

# QVM wave function simulator
wf_sim = WavefunctionSimulator()
wf_results = wf_sim.wavefunction(program)
print(f"Wavefunction simulator result: {wf_results}")
print("\tNote: the wavefunction simulator reverses the bit order\n")

# QVM - with compilation
qc = get_qc('3q-qvm')
program.wrap_in_numshots_loop(100)
qvm_results = qc.run(qc.compile(program, to_native_gates=True, optimize=True)).readout_data.get("ro")
histogram = Counter([tuple(shot_result) for shot_result in qvm_results])
print(f"QVM result with compilation: {histogram}\n")

# QVM - without compilation
program.wrap_in_numshots_loop(100)
qvm_results = qc.run(program).readout_data.get("ro")
# Note: we could also disable compilation using:
#       qvm_results = qc.run(qc.compile(program, to_native_gates=False, optimize=False)).readout_data.get("ro")
histogram = Counter([tuple(shot_result) for shot_result in qvm_results])
print(f"QVM result without compilation: {histogram}\n")

# Compute the result manually
X_np = np.array([[0, 1], [1, 0]])
permutation_gate_np = np.array([[0] * col + [1] + [0] * (len(permutation) - 1 - col) for col in permutation])
I2 = np.array([[1, 0], [0, 1]])
XII = np.kron(X_np, np.kron(I2, I2))
psi_000 = np.array([1] + [0] * 7)
manual_result = permutation_gate_np @ XII @ psi_000
print(f"Manual result: {manual_result}")

Output:

Wavefunction simulator result: (1+0j)|011>
    Note: the wavefunction simulator reverses the bit order

QVM result with compilation: Counter({(1, 1, 1): 100})

QVM result without compilation: Counter({(1, 1, 0): 100})

Manual result: [0 0 0 0 0 0 1 0]

Note: the manual result "0 0 0 0 0 0 1 0" corresponds to state |110⟩, which I think is the correct result for the [5, 1, 2, 6, 7, 0, 4, 3] permutation.

The code was tested using quilc 1.26.0, qvm 1.17.2 (as pulled from DockerHub) and pyquil 3.1.0.

The attachments contain the compiled instructions (i.e. the output from qc.compile(program)) for two cases:

• the arbitrary permutation, as shown above
• the permutation consisting of two SWAPs (SWAP(1,2) followed by SWAP(0,2)) compiled_program_arbitrary_permutation.txt compiled_program_two_SWAPs.txt

[stylewarning]

Repro with plain Quil:

(defun test-perm-thing ()
  (let* ((p (quil:parse-quil
             "
DEFGATE PERM AS PERMUTATION:
    5, 1, 2, 6, 7, 0, 4, 3

DECLARE ro BIT[3]

X 0
PERM 0 1 2
MEASURE 0 ro[0]
MEASURE 1 ro[1]
MEASURE 2 ro[2]
"))
         (p* (cl-quil::compiler-hook p (cl-quil::build-nq-linear-chip 3)))
         (q (make-qvm 3))
         (q* (make-qvm 3)))
    (load-program q p :supersede-memory-subsystem t)
    (load-program q* p* :supersede-memory-subsystem t)

    (format t "Without Compilation:~%")
    (run q)
    (dotimes (i 3)
      (format t "   ro[~D] = ~D~%" i (memory-ref q "ro" i)))

    (format t "~%With Compilation:~%")
    (run q*)
    (dotimes (i 3)
      (format t "   ro[~D] = ~D~%" i (memory-ref q* "ro" i)))))

Running this gives:

QUIL> (qvm::test-perm-thing)
Without Compilation:
   ro[0] = 1
   ro[1] = 1
   ro[2] = 0

With Compilation:
   ro[0] = 1
   ro[1] = 1
   ro[2] = 1

[stylewarning]

Repro without the QVM as a QUILC failure:

(deftest test-perm-compilation ()
  (let* ((chip (quil::build-nq-linear-chip 3 :architecture ':cnot))
         (orig-prog (quil::parse-quil "
DEFGATE PERM AS PERMUTATION:
    5, 1, 2, 6, 7, 0, 4, 3

X 0
PERM 0 1 2
"))
         (orig-matrix (quil:parsed-program-to-logical-matrix orig-prog))
         (proc-prog (quil::compiler-hook orig-prog chip))
         (proc-matrix (quil:parsed-program-to-logical-matrix proc-prog))
         (2q-code (program-2q-instructions proc-prog)))
    (is (quil::matrix-equals-dwim orig-matrix proc-matrix))
    (is (every (link-nativep chip) 2q-code))))

[stylewarning]

Found the bug. The compiler was compiling the inverse permutations. Fixed in https://github.com/quil-lang/quilc/pull/806.

[stylewarning]

Fixed in master.