Entangled set isn't computed correctly

[ellishg]

I'm pretty sure we need to rethink how we trim programs.

In this program, qubits 0 and 1 don't look entangled, but they actually are since qubit 0 affects the control flow. If we care about qubit 1, then we need to also care about qubit 0.

H 0
MEASURE 0 ro
JUMP-WHEN @END ro
X 1
JUMP @END

[seankdecker]

Hmmm that's interesting. Are q_0 and q_1 entangled? q_0 has been measured so it is in a definite state by the end of this program, but we have uncertainty about what the measurement is going to be. We are either in |00> or |11>, but we are uncertain about the state, although the state is definitely in one of these two. Isn't this the difference between writing something as a mixed state as opposed to a composite state.

Maybe, to fix this, we should add another function that tracks control flow sets also? So that "qubit reliance", the thing we care about, is a mix of control flow sets and entanglement sets?

[ellishg]

Was typing out some thoughts at the same time. The code now would delete H 0 if we asked about qubit 1. I'm probably not using "entangled" in correct physical definition, and is like a mix of control flow sets and entanglement sets. Maybe we should think of a different word. Here's a rough outline of a candidate algorithm.

Within a basic block we can accurately compute the entanglement set since there is no control flow, but we cannot delete any instructions until we know the true entangled set of the full program. We can do this in a function get_entangled_from_qubit(basic_block, qubit). Then we can compute all the entangled sets for all the basic blocks. For a given basic block, b, we can look at the last instruction of all of its parents P to find the classical bits that determine the control flow to b. The qubits that determine those classical bits (and their entangled qubits) must be added to all the entangled sets of b. In the example, since qubit 0 affects ro and ro affects the execution of X 1, then qubit 0 is entangled with qubit 1. We probably need another function get_entangled_from_bit(basic_block, bit) to get an entangled set for a classical bit. Since entangled sets can propagate through multiple basic blocks, we need to run this until convergence.

Once we know the full entangled set, we can start removing instructions and possibly removing basic blocks. Since that might affect the entangled set, we have to repeat this process until it stabilizes.

Let me know what you guys think!

[moodlezoup]

I agree. I would add that I think there is a fundamental difference between "entanglement dependencies" and "control flow dependencies". The control flow dependencies only matter insofar as whether or not the basic block gets executed. Consider the following pseudocode:

H 0 
H 2
CNOT 0 1
CNOT 2 3
X 0
X 2
MEASURE 3 ro[0]
JUMP-WHEN @END ro[0]
X 2
X 1
// breakpoint here
LABEL @END

Consider the basic block between the JUMP-WHEN and the END. Its "entanglement dependency" is the entanglement set {0, 1}, but its "control flow dependency" is the entanglement set {2, 3}. If we ran trim_program([1]) at the point indicated by the comment, we could remove the X 2 instruction after the JUMP-WHEN but not the one before.

I haven't given this too much thought yet, but I think we can generalize this as follows:

• We keep any instructions acting on the entanglement dependencies of the queried qubits.
• We keep other instructions only if they affect subsequent branches in the DAG (on the root-node path to the current basic block).
• We can also trim any basic blocks that don't have a path to the current basic block

[ellishg]

That's a good example, I hadn't thought of that. I don't think this is complete because there could be a sequence of basic blocks on the execution path that have no affect on the queried qubits. Consider the control flow graph

"root" -> bbA -> bb1 -> bb2 -> bbB
                  ^      |
                   \____/

Our breakpoint is in bbB and we have entangled qubits in bbA and bbB, but not in bb1 or bb2. We would like to remove bb1 and bb2 even though they affect the control flow. This example would also work for if statements, I think.

[ellishg]

I think it would be good to put together some test cases before we start implementing.