(1) This problem continues (5) and (6) from the previous set. All parts are about a general n- qubit graph-state circuit CG where G is an undirected graph on n nodes, possibly allowing self-loops but not multiple edges. They also refer to the maze diagram visual-aid used in lectures. For better visual clarity we abbreviate (0"|CG|0) as (0"|G|0) and so on. (a) Consider inputs x to Cg other than 0". Let the rows be indexed by binary strings u {0,1}" that of course may be different from r. Give the rule for the middle section of row u to begin with a -1 phase. You may find the text's Lemma 5.1 about the Hadamard transform helpful. (b) Use the rule in (a) to show that (0"|G|r) equals (0|G2|0), where Go is the graph obtained from G by adding self-loops to the nodes i such that Xi = 1. (You may suppose that the original G has no self-loops in your argument. It will then extend fairly readily to say that if G already has a self-loop at node i, then adding a self-loop to node i means removing it. Put another way, only the even-odd parity of edges and loops matters. Note also that the "input goes on the right in (0"|G|x). Actually, because all the gates are self-adjoint, this case is perfectly left-right symmetric, a fact that might help you in the next part.) (c) Now show that if u ov = x@y, then (y|G|x) = (v|G|u). You may be able to take (and justify) one of various shortcuts. (d) Conclude further from this that all possible cases of (z|G|y) are covered by cases of (0"|G2|0) for appropriately-defined graphs Gx. (e) Added: One can interpret the initial and final Hn transforms as transforming from the stan- dard basis (a.k.a the Z-basis) to the Hadamard basis (a.k.a. the X-basis). We can instead work within the Z-basis. In order to make an operator A defined in one basis produce output within the new basis as well as take input from it, one must sandwich A by the transform and its inverse. Since Hn is self-inverse, this just means replacing CZ by 1 1 1 -1 1 E= = (H2)(CZ)(H2) 1 1 1 -1 1 1 1 1 1 1 1 (This also equals sandwiching a CNOT gate between two Hadamards on its control line only. My E just means edge; I can't find a standard name for it.) The transform of Z is just HZH = X. Say in a few sentences what happens if you redo your answers, in particular (b) and (c), in the other basis. Does it help in confirming them? (6+12+12+6+9 = 45 pts.)