Rewiring metadata appear to be incorrect in some circumstances

steve-jeffrey commented 2 years ago

The rewiring metadata returned by the compiler appears to be incorrect in some cases. The metadata are stored in the metadata.final_rewiring field of the response from the gRPC call: response = self._compiler_client.compile_to_native_quil(request) in function quil_to_native_quil in file pyquil.api.abstractcompiler.py.

The test codes and output below demonstrate three cases:

the metadata appear to be correct
the metadata can be mapped and subsequently appear to be correct
I can't see how to interpret/map the metadata.

Case 1. The metadata are correct and the mapping between logical and physical qubit IDs is given by: physical qubit ID = final_rewiring[local_qubit_ID]. This interpretation appears to agree with the documentation.

Code:

from pyquil.gates import CZ, MEASURE
from pyquil.quilbase import Declare
from pyquil import Program, get_qc
qc = get_qc('Aspen-11')
p = Program(
    Declare("ro", "BIT", 2),
    CZ(22, 36),
    MEASURE(22, ("ro", 0)),
    MEASURE(36, ("ro", 1)),
).wrap_in_numshots_loop(10)

np = qc.compiler.quil_to_native_quil(p)
print("Original instructions:")
for instr in p.instructions:
    print(f"{instr}")
print("\nRewiring metadata:")
for index, qubit in enumerate(np.native_quil_metadata.final_rewiring):
    print(f"final_rewiring[{index}] = {qubit}")
print("\nNative quil instructions:")
for instr in np.instructions:
    print(f"{instr}")

Output:

Original instructions:
DECLARE ro BIT[2]
CZ 22 36
MEASURE 22 ro[0]
MEASURE 36 ro[1]

Rewiring metadata:
final_rewiring[0] = 0
final_rewiring[1] = 1
final_rewiring[2] = 2
final_rewiring[3] = 3
final_rewiring[4] = 4
final_rewiring[5] = 7
final_rewiring[6] = 10
final_rewiring[7] = 11
final_rewiring[8] = 12
final_rewiring[9] = 13
final_rewiring[10] = 14
final_rewiring[11] = 15
final_rewiring[12] = 16
final_rewiring[13] = 17
final_rewiring[14] = 20
final_rewiring[15] = 21
final_rewiring[16] = 22
final_rewiring[17] = 23
final_rewiring[18] = 24
final_rewiring[19] = 25
final_rewiring[20] = 26
final_rewiring[21] = 27
final_rewiring[22] = 5
final_rewiring[23] = 30
final_rewiring[24] = 31
final_rewiring[25] = 32
final_rewiring[26] = 33
final_rewiring[27] = 34
final_rewiring[28] = 35
final_rewiring[29] = 36
final_rewiring[30] = 37
final_rewiring[31] = 42
final_rewiring[32] = 43
final_rewiring[33] = 44
final_rewiring[34] = 45
final_rewiring[35] = 46
final_rewiring[36] = 6
final_rewiring[37] = 47
final_rewiring[38] = 8
final_rewiring[39] = 9
final_rewiring[40] = 18
final_rewiring[41] = 19
final_rewiring[42] = 28
final_rewiring[43] = 29
final_rewiring[44] = 38
final_rewiring[45] = 39
final_rewiring[46] = 40
final_rewiring[47] = 41

Native quil instructions:
DECLARE ro BIT[2]
CZ 5 6
MEASURE 6 ro[1]
MEASURE 5 ro[0]

For example, logical qubit 22 (see the original program above) has been mapped to physical qubit 5: final_rewiring[22] = 5

Case 2. The metadata returned by the compiler needs to be remapped as follows: physical qubit ID = final_rewiring[ID], where ID is the index of the logical qubit in an array containing all qubits, arranged in order of qubit ID.

Note: the mapping shown below can be used when: (i) all lattice qubits are used; or (ii) the device (and compiler ISA) are reduced to a subset of the full qubit lattice, and the the user program uses all qubits in the selected sub-lattice.

Code:

from pyquil.gates import I, CZ, MEASURE
from pyquil.quilbase import Declare
from pyquil import Program, get_qc
qc = get_qc('Aspen-11')
p = Program(
    Declare("ro", "BIT", 38),
    CZ(22, 36),
    I(0),
    I(1),
    I(2),
    I(3),
    I(4),
    I(5),
    I(6),
    I(7),
    I(10),
    I(11),
    I(12),
    I(13),
    I(14),
    I(15),
    I(16),
    I(17),
    I(20),
    I(21),
    I(22),
    I(23),
    I(24),
    I(25),
    I(26),
    I(27),
    I(30),
    I(31),
    I(32),
    I(33),
    I(34),
    I(35),
    I(36),
    I(37),
    I(42),
    I(43),
    I(44),
    I(45),
    I(46),
    I(47),
    MEASURE(0, ("ro", 0)),
    MEASURE(1, ("ro", 1)),
    MEASURE(2, ("ro", 2)),
    MEASURE(3, ("ro", 3)),
    MEASURE(4, ("ro", 4)),
    MEASURE(5, ("ro", 5)),
    MEASURE(6, ("ro", 6)),
    MEASURE(7, ("ro", 7)),
    MEASURE(10, ("ro", 8)),
    MEASURE(11, ("ro", 9)),
    MEASURE(12, ("ro", 10)),
    MEASURE(13, ("ro", 11)),
    MEASURE(14, ("ro", 12)),
    MEASURE(15, ("ro", 13)),
    MEASURE(16, ("ro", 14)),
    MEASURE(17, ("ro", 15)),
    MEASURE(20, ("ro", 16)),
    MEASURE(21, ("ro", 17)),
    MEASURE(22, ("ro", 18)),
    MEASURE(23, ("ro", 19)),
    MEASURE(24, ("ro", 20)),
    MEASURE(25, ("ro", 21)),
    MEASURE(26, ("ro", 22)),
    MEASURE(27, ("ro", 23)),
    MEASURE(30, ("ro", 24)),
    MEASURE(31, ("ro", 25)),
    MEASURE(32, ("ro", 26)),
    MEASURE(33, ("ro", 27)),
    MEASURE(34, ("ro", 28)),
    MEASURE(35, ("ro", 29)),
    MEASURE(36, ("ro", 30)),
    MEASURE(37, ("ro", 31)),
    MEASURE(42, ("ro", 32)),
    MEASURE(43, ("ro", 33)),
    MEASURE(44, ("ro", 34)),
    MEASURE(45, ("ro", 35)),
    MEASURE(46, ("ro", 36)),
    MEASURE(47, ("ro", 37)),
).wrap_in_numshots_loop(10)

np = qc.compiler.quil_to_native_quil(p)
print("Original instructions:")
for instr in p.instructions:
    print(f"{instr}")
print(f"\nRewiring metadata:")
for index, qubit in enumerate(np.native_quil_metadata.final_rewiring):
    print(f"final_rewiring[{index}] = {qubit}")
print(f"\nNative quil instructions:")
for instr in np.instructions:
    print(f"{instr}")

# Construct a mapping from logical qubit index ID to it's position in an array of ordered qubits
map = {qubit: index for index, qubit in enumerate(sorted([int(q) for q in qc.to_compiler_isa().qubits.keys()]))}
for lq in [22, 36]:
    pq = np.native_quil_metadata.final_rewiring[map[lq]]
    print(f"Logical qubit {lq} was mapped to physical qubit {pq}")

Output:

Original instructions:
DECLARE ro BIT[38]
CZ 22 36
I 0
I 1
I 2
I 3
I 4
I 5
I 6
I 7
I 10
I 11
I 12
I 13
I 14
I 15
I 16
I 17
I 20
I 21
I 22
I 23
I 24
I 25
I 26
I 27
I 30
I 31
I 32
I 33
I 34
I 35
I 36
I 37
I 42
I 43
I 44
I 45
I 46
I 47
MEASURE 0 ro[0]
MEASURE 1 ro[1]
MEASURE 2 ro[2]
MEASURE 3 ro[3]
MEASURE 4 ro[4]
MEASURE 5 ro[5]
MEASURE 6 ro[6]
MEASURE 7 ro[7]
MEASURE 10 ro[8]
MEASURE 11 ro[9]
MEASURE 12 ro[10]
MEASURE 13 ro[11]
MEASURE 14 ro[12]
MEASURE 15 ro[13]
MEASURE 16 ro[14]
MEASURE 17 ro[15]
MEASURE 20 ro[16]
MEASURE 21 ro[17]
MEASURE 22 ro[18]
MEASURE 23 ro[19]
MEASURE 24 ro[20]
MEASURE 25 ro[21]
MEASURE 26 ro[22]
MEASURE 27 ro[23]
MEASURE 30 ro[24]
MEASURE 31 ro[25]
MEASURE 32 ro[26]
MEASURE 33 ro[27]
MEASURE 34 ro[28]
MEASURE 35 ro[29]
MEASURE 36 ro[30]
MEASURE 37 ro[31]
MEASURE 42 ro[32]
MEASURE 43 ro[33]
MEASURE 44 ro[34]
MEASURE 45 ro[35]
MEASURE 46 ro[36]
MEASURE 47 ro[37]

Rewiring metadata:
final_rewiring[0] = 42
final_rewiring[1] = 43
final_rewiring[2] = 44
final_rewiring[3] = 47
final_rewiring[4] = 45
final_rewiring[5] = 46
final_rewiring[6] = 32
final_rewiring[7] = 31
final_rewiring[8] = 33
final_rewiring[9] = 30
final_rewiring[10] = 34
final_rewiring[11] = 37
final_rewiring[12] = 35
final_rewiring[13] = 36
final_rewiring[14] = 22
final_rewiring[15] = 21
final_rewiring[16] = 23
final_rewiring[17] = 20
final_rewiring[18] = 5
final_rewiring[19] = 24
final_rewiring[20] = 27
final_rewiring[21] = 25
final_rewiring[22] = 26
final_rewiring[23] = 12
final_rewiring[24] = 11
final_rewiring[25] = 13
final_rewiring[26] = 10
final_rewiring[27] = 14
final_rewiring[28] = 4
final_rewiring[29] = 17
final_rewiring[30] = 6
final_rewiring[31] = 15
final_rewiring[32] = 3
final_rewiring[33] = 16
final_rewiring[34] = 2
final_rewiring[35] = 7
final_rewiring[36] = 1
final_rewiring[37] = 0
final_rewiring[38] = 8
final_rewiring[39] = 9
final_rewiring[40] = 18
final_rewiring[41] = 19
final_rewiring[42] = 28
final_rewiring[43] = 29
final_rewiring[44] = 38
final_rewiring[45] = 39
final_rewiring[46] = 40
final_rewiring[47] = 41

Native quil instructions:
DECLARE ro BIT[38]
CPHASE(pi) 5 6
MEASURE 0 ro[37]
MEASURE 1 ro[36]
MEASURE 7 ro[35]
MEASURE 2 ro[34]
MEASURE 16 ro[33]
MEASURE 3 ro[32]
MEASURE 15 ro[31]
MEASURE 6 ro[30]
MEASURE 17 ro[29]
MEASURE 4 ro[28]
MEASURE 14 ro[27]
MEASURE 10 ro[26]
MEASURE 13 ro[25]
MEASURE 11 ro[24]
MEASURE 12 ro[23]
MEASURE 26 ro[22]
MEASURE 25 ro[21]
MEASURE 27 ro[20]
MEASURE 24 ro[19]
MEASURE 5 ro[18]
MEASURE 20 ro[17]
MEASURE 23 ro[16]
MEASURE 21 ro[15]
MEASURE 22 ro[14]
MEASURE 36 ro[13]
MEASURE 35 ro[12]
MEASURE 37 ro[11]
MEASURE 34 ro[10]
MEASURE 30 ro[9]
MEASURE 33 ro[8]
MEASURE 31 ro[7]
MEASURE 32 ro[6]
MEASURE 46 ro[5]
MEASURE 45 ro[4]
MEASURE 47 ro[3]
MEASURE 44 ro[2]
MEASURE 43 ro[1]
MEASURE 42 ro[0]

Logical qubit 22 was mapped to physical qubit 5
Logical qubit 36 was mapped to physical qubit 6

The remapped metadata appear to be correct.

Case 3. I cannot see how to interpret or remap the metadata.

Code:

from pyquil.gates import I, CZ, MEASURE
from pyquil.quilbase import Declare
from pyquil import Program, get_qc
qc = get_qc('Aspen-11')
p = Program(
    Declare("ro", "BIT", 2),
    CZ(22, 36),
    I(44),
    MEASURE(22, ("ro", 0)),
    MEASURE(36, ("ro", 1)),
).wrap_in_numshots_loop(10)

np = qc.compiler.quil_to_native_quil(p)
print("Original instructions:")
for instr in p.instructions:
    print(f"{instr}")
print("\nRewiring metadata:")
for index, qubit in enumerate(np.native_quil_metadata.final_rewiring):
    print(f"final_rewiring[{index}] = {qubit}")
print("\nNative quil instructions:")
for instr in np.instructions:
    print(f"{instr}")

Output:

Original instructions:
DECLARE ro BIT[2]
CZ 22 36
I 44
MEASURE 22 ro[0]
MEASURE 36 ro[1]

Rewiring metadata:
final_rewiring[0] = 5
final_rewiring[1] = 6
final_rewiring[2] = 42
final_rewiring[3] = 0
final_rewiring[4] = 1
final_rewiring[5] = 2
final_rewiring[6] = 3
final_rewiring[7] = 4
final_rewiring[8] = 7
final_rewiring[9] = 10
final_rewiring[10] = 11
final_rewiring[11] = 12
final_rewiring[12] = 13
final_rewiring[13] = 14
final_rewiring[14] = 15
final_rewiring[15] = 16
final_rewiring[16] = 17
final_rewiring[17] = 20
final_rewiring[18] = 21
final_rewiring[19] = 22
final_rewiring[20] = 23
final_rewiring[21] = 24
final_rewiring[22] = 25
final_rewiring[23] = 26
final_rewiring[24] = 27
final_rewiring[25] = 30
final_rewiring[26] = 31
final_rewiring[27] = 32
final_rewiring[28] = 33
final_rewiring[29] = 34
final_rewiring[30] = 35
final_rewiring[31] = 36
final_rewiring[32] = 37
final_rewiring[33] = 43
final_rewiring[34] = 44
final_rewiring[35] = 45
final_rewiring[36] = 46
final_rewiring[37] = 47
final_rewiring[38] = 8
final_rewiring[39] = 9
final_rewiring[40] = 18
final_rewiring[41] = 19
final_rewiring[42] = 28
final_rewiring[43] = 29
final_rewiring[44] = 38
final_rewiring[45] = 39
final_rewiring[46] = 40
final_rewiring[47] = 41

Native quil instructions:
DECLARE ro BIT[2]
CPHASE(pi) 5 6
MEASURE 6 ro[1]
MEASURE 5 ro[0]

It is not clear how the rewiring metadata can be interpreted.

steve-jeffrey commented 3 weeks ago

Quilc appears to return rewiring in two forms:

A list of integers, where the index of the list is the original qubit index, and the value at that index is the new qubit index. For example, if the program contained qubits [2, 5, 7] and the compiler rewired them to [4, 1, 9] respectively, the rewiring metadata would be:
```
      Index:  0  1  2  3  4  5  6  7  8  9
                    |        |     |
      Value:  0  2  4  3  5  1  6  9  7  8
```
A list of integers, where the first "n" elements are the new qubit indexes, in order of the corresponding original indices arranged in ascending order. The remaining elements in the list are the unused new indexes, arranged in ascending order. For example, if the program contained qubits [8, 10, 1, 15] and the compiler rewired them to [1, 2, 10, 9] respectively, the rewiring metadata would be:
```
        Index:  0  1   2   3  4  5  6  7  8  9  10  11  12  13  14  15

        Value: 10  1   2   9  0  3  4  5  6  7   8  11  12  13  14  15
                |  |   |   |
                1  8  10  15  <-- Original qubit indices in ascending order
```

If this is correct, it explains the rewiring generated by quilc.

The attached code can be used to generate rewiring metadata to test the above hypothesis. quilc_metadata_tests.py.gz

steve-jeffrey commented 2 weeks ago

If the nodes in the Program being compiled form a zero-based contiguous set, the rewiring metadata appear to be a simple mapping, and the two formats shown above become equivalent.

quil-lang / quilc

Rewiring metadata appear to be incorrect in some circumstances #787