4. Let G be a graph on n labeled vertices 1, 2, ...,n. We can describe Gusing m = O(n) bits. Let S denote the set of permutations o of {1, 2, ..., n}. We denote by o(G) the result of relabeling the vertices of G using o. Let Ug be a quantum gate operating on m qubits that realizes the mapping 10%) 2X10(G)). (a) Consider two graphs G1 and G2 on n labeled vertices. What can you tell about UGO) and UG 0m) in case G1 and G2 are isomorphic? What if G1 and G2 are not isomorphic? (b) Use part (a) to construct an algorithm for the graph isomorphism problem that uses a polynomial number of standard quantum gates and applications of U, where U is a quantum gate operating on m+m qubits realizing |G)|OM) + |G)UG|0M). (c) Part (b) implies that the graph isomorphism problem can be solved in polyno- mial time on a quantum computer provided U can be realized uniformly using a polynomial number of standard quantum gates. Pinpoint the error in the following proof of the latter hypothesis: We can describe each o E S as a bit string of length n[log n] where the ith block of log n] bits equals o(i). By concatenating with zeros, we obtain a description of m bits. We can efficiently create a uniform superposition of all the m-bit strings o that describe a permutation in S. Since we can classically compute o(G) in polynomial time from G and o, we can realize U uniformly using a polynomial number of standard quantum gates. 4. Let G be a graph on n labeled vertices 1, 2, ...,n. We can describe Gusing m = O(n) bits. Let S denote the set of permutations o of {1, 2, ..., n}. We denote by o(G) the result of relabeling the vertices of G using o. Let Ug be a quantum gate operating on m qubits that realizes the mapping 10%) 2X10(G)). (a) Consider two graphs G1 and G2 on n labeled vertices. What can you tell about UGO) and UG 0m) in case G1 and G2 are isomorphic? What if G1 and G2 are not isomorphic? (b) Use part (a) to construct an algorithm for the graph isomorphism problem that uses a polynomial number of standard quantum gates and applications of U, where U is a quantum gate operating on m+m qubits realizing |G)|OM) + |G)UG|0M). (c) Part (b) implies that the graph isomorphism problem can be solved in polyno- mial time on a quantum computer provided U can be realized uniformly using a polynomial number of standard quantum gates. Pinpoint the error in the following proof of the latter hypothesis: We can describe each o E S as a bit string of length n[log n] where the ith block of log n] bits equals o(i). By concatenating with zeros, we obtain a description of m bits. We can efficiently create a uniform superposition of all the m-bit strings o that describe a permutation in S. Since we can classically compute o(G) in polynomial time from G and o, we can realize U uniformly using a polynomial number of standard quantum gates
