Implement measurement pattern for Toffoli gate

[king-p3nguin]

Before submitting, please check the following:

• Make sure you have tests for the new code and that test passes (run pytest)
• format added code and tests by black -l 120 <filename>
• If applicable, add a line to the [unreleased] part of CHANGELOG.md, following keep-a-changelog.

Then, please fill in below:

Context (if applicable):

Description of the change:

Related issue:

• Resolves #49

also see that checks (github actions) pass. If lint check keeps failing, try installing black==22.8.0 as behavior seems to vary across versions.

[shinich1]

@king-p3nguin hi, just want to see how it's going as UnitaryHack finishes early next week.

[king-p3nguin]

@shinich1 Thank you for the reminder. I am a bit busy and unsure I can meet the deadline, but I will work on this issue even if the UnitaryHack is finished.

[natestemen]

Nice work with this hack @king-p3nguin! Just a reminder that PRs are eligible for unitaryHACK bounties as long as the issue is closed before June 20th! The hackathon finishes EOD June 13th AoE, and as long as the PR is up by this deadline, it is eligible! We understand it can take some time to get reviewed and make changes.

[shinich1]

@king-p3nguin Good that it works now! could you modify test cases to include ccz gate (perhaps add to random_circuit.py for now), and also add lines to docs (.rst files) where necessary? also - perhaps you can use -l 120 option for black to save up on line numbers in transpilar.py (see above)?

[king-p3nguin]

@shinich1 Okay, I think I can do that. Unfortunately, there still seems to be some issue in the ccx commands... I thought simply replacing the commands from the original pattern with each variable would work, but it did not. I wrote the following code to replace the commands. Maybe you can spot the bug.

from graphix.transpiler import Circuit
import numpy as np

circuit = Circuit(3)
# toffoli
circuit.h(2)
circuit.cnot(1, 2)
circuit.rz(2, -np.pi / 4)
circuit.cnot(0, 2)
circuit.rz(2, np.pi / 4)
circuit.cnot(1, 2)
circuit.rz(1, np.pi / 4)
circuit.rz(2, -np.pi / 4)
circuit.cnot(0, 2)
circuit.cnot(0, 1)
circuit.rz(2, np.pi / 4)
circuit.rz(0, np.pi / 4)
circuit.rz(1, -np.pi / 4)
circuit.h(2)
circuit.cnot(0, 1)

# transpile
pattern = circuit.transpile()
pattern.standardize()
pattern.shift_signals()
pattern.perform_pauli_measurements()

dictonary = {  # for opt = True
    0: "ancilla[0]",
    1: "ancilla[1]",
    5: "ancilla[2]",
    9: "ancilla[3]",
    13: "ancilla[4]",
    21: "ancilla[5]",
    25: "control_node1",
    28: "target_node",
    29: "ancilla[6]",
    30: "control_node2",
}
# dictonary = { # for opt = False
#     0: "ancilla[0]",
#     1: "ancilla[1]",
#     2: "ancilla[2]",
#     3: "ancilla[3]",
#     4: "ancilla[4]",
#     5: "ancilla[5]",
#     6: "ancilla[6]",
#     7: "ancilla[7]",
#     8: "ancilla[8]",
#     9: "ancilla[9]",
#     10: "ancilla[10]",
#     11: "ancilla[11]",
#     12: "ancilla[12]",
#     13: "ancilla[13]",
#     14: "ancilla[14]",
#     15: "ancilla[15]",
#     16: "ancilla[16]",
#     17: "ancilla[17]",
#     18: "ancilla[18]",
#     19: "ancilla[19]",
#     20: "ancilla[20]",
#     21: "ancilla[21]",
#     22: "ancilla[22]",
#     23: "ancilla[23]",
#     24: "ancilla[24]",
#     26: "ancilla[25]",
#     27: "ancilla[26]",
#     29: "ancilla[27]",
#     25: "control_node1",
#     28: "target_node",
#     30: "control_node2",
# }
import numpy as np
for i in range(len(pattern.seq)):
    if pattern.seq[i][0] == "E":
        print(
            f'seq.append(["E", ({dictonary[pattern.seq[i][1][0]]}, {dictonary[pattern.seq[i][1][1]]})])'
        )
    elif pattern.seq[i][0] == "M":
        s_domain = pattern.seq[i][4]
        new_s_domain = []
        for sidx in s_domain:
            if sidx in new_s_domain:
                continue
            try:
                new_s_domain.append(dictonary[sidx])
            except KeyError:
                continue
        t_domain = pattern.seq[i][5]
        new_t_domain = []
        for tidx in t_domain:
            if tidx in new_t_domain:
                continue
            try:
                new_t_domain.append(dictonary[tidx])
            except KeyError:
                continue
        try:
            print(
                f'seq.append(["M", {dictonary[pattern.seq[i][1]]}, "{pattern.seq[i][2]}", {pattern.seq[i][3]}, [{", ".join(new_s_domain)}], [{", ".join(new_t_domain)}], {pattern.seq[i][6]}])'
            )
        except IndexError:
            print(
                f'seq.append(["M", {dictonary[pattern.seq[i][1]]}, "{pattern.seq[i][2]}", {pattern.seq[i][3]}, [{", ".join(new_s_domain)}], [{", ".join(new_t_domain)}]])'
            )
    elif pattern.seq[i][0] == "X":
        # remove duplicates
        _domain = np.array(pattern.seq[i][2])
        uind = np.unique(_domain)
        unique_domain = []
        for ind in uind:
            if np.mod(np.count_nonzero(_domain == ind), 2) == 1:
                unique_domain.append(ind)

        new_domain = []
        for idx in unique_domain:
            try:
                new_domain.append(dictonary[idx])
            except KeyError:
                continue
        if new_domain == []:
            continue
        print(
            f'seq.append(["X", {dictonary[pattern.seq[i][1]]}, [{", ".join(new_domain)}]])'
        )
    elif pattern.seq[i][0] == "Z":
        # remove duplicates
        _domain = np.array(pattern.seq[i][2])
        uind = np.unique(_domain)
        unique_domain = []
        for ind in uind:
            if np.mod(np.count_nonzero(_domain == ind), 2) == 1:
                unique_domain.append(ind)

        new_domain = []
        for idx in unique_domain:
            try:
                new_domain.append(dictonary[idx])
            except KeyError:
                continue
        if new_domain == []:
            continue
        print(
            f'seq.append(["Z", {dictonary[pattern.seq[i][1]]}, [{", ".join(new_domain)}]])'
        )

[king-p3nguin]

Also, I was a bit confused about how the "X" and "Z" commands work. pattern.print_pattern() seems to remove duplicate nodes in the list, but StatevectorBackend.correct_byproduct(cmd) does not?

[shinich1]

https://github.com/TeamGraphix/graphix/pull/56#issuecomment-1626050694

What's this code supposed to do? and what exactly is the issue? could you elaborate?

[shinich1]

Also, I was a bit confused about how the "X" and "Z" commands work. pattern.print_pattern() seems to remove duplicate nodes in the list, but StatevectorBackend.correct_byproduct(cmd) does not?

the results are the same, we are thinking about a way to make sure we simplify signal lists in an efficient way, not just when printing

[king-p3nguin]

#56 (comment)

What's this code supposed to do? and what exactly is the issue? could you elaborate?

Sorry, I did not explain it enough. What I was doing is that I generated the commands from a circuit that has only one Toffoli gate and replaced the node number in the commands with ancilla[i], control_node1, control_node2, and target_node so that I can simply copy & paste directly into the code. The issue is that the _ccx_command method I added by pasting the generated code does not seem to work correctly. The following code is used to check how the _ccx_command method works:

from graphix.transpiler import Circuit

for i in range(2**3):
    circuit = Circuit(3)
    # prepare |000>
    circuit.h(0)
    circuit.h(1)
    circuit.h(2)
    # prepare |i>
    for idx, j in enumerate(format(i, "03b")[::-1]):
        if j == "1":
            circuit.x(idx)

    print(format(i, "03b")[::-1], ":")

    circuit.ccx(0, 1, 2)
    pattern = circuit.transpile()

    pattern.standardize()
    pattern.shift_signals()
    pattern.perform_pauli_measurements()
    pattern.minimize_space()

    from qiskit.quantum_info import Statevector

    ket = pattern.simulate_pattern(backend="statevector").flatten()
    ket = Statevector(ket)
    display(ket.draw(output="latex"))

[shinich1]

I see, it might be worth looking into graph state for toffoli gate and check their LC form after pauli measurement, e.g. look for isolated nodes. Just to check, have you modified pattern.perform_pauli_measurements() so it leave input qubits unmeasured? you may need to find alternative way and perhaps try out ZX calculus to get correct pattern fragment - rather than copy and paste.

[king-p3nguin]

Yes, I also tried skipping the measurement of input qubits and the results were the same. I'm kind of stuck with this method, so will check ZX calculus.

[king-p3nguin]

By using PyZX and graphix.generator.generate_from_graph(), I was able to create commands for ccx gate (only for opt = False). The commands I just created from pattern.perform_pauli_measurements(leave_input=True) do not seem to be working, so I will work on it later. (I might be missing something)

[king-p3nguin]

I was not able to reduce the nodes a lot for opt=True, but it works for now.

@shinich1 Will you review this PR?

[shinich1]

@king-p3nguin found a better pattern, please take a look. what worked was to manually perform Pauli measurements of the pattern using graph state sim while making sure no local Hadamard remain on either input or output nodes (because these cannot be commuted through next or previous commands), sometimes interleaving with equivalent_fill_nodes of the graph state simulator.

the script I used (works also after perform_pauli_measurements)

circuit = Circuit(3)
circuit.ccx(0, 1, 2)
pattern = circuit.transpile()
pattern.standardize()
pattern.shift_signals()
pattern.draw_graph()
nodes, edges = pattern.get_graph()
vops = pattern.get_vops()
print(nodes)
print(edges)
from graphix import GraphState
nodes2 = [i for i in range(21)]
mapping = {nodes[i]: nodes2[i] for i in range(21)}
edges2 = [(mapping[i], mapping[j]) for i,j in edges]
vop2 = dict()
for i in nodes:
    if i in vops.keys():
        vop2[mapping[i]] = vops[i]
    else:
        vop2[mapping[i]] = 0
g=GraphState(nodes=nodes2, edges=edges2, vops=vop2)

results = dict()
results[3] = g.measure_x(3)
g.equivalent_fill_node(2)
results[4] = g.measure_x(4)
results[6] = g.measure_x(6)
results[12] = g.measure_x(12)
g.equivalent_fill_node(1)
results[11] = g.measure_x(11)
results[19] = g.measure_x(19)
results[9] = g.measure_x(9)
# 17, 14
g.draw()
print(results)

[shinich1]

@king-p3nguin would you be happy to add type hints to transpiler.py?

[shinich1]

@king-p3nguin looks great, thanks! if it's ready on your side, please squash and merge.

[king-p3nguin]

@shinich1 Thank you for the optimization! I will merge this after testing.