How to construct a quantum circuit (QIP system) for the graph non-isomorphism problem?

Question

I'm having some trouble understanding quantum interactive proof systems (QIP systems) and the related circuit constructions. Interactive proof systems model these type of situations:

Interactive proof systems:

To say a promise problem $\mathcal{A}$ has an interactive proof system means there exists a verifier meeting two conditions:

Completeness: For every input $x\in \mathcal{A}_{\text{yes}}$, there must exist a prover strategy causing the verifier to accept with high probability.

Soundness: For every $x\in \mathcal{A}_{\text{no}}$, all prover strategies must cause the verifier to reject with high probability.

Classical protocol for graph non-isomorphism:

Now let's consider the classical proof system for the graph non-isomorphism problem.

Input: Two simple undirected graphs $G_0$ and $G_1$.

Yes: $G_0$ and $G_1$ are not isomorphic. ($G_0 \ncong G_1$).

No: $G_0$ and $G_1$ are isomorphic. ($G_0 \cong G_1$).

There is a simple (classical) interactive proof system requiring just one question and response:

1. The verifier randomly chooses a bit $b\in\{0,1\}$ and a permutation $\sigma \in S_n$, and sends $\mathcal{H}=\sigma(G_b)$ to the prover.

2. Implicitly, the prover is being challenged to identify whether $b=0$ or $b=1$. If the prover guesses correctly, the verifier accepts (or outputs $1$), otherwise he rejects (or outputs $0$).

Quantum interactive proof systems:

The quantum interactive proof system works exactly the same as the classical model except that the prover and verifier may exchange and process quantum information. General assumptions and notions of completeness and soundness are unchanged. The model may be formalized in terms of quantum circuits. An illustration of an interaction:

(There are 6 messages in this example.)

Quantum protocol for graph non-isomorphism?

The previous section on quantum interactive proof systems appears rather vague to me. I'm not sure how we can map a classical interactive proof system protocol to an equivalent quantum protocol or construct a quantum circuit for it (as shown in the above example).

For simplicity, let's just take the graph non-isomorphism problem. What would be a quantum circuit i.e. a quantum interactive proof system for the graph non-isomorphism problem? How to construct such a quantum circuit, given that we know the corresponding classical proof system protocol?

---

^{Note: All quotes are from John Watrous - Quantum Complexity Theory (Part 2) - CSSQI 2012 (timestamp included).}

Answer 1

As I understand $\mathsf{IP}$ and similarly $\mathsf{QIP}$, two parties, prover Peggy and verifier Vicky, engage in a number of rounds that are polynomial in $n$. Each round consists of Vicky providing a challenge to Peggy, then Peggy replying with a response, with the challenges and responses being a function of the previous rounds. Eventually after the polynomial number of rounds, Vicky should be convinced by Peggy. This is how I read Shamir's $\mathsf{IP=PSPACE}$ paper - after each round, Peggy simplifies a polynomial based on challenges from Vicky, until eventually Vicky can be assured that the polynomial is non-zero.

This is distinct from the standard protocol used for the graph non-isomorphism $GNI$ problem. In $GNI$, the weaker Vicky challenges the powerful Peggy with a single round to determine which graph Vicky has permuted. The $GNI$ protocol can be run a plurality of times between Vicky and Peggy to amplify soundness, but each round is done independent of the others, and there is no challenge/response that is based on previous challenge/responses.

Furthermore the classes $\mathsf{MA}$ and $\mathsf{QMA}$ are different still - here the powerful Merlin provides the weaker Arthur initially with a classical/quantum certificate (not the other way around).

Watrous ended the 2000 paper "Succinct Quantum Proofs for Properties of Finite Groups" with an open question as to whether $GNI\in\mathsf{QMA}$.

Okamoto and Tanaka offer an answer Watrous's problem in the affirmative with their 2007 paper "Graph Non Isomorphism Has a Succinct Quantum Certificate." Although there are some areas in the paper that are causing me a little bit of confusion, as I understand it Merlin's quantum certificate $\mathsf{MA}$ protocol for $GNI$ consists of $O(n^{12})$ replicates of their FIG. 1. Their verification procedure entails Arthur burning through most of these by measuring random replicates without performing any quantum gates, just to confirm that the structure of the certificates for remaining replicates is highly likely to be correct. They then have Arthur permute adjacency matrices conditioned on the value of their garbage registers (going from FIG. 1 to FIG. 2). At the end they have Arthur perform some CNOTs and Hadamard transforms on remaining replicates, to get a rough measure of the structure of the replicates and how close the vectors in the replicates are to one another.

In step 6 in their protocol, Arthur has possession of a state that should be a uniform superposition of (an appropriately normalized version of)

$$\sum_{b\in\{0,1\},i\in S_n}\vert b\rangle\vert \pi_i(G_b)\rangle$$

for rigid graphs $G_0$ and $G_1$. That is, the state that Arthur possesses consists of a uniform superposition over all adjacency matrices that are equivalent to either the given $G_0$ or the given $G_1$. Arthur can then Hadamard and measure $\vert b \rangle$. Depending on whether $G_0\not\cong G_1$, after Hadamarding Arthur should measure $b=1$ the appropriate number of times.

Even though Okomoto and Tanaka's protocol uses $O(n^{12})$ replicates, it still is fundamentally an $\mathsf{MA}$ protocol, as most of these replicates are for improving soundness. The protocol does not use the sophistication of more than one round of interaction in $\mathsf{QIP}$ (the second figure in the question). Certainly such a multi-round $\mathsf{QIP}$ protocol is likely to exist, because $GNI\in\mathsf{AM}\subseteq\mathsf{IP}=\mathsf{PSPACE}=\mathsf{QIP}$, but at least according to Okomoto and Tanaka, it would be overkill and a single round is sufficient.